Please use this identifier to cite or link to this item: http://www.monografias.ufop.br/handle/35400000/4072
Title: Resolução do problema de roteamento de veículos com janelas de tempo e incerteza nos tempos de viagem e serviço por meio de um algoritmo simheurístico.
Authors: Vasconcelos, Lucas Fernandes
metadata.dc.contributor.advisor: Gomes, Helton Cristiano
Gomes Júnior, Aloísio de Castro
metadata.dc.contributor.referee: Pinheiro, Ruan Carlos Silva Menezes
Gomes Júnior, Aloísio de Castro
Gomes, Helton Cristiano
Keywords: Pesquisa operacional
Otimização combinatória
Veículos - rotas
Programação heurística
Parâmetros estocásticos
Issue Date: 2022
Citation: VASCONCELOS, Lucas Fernandes. Resolução do problema de roteamento de veículos com janelas de tempo e incerteza nos tempos de viagem e serviço por meio de um algoritmo simheurístico. 2022. 51 f. Monografia (Graduação em Engenharia de Produção) - Escola de Minas, Universidade Federal de Ouro Preto, Ouro Preto, 2022.
Abstract: Uma das formas de adotar processos logísticos mais ágeis e adaptados aos perfis dos clientes é a otimização da utilização de veículos e de suas rotas de entrega, objetivando a minimização dos custos envolvidos na operação. Na literatura, este problema corresponde ao Problema de Roteamento de Veículos (PRV). Para tratar complicações realistas e generalizações do modelo básico de roteamento, surge o Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT), onde os clientes devem ser atendidos dentro de um certo período de tempo. Em cenários reais, o tempo de viagem e serviço das rotas pode ser afetado por diversos aspectos, como a má qualidade das vias e condições meteorológicas, o que gera uma incerteza intrínseca aos problemas deste tipo. O presente trabalho tem como objetivo o desenvolvimento de um algoritmo baseado nas chamadas simheuristics, de forma a combinar as meta-heurísticas ILSVNS com as Simulações de Monte-Carlo para encontrar boas soluções para o PRVJT com incerteza nos tempos de viagem e serviço em tempo computacional aceitável. Em um primeiro momento o problema é resolvido em sua forma determinística e, posteriormente, os tempos determinísticos são substituídos por amostras aleatórias de uma função densidade de probabilidade pré-determinada. Por fim, são avaliados os impactos da presença da incerteza nas soluções encontradas. O método proposto foi validado através da comparação dos resultados obtidos com resultados encontrados na literatura para instâncias de pequeno porte, onde a diferença entre os resultados foi mínima ou nenhuma. O algoritmo se mostrou eficiente para resolução de instâncias com clientes distribuídos aleatoriamente e para instâncias com clientes agrupados. Entretanto, os resultados foram consideravelmente piores para instâncias que possuem essas duas características em conjunto.
metadata.dc.description.abstracten: One of the ways to adopt more agile logistics processes and adapted to customer profiles is to optimize the use of vehicles and their delivery routes, aiming to minimize of the costs involved in the operation. In the literature, this problem corresponds to the Vehicle Routing Problem (VRP). To treat realistic complications and generalizations from the basic routing model, the Vehicle Routing Problem with Windows of Time (VRPWT), where customers must be served within a certain period of time. In real scenarios, the travel and service time of the routes can be affected by several aspects, such as the poor quality of the roads and meteorological conditions, which generates an intrinsic uncertainty to the problems of this kind. The present work aims to develop an algorithm based on the so-called simheuristics, in order to combine the ILS-VNS metaheuristics with the Monte-Carlo Simulations to find good solutions for the VRPWT with uncertainty in the travel times and service in acceptable computational time. At first, the problem is solved in its deterministic form and, later, the deterministic times are replaced by random samples of a predetermined probability density function. Finally, the impacts of the presence of uncertainty in the solutions found are evaluated. The method proposed was validated by comparing the results obtained with results found in the literature for small instances, where the difference between the results was minimal or none. The algorithm proved to be efficient for resolving instances with randomly distributed clients and for instances with clustered clients. However, the results were considerably worse for instances that have these two characteristics together.
URI: http://www.monografias.ufop.br/handle/35400000/4072
Appears in Collections:Engenharia de Produção - OP

Files in This Item:
File Description SizeFormat 
MONOGRAFIA_ResolucaoProblemaRoteamento.pdf1 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons