Two-Indexed Formulation of the Traveling Salesman Problem With Multiple Drones Performing Sidekicks and Loops

Kurzfassung/Abstract

Aerial drone delivery has great potential to improve delivery time in package delivery, as drones can fly autonomously over obstacles at a possibly higher speed than trucks. The benefits of drones in delivery can even be increased in a truck-and-drone tandem where a truck carries one or multiple drones and releases them at advantageous places. This problem is known as the traveling salesman problem with multiple drones (TSPmD). We focus on a variant of this problem, where the drones have two options after serving the customer: they can return to a node the truck visits at a later stage (sidekick) or return to the same node they were launched from (loop).

While several variants of the TSPmD have been studied, considering sidekicks and loops in combination with minimizing the makespan is not represented so far. We fill this gap and introduce an efficient two-indexed mixed-integer linear program (MILP) formulation that provides new optimal solutions for instances with up to 28 nodes for benchmark purposes. Our MILP formulation outperforms two state-of-the-art MILP formulations from the literature considering one drone. In a case study, we analyze the impact on the minimization of the makespan when allowing drones to perform loops. Loops mainly become relevant when drones travel faster than trucks resulting in average makespan savings of up to 2.7%.