Skip to content
Open access

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

2026 · IEEE Access · Vol 14, pp. 144912-144928 · 0 citations · 44 references
Computer Science

TL;DR

This work proposes 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, and introduces novel operators including event-proximity string removal and coverage-aware greedy insertions.

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.

Read PDF

Similar papers

2026

Safety-Aware Multi-Robot Scheduling Under Time-Critical Constraints: A Colored Traveling Salesman Problem Approach

The Colored Traveling Salesman Problem (CTSP) is a seminal generalization of the Multiple TSP, where colors represent the heterogeneity of salesmen and their city visits. This work presents a time-critical extension, termed the Time-Critical CTSP (T-CTSP). By emphasizing the timing of visits, T-CTSP explicitly captures...

Y. Duan, Jun Li · 0 citations
Open access Sep 2026

Obstacle-Aware Multi-Target Routing for Campus Logistics Using an Improved Mayfly Optimization Algorithm

An obstacle-aware routing framework that combines a 1 m occupancy grid, A* shortest-path computation, and an Improved Mayfly Optimization Algorithm (IMOA) is developed, establishing routing-efficiency gains under the evaluated protocol.

Ze Yang, Xin-Ying Cheng, Hao-Min Wang · 0 citations
Conference Aug 2026

An Integration of Multiple Heuristics for Multi-Depot Multiple Traveling Salesman Problems

This paper addresses the multi-depot multiple traveling salesman problem (MDMTSP), a complex combinatorial optimization problem with significant real-world applications in logistics and transportation. A permutation-based representation is proposed to encode candidate solutions, where salesman routes are generated by p...

Kallol Bera, Somnath Mukhopadhay, M. Maiti · 0 citations
Open access Sep 2026

Pointer Amplifier for Vehicle Routing Problem: Solving Time-Constrained Vehicle Routing Problems with Finite Fleet Using End-to-End Neural Combinatorial Optimization

An NCO solution method for a time-constrained capacitated VRP with finite vehicle fleet is presented, providing competitive cost-efficient solutions while exhibiting robustness and generalization, compared with state-of-the-art heuristics.

E. Deineko, Carina Kehrt · 0 citations
Open access 2026

From Feasibility to Multi-Criteria Optimization in Service Team Transport Scheduling: A Declarative and Metaheuristic Perspective

The scalability of a multi-criteria optimization for the Service Team Transport Scheduling (STTS) problem is investigated, minimizing total travel time, maximum vehicle worktime, and total vehicle engagement time to define scale-aware algorithmic boundaries essential for real-time decision support systems.

Jarosław Rudy, G. Radzki · 0 citations
Aug 2026

A novel ant colony system for vehicle routing problem with time windows: leveraging multiple heuristic strategies for improved solutions

This paper introduces an advanced ant colony system approach that seamlessly integrates four heuristic techniques, and incorporates a no-improvement counter into the algorithm for solution selection to counter stagnation and enhance solution diversity.

Yiğit Çağatay Kuyu, Jenny Fajardo-Calderin, Enrique Onieva · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.