Genetic algorithms applied to the vehicle routing problem

Orientador: Luis Augusto Angelotti MeiraDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de TecnologiaResumo: O Problema de Roteamento de Veículos (do inglês Vehicle Routing Problem, VRP) é uma generalização do clássico Problema do Caixeiro Viajante (do inglês Traveling Salesman Problem, TSP) e pode ser definido de forma ampla como uma classe de problemas que envolvem visitar "clientes" com "veículos". Tal problema surgiu em 1959 e possui uma estrutura desafiadora a ser otimizada. O VRP modela diversas situações reais, como o roteamento de veículos para atender chamadas ou ocorrências, definição de rotas para carteiros, definição de rotas para coleta de lixo, definição de itinerários de ônibus fretados e vans, entre muitas outras. Este trabalho desenvolveu algoritmos genéticos combinados à busca local e os aplicou a duas variantes do problema, focando primariamente na minimização do número de veículos. A primeira variante modela um caso real baseado nos correios de Artur Nogueira, SP, chamada PostVRP. Trata-se de um benchmark de grande escala, com instâncias de até 30.000 pontos de entrega, cujos limitantes são desconhecidos. A segunda variante é chamada CVRP (do inglês Capacitated Vehicle Routing Problem) e o conjunto de instâncias aqui utilizado já possui ótimos conhecidos para fins de comparação. Foram feitos experimentos com quatro variações de algoritmo genético: usando Best Cost Route Crossover (BCR) ou Order Based Crossover (OX) e otimizando com e sem busca local. Os algoritmos propostos obtiveram os ótimos resultados conhecidos em 46% dos casos para as instâncias CVRP, e ficaram mais de 10% piores em apenas 9%. O uso de busca local combinado ao algoritmo genético acelerou a convergência das soluções e, entre os dois operadores de crossover testados, o operador BCR se sobressaiu ao OX. Já para as instâncias do PostVRP, que não possuíam resultados prévios para comparação, conseguimos os primeiros limitantes para o problema considerando instâncias com até 10.000 pontos de entrega. Palavras-chave: VRP, algoritmo genético, busca localAbstract: The Vehicle Routing Problem (VRP) is a generalization of the classic Traveling Salesman Problem (TSP) and it can be broadly defined as a class of problems about visiting "costumers" through "vehicles". Such problem appeared in 1959 and has a challenging structure to be optimized. The VRP models several real situations, like vehicles routing for dispatch calls, establishing routes for mailmen, establishing routes for garbage collection, establishing itineraries for buses, and many others. This work developed genetic algorithms (AGs) combined to local search and applied them to two problem variants, with the primary focus being to minimize the number of vehicles. The first variant models a real case based on the post offices of Artur Nogueira, SP, with the name PostVRP. It is a large scale benchmark, with up to 30,000 delivery points, which has unknown bounds. The second variant is called Capacitated Vehicle Routing Problem (CVRP) and the instances set used here already has known optimal values for comparison purposes. The experiments conducted had four genetic algorithms variations: employing Best Cost Route Crossover (BCR) or Order Based Crossover (OX) and running the AG with or without local search. The proposed algorithms reached the known optimal results in 46% of the CVRP instances, and were more than 10% worse in only 9%. The use of local search combined to the AG accelerated the solutions convergence and, between the two tested crossover operators, BCR surpassed OX. For the PostVRP instances, which had no previous results for comparison, we obtained the first bounds for the problem considering up to 10,000 delivery points. Keywords: VRP, genetic algorithm, local searchMestradoSistemas de Informação e ComunicaçãoMestre em Tecnologi