Please use this identifier to cite or link to this item: https://repositorio.ufjf.br/jspui/handle/ufjf/15931
Files in This Item:
File Description SizeFormat 
eugeniobelizarioribeirofaria.pdfPDF/A893.62 kBAdobe PDFThumbnail
View/Open
Type: Trabalho de Conclusão de Curso
Title: Heurísticas para o problema de roteamento de veículos com drones e janelas de tempo.
Other Titles: Heuristics for the drone vehicle routing problem and time windows.
Author: Faria, Eugenio Belizário Ribeiro
First Advisor: Soares, Stênio Sã Rosário Furtado
Co-Advisor: Gonçalves, Luciana Brugiolo
Referee Member: Menezes, Victor Ströele de Andrade
Referee Member: Moreno, Lorenza Leão Oliveira
Resumo: O problema de roteamento de veículos com drones e janelas de tempo é uma variação do problema clássico de roteamento de veículos onde o conjunto de clientes apresenta elementos que podem ser atendidos por caminhões ou drones e outros que, obrigatoriamente, devem ser atendidos por caminhão. Além disso, cada cliente tem uma demanda conhecida e um intervalo de tempo em que é permitida a entrega. No problema estudado, drones podem ser lançados de caminhões desde que estes estejam parados no depósito ou em algum cliente. Após a realização da entrega, cada drone lançado deve retornar ao mesmo caminhão de onde partiu. O objetivo é minimizar o a deslocamento total necessário ao atendimento da demanda de cada cliente respeitando as restrições de janelas de tempo, capacidade de carga de drones e caminhões, além da autonomia e o alcance dos drones. Foi proposta uma abordagem GRASP (Greedy Randomized Adaptive Search Procedure) que utiliza diferentes heurísticas de construção de forma gulosa randomizada e, na fase de busca local, um algoritmo RVND (Randomized Variable Neighborhood Descent). Como estratégia para melhorar a qualidade da abordagem proposta, utiliza-se um algoritmo baseado em um modelo de Programação Linear Inteira que combina rotas de diferentes soluções.
Abstract: The vehicle routing problem with drones and time windows is a variation of the classic vehicle routing problem where the set of customers has elements that can be serviced by trucks or drones and others that must be serviced by truck. In addition, each customer has a known demand and a time interval in which delivery is allowed. In the problem studied, drones can be launched from trucks as long as they are stopped at the warehouse or at a customer. After the delivery is completed, each drone launched must return to the same truck it started from. The objective is to minimize the total displacement necessary to meet the demand of each client, respecting the restrictions of time windows, carrying capacity of drones and trucks, in addition to the autonomy and range of drones. A GRASP (Greedy Randomized Adaptive Search Procedure) approach was proposed, which uses different construction heuristics in a random greedy way and, in the local search phase, an RVND (Randomized Variable Neighborhood Descent) algorithm. As a strategy to improve the quality of the proposed approach, an algorithm based on an Integer Linear Programming model that combines routes from different solutions is used.
Keywords: Roteamento de veículos
Drones
Metaheurística
MIP
Vehicle routing problem
Metaheuristics
CNPq: Ciências Exatas e da Terra.
Language: por
Country: Brasil
Publisher: Universidade Federal de Juiz de Fora (UFJF)
Institution Initials: UFJF
Department: Faculdade de Engenharia
Access Type: Acesso Aberto
Attribution-ShareAlike 3.0 Brazil
Creative Commons License: http://creativecommons.org/licenses/by-sa/3.0/br/
URI: https://repositorio.ufjf.br/jspui/handle/ufjf/15931
Issue Date: 17-Feb-2022
Appears in Collections:Engenharia Computacional - TCC Graduação



This item is licensed under a Creative Commons License Creative Commons