Aplicação de Metaheurísticas para o problema de roteamento de veículos dinâmico para transporte reativo a demanda

Abstract

Os problemas de roteamento de veículos são de grande importância na pesquisa operacional, uma vez que envolvem problemas relacionados a logística de distribuição de mercadoria e/ou transportes de pessoas e possuem aplicabilidade em diversas áreas da economia. Este trabalho aborda o problema de roteamento de veículos estático e dinâmico para transporte reativo a demanda. Por ser um transporte sob demanda, as necessidades dos passageiros devem ser consideradas também durante a determinação das rotas dos veículos a fim de garantir a qualidade do serviço prestado, flexibilidade das rotas e eficiência na utilização do veículo com um mínimo de adição de ônus para o prestador. Visto que o problema possui características combinatórias, foi proposta para o caso estático uma heurística GRASP Reativo onde o parâmetro de aleatoriedade utilizado durante a construção da solução tem sua probabilidade de escolha autocalibrada. Foram propostas e testadas combinações de estratégias e movimentos a fim de determinar a escolha mais adequada para solução de instâncias do problema. Além disso, foi proposto um algoritmo híbrido substituindo-se a Busca Local do GRASP Reativo pelo método Busca Tabu. Por fim, foram propostos e testados algoritmos de replanejamento para o caso dinâmico. Os resultados obtidos pelos algoritmos propostos são comparados entre si e com resultados gerados por algoritmos da literatura. A análise e discussão dos resultados mostram que os métodos propostos alcançaram resultados satisfatórios, visto que as metaheurísticas obtiveram em média resultados pelo menos 10,27% melhores que algoritmos da literatura no caso estático, e os métodos de replanejamento conseguem melhorar ainda mais estes resultados.

Vehicle routing problems have great interest in operations research, as they are logistics problems related to the delivery of goods and people transportation, and because they have applications in several fields of economy. This work deals with static and dynamic vehicle routing problem for demand responsive transportation. Being a responsive transportation, passengers' needs must be considered also along the route planning, in order to assure the quality or service, route flexibility and vehicle usage effectiveness, with minimum impact in the costs for the company. Since the problem has combinatorial characteristics, a Reactive GRASP heuristic is proposed for the static case. The randomness parameter used in construction phase has its probability self-adjusted. To find the approach best suited for the set of instances, different combinations of strategies and neighborhoods are proposed and tested. Besides that, it is proposed an hybrid algorithm, substituting the local search of the Reactive GRASP by an Tabu Search method. Furthermore, dynamic replanning algorithms were proposed and tested for the dynamic scenario. The results of the proposed methods are compared one to each other and to results of algorithms from the literature. The experimental analisys shows that the proposed methods give satisfactory results, as the metaheuristics obtained in average solutions 10,27% better than those from the literature in the static scenario, and the dynamic replanning methods improve the results even further.