https://repositorio.ufjf.br/jspui/handle/ufjf/15931
File | Description | Size | Format | |
---|---|---|---|---|
eugeniobelizarioribeirofaria.pdf | PDF/A | 893.62 kB | Adobe PDF | 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