The use of unmanned aerial vehicles (UAVs), or drones, in conjunction with drone-launching trucks/vans for customer deliveries is currently being explored by numerous corporations. We study the vehicle routing problem with flexible drones, where the drones are not dedicated to certain vehicles. Rather, they can switch between vehicles in order to further increase the parallelization of delivery operations. We demonstrate the performance improvements provided by this flexibility compared to the more widely studied variant of this problem, where the drones must come back to the vehicle they were launched from.

We model this problem using a time-expanded network, and provide optimal solutions for benchmark problem instances adapted from the traveling salesman problem with drone (TSPD) literature, as well as larger problem instances. To solve large problem instances, for which solving the fully time-expanded network MIP is impractical, we present a dynamic discretization discovery (DDD) algorithm (Boland et al. 2017), which iteratively refines the time-expanded network via computing lower and upper bounds. This way, the optimal solution is found without generating the fully time-expanded network, by only solving a series of much smaller MIPs compared to the fully time-expanded network MIP. We present an extensive computational study that demonstrates (i) the benefits provided by using drones in commercial delivery settings, (ii) makespan improvements obtained by flexible, rather than dedicated, drones, (iii) the solution performance of DDD in comparison to commercial solver(s), and (iv) the practical performance of DDD when stopped after a time/iteration limit, rather than proof of optimality.