A Step Backward is a Leap Forward: Solving the CVTSP Based on Near-Optimal TSP Routes

Abstract

The carrier-vehicle traveling salesman problem (CVTSP) involves two types of heterogeneous vehicles, i.e., the carrier and a vehicle, operating cooperatively in a continuous space, where the vehicle may take off from and land on the carrier. Given a set of target points, the CVTSP seeks to determine both the visiting sequence of the targets and the corresponding takeoff and landing locations, with the objective of minimizing the total travel time. The problem is widely recognized in the truck-and-drone delivery and mothership-and-drone routing scenarios. In this letter, we prove that the optimal sequence of the CVTSP lies within a set of sequences whose traveling salesman problem (TSP) costs are within a fixed range, i.e., $\Delta$, of the optimal TSP cost. Based on this insight, the proposed solution pool search strategy explores the near-optimal neighborhood more efficiently. Extensive experiments on benchmark datasets demonstrate that our method consistently finds optimal or near-optimal solutions for all small to medium-scale instances and identifies new best-known solutions for large-scale cases.