Orientador: Paulo Morelato França

Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica

Resumo: O Problema de Roteamento de Veículos (PRV) consiste basicamente em definir rotas eficientes para uma frota de veículos que deve entregar quantidades de bens a um conjunto de clientes. Vários métodos têm sido propostos para tal tarefa, mas devido ao esforço computacional requerido, problemas...

Resumo: O Problema de Roteamento de Veículos (PRV) consiste basicamente em definir rotas eficientes para uma frota de veículos que deve entregar quantidades de bens a um conjunto de clientes. Vários métodos têm sido propostos para tal tarefa, mas devido ao esforço computacional requerido, problemas de maior porte (50 clientes ou mais) são resolvidos por algoritmos aproximados. Dentre estes algoritmos aproximados, abordamos os métodos de melhoria de rotas. Estes métodos são caracterizados pela geração de uma solução inicial factível, seguida da aplicação de mecanismos de busca que alteram a solução inicial. Estes mecanismos promovem essencialmente a melhoria da função objetivo em direção a um mínimo local. Neste ponto, dada a falta de movimentos de melhoria, o algoritmo pára. Apesar do desempenho excelente deste métod6S, observa-se uma limitação fundamental. Sendo o PRV um problema combinatório e, portanto, não convexo, o ótimo local obtido pode não ser o ótimo global. Conseqüentemente, a qualidade da solução final depende drasticamente da solução de partida. Várias técnicas foram elaboradas com vistas à superação da otimalidade local. A maioria delas recomeça o processo de busca a partir de soluções iniciais diferentes ou atrasa a obtenção do ponto ótimo. Outra maneira de lidar com tais limitações é através da aplicação da estratégia de Busca Tabu. Ao invés de evitar ótimos locais, a Busca Tabu os supera, permitindo assim a continuidade das explorações. Neste trabalho apresentamos um estudo da aplicação da técnica de Busca Tabu ao PRV. Um algoritmo dotado de mecanismos de Busca Tabu foi utilizado para a resolução de vinte problemas caracterizados pela existência (ou ausência) de certas restrições temporais. Procedemos a várias análises do comportamento do algoritmo e comparações com outros métodos heurísticos. Os resultados indicaram ser a BuscaTabu uma ferramenta poderosa na resolução de problemas combinatórios

Abstract: Not informed.