An Adaptive Large Neighborhood Search for the Multiple Traveling Salesman Problem With Backup Coverage

Abstract

The Multiple Traveling Salesman Problem with Backup Coverage (mTSP-BC) is a vehicle routing variant in which all vehicles must remain within a maximum pairwise distance at every instant during their traversal, imposing spatiotemporal interdependence among routes. This constraint models real-world scenarios such as military convoy coordination, collaborative drone missions, and emergency response fleet management, where mutual support between vehicles is critical. We present a mixed-integer programming (MIP) formulation for the mTSP-BC and document the computational limits of solving it with a state-of-the-art solver. To overcome these limits, we propose an Adaptive Large Neighborhood Search (ALNS) metaheuristic with a hybrid C++/Python architecture, featuring problem-specific destroy and repair operators designed to handle the backup coverage constraint. We introduce novel operators including event-proximity string removal and coverage-aware greedy insertions. The algorithm employs a multi-phase search strategy comprising constructive initialization via convex hull insertion, a feasibility-seeking phase, and iterated cost optimization. Computational experiments on benchmark instances show that the MIP formulation, solved by Gurobi, is limited to instances with at most 16 nodes, while the ALNS finds solutions of comparable quality on those instances and scales to instances with up to 99 nodes and 7 vehicles within practical time limits.