Aplicação de algoritmo genético para roteirização e carregamento de veículo - Rocha, Giulia Rossatto [UNESP] (Universidade Estadual Paulista (Unesp), 2023)
A globalização é responsável pelo surgimento de um maior número de clientes exigentes quanto à prazos e qualidade de entrega de mercadorias. Nesse sentido, a capacidade em atender às necessidades dos clientes, com qualidade e com baixo custo despendido é uma urgência no contexto de concorrência entre empresas de transporte, distribuição e coleta. A logística e a gestão apresentam-se como estratégias para realizar a organização e planejamento dos recursos empresariais de forma a maximizar a execução de pedidos. No entanto, no âmbito da gestão de transportes há dificuldades no planejamento e roteirização dos veículos envolvidos de modo a determinar o melhor percurso, com menor gasto de tempo e recursos operacionais. O presente trabalho teve por objetivo a construção de um software capaz de realizar a roteirização de um veículo que percorra a menor distância possível entre as localidades pré-definidas por um usuário, considerando uma possível limitação de carga do veículo e uma cidade inicial que servirá como depósito. Foram utilizados Algoritmos Genéticos que são meta-heurísticas baseadas no conceito de evolução dos seres vivos e no processo de seleção natural, visto que o Problema de Roteirização de Veículos Capacitados (PRVC) e que o Problema do Caixeiro Viajante (PCV) são chamados de problemas NP-difícil e, portanto, não são capazes de gerar uma solução ótima em tempo computacional viável com algoritmos polinomiais ou técnicas tradicionais da pesquisa operacional. O software desenvolvido consiste em uma aplicação web, desenvolvida em Python, com a utilização do micro framework Flask e do framework Bootstrap para estilização das páginas. Finalmente, o algoritmo desenvolvido foi submetido a diversos testes, alterando alguns parâmetros como o processo de seleção, cruzamento e mutação. Verificou-se que o algoritmo genético se apresenta como uma ótima alternativa para a solução do problema, pois permite a utilização de variedades de parâmetros, apresentando ótimos resultados em um tempo positivo. Por fim, verificou-se que o operador de mutação SM não apresentou bons resultados para obtenção da menor distância possível, enquanto os operadores que se destacaram foram os operadores de cruzamento OX e PMX e os operadores de mutação EM, SIM e DM, tanto em questão de tempo quanto em melhor solução obtida.

Globalization is responsible for the emergence of a greater number of demanding customers in terms of deadlines and delivery quality. Therefore, the ability to meet customer needs, with quality and at a low cost, is urgent in the context of competition between transport, distribution and collection companies. Logistics and management are presented as strategies to carry out the organization and planning of business resources in order to maximize orders execution. However, in the context of transport management, there are difficulties in planning and routing the vehicles involved in order to determine the best route, with less time and less use of operational resources. The objective of this work was to build a software capable of routing a vehicle that travels the shortest possible distance between locations predefined by a user, considering a possible vehicle load limitation and an initial city that will serve as vehicle deposit. Genetic Algorithms were used, which are meta-heuristics based on the concept of evolution of living beings and on the process of natural selection, since the Capacitated Vehicle Routing Problem (CVRP) and the Traveling Salesman Problem (TSP) are called NP-hard problems, therefore, are not able to generate an optimal solution in computational time feasible with polynomial algorithms or traditional operations research techniques. The software presented is a web application, developed in Python, using the microframework Flask and the framework Bootstrap for page styling. Finally, the developed algorithm was submitted to several tests, changing some parameters such as the selection, crossover and mutation process. It was verified that the genetic algorithm presents itself as a great alternative for the problem solution, since it allows the use of a variety of parameters, presenting excellent results in a positive time. Finally, it was verified that the mutation operator SM did not present good results for obtaining the smallest possible distance, while the operators that stood out were the crossover operators OX and PMX and the mutation operators EM, SIM and DM, regarding the matter of time and the best solution obtained.
Genetic algorithm application for vehicle routing and loading
Keywords: Meta-heurística; Roteamento de veículos; Algoritmo genético; Metaheuristics; Genetic algorithm; Vehicle routing