Heurísticas para o problema de roteamento de veículos com drones e janelas de tempo.

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.