Resumo: O Problema de Roteamento de Veículos (do inglês Vehicle Routing Problem, VRP) é uma generalização do Problema do Caixeiro Viajante (do inglês Traveling Salesman Problem, TSP). É um problema que têm no seu contexto várias rotas e veículos. O VRP pode ser encontrado em vários problemas cotidianos como entrega de cartas, coleta de lixo, transporte público (ônibus/mêtro), entre outros. Neste trabalho utilizamos dois algoritmos, o algoritmo de troca de vértice (TrocaV) e o de troca de arestas, também chamado 2-Opt. Ambos algoritmos foram retirados da literatura. Utilizamos uma variante do VRP que limita a capacidade da rota. Como modelo utilizamos o benchmark conhecido como PostVRP, que é um benchmark que possui instâncias com diversos pontos de entrega. Possui instâncias com no mínimo 20 pontos de entrega e, no máximo, 30.000 pontos de entrega. O algoritmo de Troca de vértice (TrocaV) foi executado em instâncias com até 1.000 pontos de entrega e o 2-Opt em instâncias com até 10.000. Comparando as soluções criadas pelos dois algoritmos, o 2-Opt obteve resultados superiores ao do TrocaV. Em alguns casos o custo do 2-Opt foi duas vezes menor que o TrocaV Ver menos

Abstract: The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem (TSP). It is a problem that has in its context several routes and vehicles. VRP can be found in many everyday problems such as letter delivery, garbage collection, public transportation (bus / subway), among others. The Vertex Swap algorithm (TrocaV) ran on instances with up to 1,000 delivery points and 2-Opt on instances with up to 10,000. Comparing the solutions created by the two algorithms, 2-Opt obtained better results than TrocaV. In some cases the cost of 2-Opt was twice as low as TrocaV. In this work we developed two algorithms, the vertex exchange algorithm (TrocaV) and the edge exchange algorithm, also called 2-Opt. We use a variant of VRP that limits the capacity of the route. As a model we use the benchmark known as PostVRP, which is a benchmark that has instances with multiple delivery points. It has instances with a minimum of 20 delivery points and a maximum of 30,000 delivery points Ver menos