Complexity analysis of the Line-TSP with Drone Transports

Abstract

Since last-mile distribution processes in urban areas are rapidly expanding, several novel delivery concepts have been proposed in recent years to improve their efficiency. Among these innovative concepts, the integration of unmanned aerial vehicles (drones) plays a prominent role, as they can enable simultaneous deliveries. However, due to limited experience and complexity avoidance, the first experimental real-world applications of combined drone and truck transports in urban areas should be kept simple by limiting them to transports along a single road. To provide a first basic model for these processes whose computational complexity is analyzed in detail, this paper introduces the Traveling Salesman Problem on the Line with Drone Transports (Line-TSPwD). It extends the well-known Line-TSP by a versatile integration of drone transports. After starting together from a given position, neither the truck's nor the drone's route is given, but must be generated such that all customers are served and that the drone returns to the truck after each drone delivery. The Line-TSPwD minimizes the time when the truck and the drone meet after all customers have been served. The Line-TSPwD distinguishes between the continuous case, where the truck and the drone can meet at any line position, and the discrete case, where these meeting points are limited to the predetermined customer locations. A further distinction is made by assuming either a faster truck or a faster drone, while the service at customer locations can be constrained by time windows that define deadlines and/or release dates. This study provides significant new results that resolve the complexity status of different variants of the new Line-TSPwD. In addition, known results from the literature are significantly strengthened.