Resolução do problema de alocação de veículos: comparação de algumas técnicas heurísticas

Abstract

O Problema de Alocação de Veículos (VSP - Vehicle Scheduling Problem) consiste em atribuir veículos a um conjunto predeterminado de viagens, com horários de saída e chegada fixos, minimizando os custos operacionais. O objetivo desta pesquisa é comparar a eficiência de algumas técnicas heurísticas para a solução do VSP, e em particular a aplicação da metaheurística denominada Busca Local Dirigida (BLD) quando aplicada sobre soluções iniciais obtidas com as heurísticas pesquisadas. BLD é um método geral, baseado em penalidades, as quais são utilizadas no algoritmo de busca local, para ajudar a guiar a busca para fora de mínimos locais. A técnica opera aumentando a função objetivo com as penalidades. O método BLD foi aplicado para duas funções objetivas distintas, uma baseada em custo e a outra em tempo, utilizando como soluções iniciais as soluções obtidas pelo método de programação concorrente e o método de atribuição. Uma importante contribuição deste trabalho é o estudo computacional que compara a metaheurística com as soluções iniciais citadas, utilizando dados reais e custos fictícios. As conclusões são apresentadas sobre a qualidade dos resultados e sugestões para trabalhos futuros são comentadas