Algorithms for Solving the Vehicle Routing Problem with Drones

The Vehicle Routing Problem (VRP) and its variants are well-studied problems in Operations Research. They are related to many real-world applications. Recently, several companies like Amazon, UPS, and Deutsche Post AG showed interest in the integration of autonomous drones in delivery of parcels. This motivates researchers to extend the classical VRP to the Vehicle Routing Problem with Drones (VRPD), where a drone works in tandem with a vehicle to reduce delivery times. In this paper, we focus on solving the VRPD. In particular, we introduce two heuristic algorithms for solving this problem and, through numerical experiments on large-scale instances, we evaluate the performance of the heuristics and show the potential benefit that can be expected when using drones.