https://repositorio.ufjf.br/jspui/handle/ufjf/19116
File | Description | Size | Format | |
---|---|---|---|---|
marceloianrezendemenezes.pdf | PDF/A | 1.17 MB | Adobe PDF | View/Open |
Type: | Trabalho de Conclusão de Curso |
Title: | Um algoritmo multi-start iterated greedy para o problema de roteamento de veículos com drones |
Author: | Menezes, Marcelo Ian Rezende |
First Advisor: | Moreno, Lorenza Leão Oliveira |
Co-Advisor: | Gonçalves, Luciana Brugiolo |
Referee Member: | Borges, Carlos Cristiano Hasenclever |
Referee Member: | Soares, Stênio Sã Rosário Furtado |
Resumo: | O transporte de produtos desempenha um papel essencial na indústria global, impulsionando a busca por soluções que tornem a logística mais eficiente e sustentável. Dentro desse contexto, o Problema de Roteamento de Veículos com Drones e Janelas de Tempo (VRP-DTW) surge como uma abordagem promissora para otimizar entregas, integrando caminhões e drones para reduzir custos operacionais, minimizar a emissão de poluentes e agilizar a distribuição de mercadorias. Nesse tipo de problema, são considerados um conjunto de caminhões, todos equipados com drones, que devem atender um número definido de clientes em rotas. Enquanto os caminhões realizam essas entregas, os drones podem auxiliá-los atendendo a outros clientes. O drone se mostra uma alternativa mais barata do que o caminhão, porém, devido à baixa autonomia, deve realizar as rotas em conjunto com os veículos terrestres. Neste trabalho, propõe-se um algoritmo Multi-Start Iterated Greedy, que utiliza técnicas para construção da solução inicial, passa por etapas de destruição, reconstrução e refinamento, utilizando para isso um conjunto de movimentos que exploram as vizinhanças da solução, de forma a encontrar outras melhores. Assim, foram implementados dois métodos, sendo um método baseado em aprendizado por reforço, Q-learning, para guiar a ordem na qual esses movimentos são aplicados usando uma função valor-ação Q. O outro método, Random Variable Neighborhood Descent, envolve a escolha aleatória dessa ordem de movimentos. O desempenho do algoritmo foi comparado a outras abordagens da literatura que tratam o VRP-DTW. Além disso, a performance do Q-learning foi comparada à do Random Variable Neighborhood Descend (RVND) implementado. Os experimentos foram realizados considerando instâncias com 25, 50 e 100 clientes, e os resultados mostram que a abordagem proposta se mostrou competitiva em relação às da literatura, tanto na qualidade das soluções quanto no tempo computacional. E, na comparação do uso do RVND em relação ao uso do Q-learning, a abordagem RVND apresentou desempenho superior. |
Abstract: | The transportation of goods plays a crucial role in the global industry, driving the search for solutions that make logistics more efficient and sustainable. In this context, the Vehicle Routing Problem with Drones and Time Windows (VRP-DTW) emerges as a promising approach to optimizing deliveries by integrating trucks and drones to reduce operational costs, minimize pollutant emissions, and speed up the distribution of goods. In this type of problem, a set of trucks, all equipped with drones, must serve a defined number of customers along their routes. While trucks perform these deliveries, drones can assist by serving additional customers. The drone proves to be a cheaper alternative compared to the truck; however, due to its low autonomy, it must operate in coordination with land vehicles. In this work, a Multi-Start Iterated Greedy algorithm is proposed, which uses techniques for constructing the initial solution, followed by stages of destruction, reconstruction, and refinement, employing a set of moves that explore the solution’s neighborhoods to find better ones. Two methods were implemented: one method is based on reinforcement learning, Q-learning, to guide the order in which these moves are applied using a Q action-value function. The other method, Random Variable Neighborhood Descent (RVND), involves the random selection of the order of these moves. The algorithm’s performance was compared to other approaches from the literature addressing the VRP-DTW. Additionally, the performance of Q-learning was compared to the implemented RVND. Experiments were conducted considering instances with 25, 50, and 100 customers. The results show that the proposed approach proved competitive with those in the literature in terms of both solution quality and computational time. However, when comparing the use of RVND with Q-learning, the RVND approach demonstrated superior performance. |
Keywords: | Roteamento de veículos com drones Janelas de tempo Q-learning Otimização Logística Vehicle routing with drones Time windows Optimization Logistics |
CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO::MODELOS ANALITICOS E DE SIMULACAO |
Language: | por |
Country: | Brasil |
Publisher: | Universidade Federal de Juiz de Fora (UFJF) |
Institution Initials: | UFJF |
Department: | Faculdade de Engenharia |
Access Type: | Acesso Aberto Attribution-NonCommercial-NoDerivs 3.0 Brazil |
Creative Commons License: | http://creativecommons.org/licenses/by-nc-nd/3.0/br/ |
URI: | https://repositorio.ufjf.br/jspui/handle/ufjf/19116 |
Issue Date: | 17-Mar-2025 |
Appears in Collections: | Engenharia Computacional - TCC Graduação |
This item is licensed under a Creative Commons License