Resumo: O problema de definir rotas para veículos é enfrentado diariamente por empresas que realizam entregas, coletas, atendimentos em domicílios, transporte de cargas, pessoas, alimentos, entre outros. Também é um problema clássico em computação, sendo estudado por décadas e sendo desafiador até os dias atuais. O problema de roteamento pode ser dividido em dois casos. Se houver apenas um veículo, temos o Problema do Caixeiro Viajante, conhecido pela sigla TSP. Se tivermos que atender os clientes com uma frota de veículos, temos o Problema de Roteamento de Veículos, conhecido pela sigla VRP. Temos o surgimento de novas ferramentas para resolver tanto o TSP quanto o VRP, porém é necessário executar experimetos com as tais ferramentas para validá-las. Neste trabalho realizamos um estudo da ferramenta Google OR-Tools, uma ferramenta lançada pelo Google para resolver uma série de problemas de otimização. O Google OR-Tools resolve problemas como Otimização Linear, Otimização Inteira, Otimização de Restrições, Agendamento, Roteamento entre outros. Nosso foco foi utilizar a ferramenta para problemas de roteamento, tanto para o TSP quanto para o VRP. Este trabalho utilizou a linguagem Python e trabalhou com dois conjuntos de instâncias, algumas vindas do TSPLIB95 e outras vindas do PostVRP, que são instâncias feitas para carteiros nas cidades de Artur Nogueira e Rio Claro. Foi necessário fazer a leitura e processamento dos arquivos das instâncias, deixá-los no formato adequado para o Google OR-Tools e depois ajustar uma série de parâmetros para poder realizar os experimentos. Por exemplo, existem estratégias de resolução como GLOBAL_CHEAPEST_ARC, PATH_CHEAPEST_ARC e a GUIDED_LOCAL_SEARCH. Executamos as instâncias com cada uma das estratégias e comparamos os resultados. Também comparamos os resultados com o ótimo, quando este era conhecido. O resultado deste TCC consiste em analisar o esforço necessário para se executar instâncias utilizando o Google OR-Tools e também analisar a qualidade da solução versus o tamanho da solução versus o tempo de execução dos algoritmos de otimização. Além de analisar o esforço necessário para se utilizar a ferramenta Google OR-Tools, pudemos atestar a qualidade dos resultados em instâncias com ótimo conhecido e em instâncias reais de roteamento Ver menos

Abstract: The issue of defining vehicles routes is faced daily by companies that works with deliveries, collection, home care, cargo transport, passenger transport, food transport, among others. It is also a traditional computing issue, which has been studied for decades and remains challenging until nowadays. The routing issues could be divided in two cases. If only one vehicle is available, it defines the Travel Salesman Problem, also know by the acronym TSP. If the customers will be attended by a vehicle fleet, it defines another routing issue know by the acronym VRP. New tools has being emerged to solve both TSP and VRP issues, but it is necessary to execute experiments with those tools to validate them. On this work we carried out a study of the Google OR-Tools, a tool released by Google to solve a lot of optimization issues. The Google OR-Tools solve issues as Linear Optimization, Integer Optimization, Constraint Optimization, Scheduling, Routing, among others. Our focus was to validate the tool on routing issues, both for TSP and VRP. This work used Python language and worked with two sets of instances, some came from TSPLIB95 and others came from PostVRP, that are instances made to postmen in the cities of Artur Nogueira and Rio Claro. It was necessary make the parse from those instances files, them process it, transform the data on the proper format to Google OR-Tools and them adjust a lot of parameters to be able to realize all the experiments. As example there is solve strategies as GLOBAL_CHEAPEST_ARC, PATH_CHEAPEST_ARC and GUIDED_LOCAL_SEARCH. We executed those instances with each of the strategies and we compared the results. We also compared the results with the optimum solution, when it was know. The result of this final paper consists on analyze the necessary effort to execute those instances using Google OR-Tools and also analyze how good was the solution against the solution size and against the cost from the execution time from the optimization algorithms. In addition to analyzing the effort required to use the Google OR-Tools, we could certify the results quality on instances with a know optimum tour and also on real routing issue instances Ver menos