Source-linked AI summary
A Comprehensive Survey on the Multiple Travelling Salesman Problem: Applications, Approaches and Taxonomy
Omar Cheikhrouhou, Ines Khoufi
TL;DR
MTSP is important across real-life applications, yet recent MTSP contributions lacked a dedicated survey. This paper reviews recent work across classical and flying vehicles, analyzes variants and solution approaches, and proposes a taxonomy and classification; it also identifies scope and scalability boundaries in existing solutions.
Problem
Despite MTSP's importance, the paper identifies a lack of dedicated analysis of recent MTSP contributions.
Method
The paper conducts a comprehensive survey of MTSP applications, variants, solution approaches, and recent studies involving ground and flying vehicles.
Results
The survey reviews recent contributions and proposes a taxonomy and classification of MTSP studies.
Takeaways & Limitations
The survey organizes MTSP research across applications, variants, and approaches for classical vehicles, robots, and UAVs.
Takeaways & Limitations
Exact approaches provide optimal solutions but are useful only for very small instances because MTSP is NP-hard, while execution time becomes very long as the problem scales.
Abstract
from arXiv · showhide
The Multiple Travelling Salesman Problem (MTSP) is among the most interesting combinatorial optimization problems because it is widely adopted in real-life applications, including robotics, transportation, networking, etc. Although the importance of this optimization problem, there is no survey dedicated to reviewing recent MTSP contributions. In this paper, we aim to fill this gap by providing a comprehensive review of existing studies on MTSP. In this survey, we focus on MTSP's recent contributions to both classical vehicles/robots and unmanned aerial vehicles. We highlight the approaches applied to solve the MTSP as well as its application domains. We analyze the MTSP variants and propose a taxonomy and a classification of recent studies.
1. Introduction and Motivation
MTSP is a widely used optimization problem spanning ground and flying vehicles, but recent MTSP-specific research lacked a dedicated survey. This paper addresses that gap by reviewing applications, variants, solution approaches, and recent studies.
- MTSP generalizes the Traveling Salesman Problem and is related to Vehicle Routing and Task Assignment problems.
- Applications represent salesmen as ground robots, vehicles, or trucks, and as UAVs or drones serving customers, sensor nodes, targets, victims, or critical sites.
- Earlier surveys covered vehicle routing, TSP, robotic routing, evolutionary multi-objective TSP, or UAV optimization, but MTSP was not their central subject.
- The survey fills the gap by reviewing recent MTSP and variant contributions, including uses of MTSP for real-life optimization problems.
- Its contributions include applications, formal analysis of variants, reviews of ground and flying vehicle studies, and classification by application area and solution approach.
- The paper proposes a taxonomy and classification of recent MTSP studies intended to support research and indicate future directions.
2. MTSP Application Fields
MTSP is applied across transportation, networking, search and rescue, agriculture, disaster management, surveillance, and multi-robot cooperation. These applications use ground vehicles, robots, and UAVs whose routes must reflect operational objectives and constraints.
- Transportation and Delivery: Transportation applications optimize routes for goods, parcels, or people while considering vehicle capacity and time constraints.
- Transportation and Delivery: Truck–drone delivery systems combine vehicle types to reduce delivery time, with trucks carrying valuable goods and drones delivering small parcels quickly.
- WSN Data Collection and Network Connectivity: Mobile robots can collect wireless-sensor data as mobile sinks, reducing energy dissipation near fixed sinks and increasing network lifetime.
- Search and Rescue: Search-and-rescue applications determine locations to visit and optimize routes, using UAVs to support time-critical operations.
- Precision agriculture: Precision agriculture uses ground robots and UAVs for crop monitoring and irrigation management, requiring optimized paths to reduce costs and improve production.
- Disaster management: Disaster-management systems model optimized rescue plans as MTSP problems, while cooperative missions coordinate routes and collision avoidance across vehicles.
3. MTSP Definition and Variants
MTSP assigns multiple salesmen, vehicles, or robots to collectively visit targets while optimizing route costs under varied structural and operational conditions. The survey organizes variants by depots, paths, cooperation, objectives, vehicle characteristics, and constraints, and distinguishes ground-vehicle and UAV classes.
- Definition: The standard MTSP minimizes the total cost of multiple depot-to-depot routes while each city is visited exactly once by one salesman.
- Variant taxonomy: The survey extends prior MTSP variants and provides an analysis of more metrics based on recent contributions.
- Structural variants: Variants distinguish cooperative salesmen, single or multiple depots, fixed or mobile depots, closed or open paths, and optional refueling points.
- Assignment and objectives: Colored MTSP separates cities shared by all salesmen from cities assigned to specific salesmen, while objectives may be single or multi-objective.
- Objectives: Common objectives include minimizing total tour cost, the maximum tour cost, mission time, energy consumption, salesman count, and refueling cost.
- Constraints: Vehicle-specific constraints include limited UAV energy and carrying capacity, time windows, and data latency, which restrict feasible tours.
- Objective formulations: MinSum minimizes the sum of robots’ tour costs, whereas MinMax minimizes the longest tour cost and is associated with mission-completion time.
- Problem classes: The survey divides MTSP studies into ground-vehicle problems and UAV problems, reflecting UAV energy and carrying-capacity characteristics.
4. MTSP Approaches
The survey reviews approaches for solving MTSP separately for ground vehicles and flying vehicles. It presents this separation as a way to account for vehicle-specific issues and guide approach selection.
- Approach taxonomy: Most approaches for flying vehicles extend approaches originally applied to ground vehicles.
- Scope: The survey analyzes MTSP solution approaches for ground vehicles, including salesmen and robots, separately from approaches for flying vehicles.
- Purpose: The separate treatment is intended to clarify the issues associated with each vehicle type and support selection of an appropriate optimization approach.
- Approach taxonomy: The reviewed approaches are organized in the MTSP approaches taxonomy shown in Figure 3.
4.1. MTSP for Ground Vehicles and Robots
The reviewed ground-vehicle and robot MTSP studies are organized by optimization approach, spanning exact, genetic, swarm, ant-colony, and other methods. Exact approaches can reach optimal solutions but are time-consuming, while meta-heuristic studies explore representations, operators, and multi-objective formulations.
- Deterministic approaches: Exact methods are computationally expensive and are therefore adopted in only a few studies.Constraint programming required more than 2 hours for an instance with 51 cities and 3 salesmen.
- Meta-heuristic based approaches: Sequential constructive crossover outperformed CX, PMX, OX, ERX, AEX, and SCX alternatives on TSPLIB benchmark instances.Another proposed crossover method optimized both total distance traveled and maximum tour length.
- Meta-heuristic based approaches: Partheno-genetic approaches were extended with reproduction mechanisms to address the lack of local information and avoid local convergence.The resulting RIPGA was compared with GA solutions, while IPGA outperformed PSO in the cited benchmark study.
- Meta-heuristic based approaches: Multi-objective MTSP studies optimize objectives such as total distance, travel-time balance, mission time, robot count, and tour-time balance.NSGA-II computes a set of non-dominated solutions for distance minimization and balancing traveling times.
- Other approaches: Ant-colony, swarm, market-based, and hybrid approaches are also reviewed for ground vehicles and robots.The reviewed results include Multiple ACS outperforming classical ACS and a Webots solution reported as efficient in scalability, path length, and communication overhead.
4.2. MTSP for UAVs
UAV-focused MTSP research addresses delivery, communication, task assignment, surveillance, and cooperative missions under vehicle-specific constraints. The reviewed solutions combine exact formulations, constraint programming, clustering, genetic methods, and multi-stage heuristics to manage these settings.
- Overview: The survey classifies recent UAV MTSP solutions by optimization approach and highlights their application areas.The reviewed UAV context includes delivery, communication, task assignment, and cooperative mission settings.
- Transport and delivery: Truck-and-drone delivery variants minimize the vehicles’ arrival time at the depot after all parcels are delivered.One formulation uses mixed integer programming solved with IBM-CPLEX.
- Transport and delivery: Exact optimization is practical only for small instances, whereas heuristics are used for medium and large delivery instances.A three-phase heuristic produced high-quality solutions with reasonable execution time for realistic-size problems.
- Transport and delivery: Other delivery models incorporate multiple depots, trucks, drones, time windows, drop-pickup synchronization, and multi-visit constraints.Constraint programming is used to minimize the maximum time required to satisfy parcel delivery.
- Task assignment and cooperative missions: UAV task-assignment and trajectory-planning formulations incorporate dynamics, threat avoidance, collision avoidance, and uncertain parameters.Proposed methods include ATSP transformations, LKH search, digraph-based deadlock-free planning, and modified Two-Part Wolf Pack Search.
- Heuristic approaches: GA-ADI reached optimal solutions on small instances and solved MTSPD significantly faster than IBM-CPLEX, while GA-ADI was used for large instances.The study also reported efficiency from combining multiple techniques in the heuristic.
- Communication networks: UAV communication studies use genetic algorithms to plan message-ferry tours or clustered UAV routes that reduce delivery delay.A related optimization problem produced solutions comparable to exhaustive search in shorter runtime and outperformed traditional MTSP on message delivery delay.
5. Taxonomy, Classification and Analysis
The survey’s taxonomy classifies MTSP studies by variants, optimization approaches, and application fields, then analyzes the reviewed literature across these dimensions. Ground-vehicle studies dominate the sample, while UAV solutions are newer, more constrained, and more application-diverse.
- Taxonomy and classification: The proposed taxonomy uses three criteria: MTSP variants, solution approaches, and application fields.The classification is intended to help readers select a suitable MTSP variant and solution approach for an application.
- Statistical analysis: 71% of the reviewed MTSP studies concern ground vehicles, compared with 29% concerning flying vehicles.The survey attributes this distribution partly to the earlier publication history of ground-vehicle research.
- Statistical analysis: 36% of papers used genetic algorithms, while exact and ACO approaches each appeared in 18% and market-based approaches in 11%.GA was the most used approach across both vehicle types.
- Vehicle-specific variants: Ground-vehicle studies mostly use multiple depots, whereas UAV studies mostly use a single depot.The survey connects depot choice to application domain and vehicle type.
- Vehicle-specific variants: UAV studies more often treat energy and time windows as constraints, while ground-vehicle studies more often treat energy as an objective.UAV multi-objective MTSP is rarely considered, and mission-time minimization is the most common UAV objective.
- Approaches and applications: UAV solutions are more complex because they combine approaches to handle energy, carrying capacity, truck coordination, and application requirements.Many studies decompose the optimization into several stages to reduce problem complexity.
- Application fields: Ground-vehicle papers often address general contexts, whereas UAV studies cover a wider diversity of application areas.Ground-vehicle examples include multi-robot task allocation, while UAV applications span several domains listed in the classification.
6. Discussion and Future Directions
The survey reviews MTSP applications, variants, and solution approaches across ground vehicles, robots, and UAVs, while identifying modeling constraints and directions for more realistic applications.
- Applications and variants: MTSP studies span ground vehicles, robots, trucks, and UAVs, with some heterogeneous systems combining trucks and UAVs.Applications include parcel delivery, data collection, monitoring, and surveillance, which motivate new MTSP variants.
- Applications and variants: Vehicle capacity, energy consumption, and time windows are additional constraints considered in MTSP formulations.The survey restricts its review to studies formulated as MTSP, even when such constraints make the problem similar to VRP.
- Solution approaches: Exact approaches provide optimal solutions but are useful only for very small instances because MTSP is NP-hard.Heuristics and meta-heuristics are therefore extensively explored for larger problems.
- Solution approaches: Genetic algorithms are the most widely used meta-heuristic, while recent studies show a tendency toward ant colony optimization.Hybrid methods combine meta-heuristics with local search or clustering to reduce computation complexity and convergence time.
- Solution approaches: Market-based approaches can handle dynamic system changes without requiring prior knowledge of all system states.This makes them distinct from approaches that assume a fully known system state.
- Modeling limitations and future directions: Many studies relax vehicle characteristics and constraints, while only a few UAV contributions include them or collision avoidance.The survey calls for greater attention to endurance, kinematics, system dynamics, safety, and energy-consumption models in future MTSP research.
7. Conclusion
MTSP is widely used to formulate real-life optimization problems, but the survey addresses a lack of comprehensive reviews by organizing recent work across vehicle classes, approaches, variants, and applications.
- Scope and motivation: MTSP formulates real-life optimization problems in transportation and delivery, data collection, search and rescue, and multi-robot task allocation and scheduling.Its applications span several fields rather than a single operational setting.
- Scope and motivation: Despite MTSP’s importance, the literature lacked a survey describing existing solutions.The paper positions its review as addressing this gap.
- Taxonomy and classification: The survey divides existing solutions into MTSP for vehicles and robots and MTSP for UAVs or drones.This classification reflects the two broad classes used in the paper.
- Taxonomy and classification: Solutions are classified by optimization approach, including exact, meta-heuristic, and market-based methods.The survey also proposes a taxonomy based on MTSP variants, approaches, and applications.
- Future outlook: MTSP remains a promising research field, especially for UAV-based applications where new optimization problems are emerging.The conclusion identifies UAV applications as a particularly active direction.