Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone.

This article focuses on developing an exact algorithm to solve the basic Traveling Salesman Problem with a Drone (TSP-D), a routing problem where a truck and a drone cooperate to deliver parcels to customers with synchronized routes. The authors introduce a stronger notion of ng-feasibility and enhanced dominance rules within a dynamic programming labeling algorithm that employs bidirectional search, enabling the solution of benchmark instances with up to 59 customers and scaling to 99 customers when the drone is significantly faster than the truck. The proposed solver, called Price-Fix-and-Augment (PFA), integrates decremental state-space relaxation strategies, variable fixing methods based on completion bounds, tailored column generation, and neighborhood augmentation to efficiently compute tight lower bounds and optimal routes. Computational experiments demonstrate that PFA outperforms previous exact methods, solving all instances with 59 customers and many with up to 99 customers, while maintaining balanced computational effort across its components. The algorithm is flexible and can incorporate additional operational constraints discussed in prior literature without significant modifications.