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

DOI10.1016/J.COSREV.2021.100369zbMATH Open1487.90545arXiv2102.12772OpenAlexW3130706049MaRDI QIDQ826328FDOQ826328

Authors: Omar Cheikhrouhou, Ines Khoufi 

Publication date: 20 December 2021

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

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.

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

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

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)

Cites Work

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

Cited In (10)

• 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
• 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)