Por favor, use este identificador para citar o enlazar este ítem:
https://repositorio.ufu.br/handle/123456789/31794
ORCID: | ![]() |
Tipo de documento: | Trabalho de Conclusão de Curso |
Tipo de acceso: | Acesso Aberto |
Título: | Comparação de duas meta-heurísticas para a resolução do Problema de Roteamento de Veículos (PRV) |
Autor: | Morelli, Laura Caligaris Perim |
Primer orientador: | Reis, Jorge von Atzingen dos |
Primer miembro de la banca: | Costa, Eugênio Pacceli |
Segundo miembro de la banca: | Silva, Hebert Roberto da |
Resumen: | Para manter o nível de competitividade as organizações buscam meios de otimização para as operações, possibilitando o estudo e desenvolvimento de modelos de otimização, onde o roteamento de veículos se enquadra nos problemas clássicos dentro do gerenciamento logístico. O Problema de Roteamento de Veículos (PRV) é uma extensão do Problema do Caixeiro Viajante (PCV), ao adicionar diversas restrições. O PRV é classificado como um problema NP-hard, ou seja, não existe um algoritmo que encontre a solução ideal em tempo polinomial. Nesse contexto, as organizações com mais processos ágeis e eficientes trazem um enorme valor agregado na experiência dos clientes sobrevivendo à concorrência. Dessa forma o roteamento de veículos é um dos maiores gargalos para roteirização para organizações e se enquadra nos problemas clássicos dentro do gerenciamento logístico. O presente trabalho aborda um estudo onde é necessário desenvolver e implementar um modelo matemático no software de otimização Gurobi (2021) capaz de determinar rotas para diferentes veículos com capacidades distintas, o qual retornará a solução ótima referente ao melhor roteamento de veículos a ser implementado, porém demanda um tempo elevado para retornar tal solução. Com o intuito de diminuir esse tempo, foi desenvolvida uma heurística construtiva e posteriormente duas meta-heurísticas: Variable Neighborhood Search (VNS) e Iterated Local Search (ILS) a fim de comparar os resultados entre si e buscar a minimização de custos logística. Como resultado, foi possível desenvolver uma metodologia para otimizar a resolução do Problema de Roteamento de Veículos (PRV), porém é possível realizar melhorias como uma nova busca local |
Abstract: | The organizations search ways to improve their operations to maintain the high level of competitiveness, making possible the study and development of optimization models, where the vehicle routing fits on the classical problems from logistics management. The Vehicle Routing Problems (VRP) is an extension from the Travel Salesman Problem (TSP) when adding various restrictions. The VRP is classified as an NP-hard problem, in other words, there is no algorithm that finds an ideal solution in a polynomial time. In that context, the organizations with more optimized processes and low costs, survive the competition. This way, the VRP is one of the biggest problems to the routing for organizations and it fits on the classical problems from the logistics management. The present work is about a study where it is necessary to develop and implement a mathematical model on the optimization software Gurobi (2021) capable to determine routes to different vehicles with distinct capabilities, which will return an optimum solution indicating the best vehicle routing to be implemented, but much time is needed to return the solution. In order to speed the process, it was developed a constructive heuristic and, later, two metaheuristics: Variable Neighborhood Search (VNS) and Iterated Local Search (ILS) to compare the results between itself and seek the minimum cost from logistics operation by a distributor located in Guarulhos. The result was possible to develop a methodology to optimize the Vehicle Routing Problems (VRP) resolution, but it is possible to make improvements with a new local search. |
Palabras clave: | Pesquisa operacional Meta-heurística PRV VNS ILS Logística |
Área (s) del CNPq: | CNPQ::ENGENHARIAS |
Idioma: | por |
País: | Brasil |
Editora: | Universidade Federal de Uberlândia |
Cita: | MORELLI, Laura Caligaris Perim. Comparação de duas meta-heurísticas para a resolução do Problema de Roteamento de Veículos (PRV). 2021. 43 f. Trabalho de Conclusão de Curso (Graduação em Engenharia de Produção) - Universidade Federal de Uberlândia, Uberlândia, 2021. |
URI: | https://repositorio.ufu.br/handle/123456789/31794 |
Fecha de defensa: | 14-may-2021 |
Aparece en las colecciones: | TCC - Engenharia de Produção (Ituiutaba / Pontal) |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
ComparaçãoMetaHeurísticas.pdf | TCC | 24.12 MB | Adobe PDF | ![]() Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons