A comprehensive survey on the multiple traveling salesman problem: applications, approaches and taxonomy

DOI10.1016/J.COSREV.2021.100369MaRDI QIDQ826328zbMATH OpenOpenAlexFDO

Authors Omar Cheikhrouhou, Ines Khoufi

Publication date 20 December 2021

Published in Computer Science Review (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.12772

zbMATH Keywords

MTSProbotstaxonomymultiple traveling salesman problemUAVsapproachesMTSP applicationsMTSP variants

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Abstract: 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.

Recommendations

• A comparative study of task assignment and path planning methods for multi-UGV missions
• Vehicle routing problems with multiple trips
• A new approach to solving the multiple traveling salesperson problem using genetic algorithms
• Vehicle routing problems with multiple trips
• A new heuristic algorithm for multiple traveling Salesman problem

Cites work

• A Survey of the Generalized Assignment Problem and Its Applications
• A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms
• Evolutionary Multi-Criterion Optimization
• Rich vehicle routing problems: from a taxonomy to a definition
• Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem
• The analytic hierarchy process—what it is and how it is used

Cited in

(11)

• A comprehensive survey on the generalized traveling salesman problem
• Memetic search for the minmax multiple traveling salesman problem with single and multiple depots
• Hybrid search with neighborhood reduction for the multiple traveling salesman problem
• Routing problems with electric and autonomous vehicles: review and potential for future research
• An effective iterated two-stage heuristic algorithm for the multiple traveling salesmen problem
• The dynamic stochastic container drayage problem with truck appointment scheduling
• Solving the multiple traveling salesperson problem on regular grids in linear time
• A comparative study of task assignment and path planning methods for multi-UGV missions
• CGKOA: an enhanced Kepler optimization algorithm for multi-domain optimization problems
• Research on improved ant colony optimization for traveling salesman problem
• MILP models of a patient transportation problem

This page was built for publication: A comprehensive survey on the multiple traveling salesman problem: applications, approaches and taxonomy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q826328)