Evolutionary algorithm with hybrid methodology for elaboration of distribution routes

In the logistical chain of parcel delivery in general, the difficulties of managing the routes of distribution are remarkable. The present work has the objective of developing a software prototype capable of optimizing the order distribution route, using as a case study the registered orders of the post office in the city of Coromandel / MG. It is highlighted in this paper the option of elaborating routes that facilitate their use according to the type of vehicle used by the delivery of orders. An OpenStreetMap database was used to locate the geographical coordinates of residences and streets, and the routes are defined through a hybrid genetic algorithm based on travelling salesman problem and also with the Dijkstra algorithm to define the minimum cost path between the vertices of the problem. This work is also described as elaboration stages, as well as the results obtained experimentally. Finally, it is concluded through this work that the use of hybrid algorithms presents a great potential for the resolution of routing problems, including those in which the type of vehicle to be used in the deliveries is considered.Dissertação (Mestrado)Na cadeia logística de entrega de encomendas de um modo geral, são notáveis as dificuldades de se elaborar as rotas de distribuição. O presente trabalho tem como objetivo o desenvolvimento de um protótipo de software capaz de otimizar a rota de distribuição de encomendas, utilizando como estudo de caso as encomendas registradas dos correios na cidade de Coromandel/MG. Destaca-se neste trabalho a opção de elaboração de rotas que facilitam a sua utilização de acordo com o tipo de veículo utilizado pelo entregador das encomendas. Foi utilizada a base de dados OpenStreetMap para localização das coordenadas geográficas das residências e ruas, sendo que as rotas são definidas através de um algoritmo genético híbrido baseado no problema do caixeiro viajante e utilizando o algoritmo de Dijkstra para definir qual o caminho de custo mínimo dentre as vértices do problema. Neste trabalho também são descritas as etapas de elaboração, bem como os resultados obtidos de forma experimental. Ao final, conclui-se através deste trabalho que a utilização de algoritmos híbridos apresenta um grande potencial para a resolução de problemas de roteamento, incluindo aqueles nos quais são considerados o tipo de veículo a ser utilizado nas entregas