The Vehicle Routing Problem with Drones

• Ano de defesa: 2019
• Autor(a) principal: Costa, Joao Guilherme Cavalcanti
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Algoritmo genético híbrido; Drones; Hybrid genetic algorithm; Logística; Logistics; Mixed Iiteger linear programming; Problema do roteamento de veículos; Programação linear Inteira mista; VANTs; Vehicle routing problem
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-091040/

In this Dissertation, the Vehicle Routing Problem with Drones (VRPD), motivated by the growing interest on Unmanned Aerial Vehicles (UAVs, or Drones) by the industry and their applications in logistics is studied. A pioneer work by (MURRAY; CHU, 2015) shows a combination between UAV and a truck to deliver products, presenting an adaptation to the Traveling Salesman Problem (TSP). After a literature review, an extension of the model from Murray and Chu (2015) we present a model for the problem with multiple vehicles. This model is developed as a Mixed Integer Linear Programming (MILP) problem and solved with the solver CPLEX. A heuristic based on a Hybrid Genetic Algorithm (HGA) is also developed and presented. Our results show that the use of drones reduces the total mileage of the trucks by a significant percentage.