Publicação: Aplicação de algoritmo genético para roteirização e carregamento de veículo
Carregando...
Arquivos
Data
Autores
Orientador
Silva, Márcia Aparecida Zanoli Meira e 
Coorientador
Pós-graduação
Curso de graduação
Ciência da Computação - FC
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Tipo
Trabalho de conclusão de curso
Direito de acesso
Acesso aberto
Resumo
Resumo (português)
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.
Resumo (inglês)
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.
Descrição
Palavras-chave
Meta-heurística, Roteamento de veículos, Algoritmo genético, Metaheuristics, Genetic algorithm, Vehicle routing
Idioma
Português
