This paper gives a comprehensive overview of the application, methods and classification of the multi traveling salesman problem

Abstract ：

Multiple traveling salesman problem ( MTSP ) Is one of the most interesting combinatorial optimization problems , Because it is widely used in robots 、 traffic 、 Network and other practical applications . Although the importance of this optimization problem is self-evident , However, there is no special investigation on the near future MTSP Contribution survey . The purpose of this paper is to review the existing MTSP A comprehensive review of the study , Fill this gap . In this survey , We focus on MTSP For classic vehicles in the near future / The contribution of robots and UAVs . The solution is mainly introduced MTSP Method and its application field . We are right. MTSP Variants were analyzed , A taxonomic and recently studied classification is proposed .

1、 Introduction and motivation

Multiple traveling salesman problem （MTSP） It's a famous traveling salesman problem （TSP） Promotion of , Multiple salespeople will visit a given number of cities once , And return to the original location with the minimum travel cost .MTSP Highly relevant to other optimization problems , Such as vehicle routing problem （VRP） And task allocation .（MTSP） Is one of the most important optimization problems , It has been applied to many actual scenarios for a long time . Considering the importance of such optimization problems , We specialize in MTSP The latest contributions of 、 Analysis and discussion . This paper introduces the multi-objective traveling salesman problem （MOTSP） Comparative analysis of evolutionary algorithms . The author only focuses on five evolutionary algorithms , namely NSGA-II、NSGA-III、SPEA-2、MOEA/D and VEGA, To determine the best fit MOTSP The algorithm of the problem . Although several studies have cited MTSP, But only in some chapters , Not the subject of any of the above surveys . in fact ,Bektas[9] Put forward about MSTP The only investigation that can be traced back to 2006 year , The survey reviewed MTSP And Its Applications , Some formulas are emphasized , Some exact heuristic solutions are described . therefore , Lack of specific targeting MTSP Analysis and research of . To fill this gap , This survey is dedicated to reviewing recent contributions , These contributions focus on MTSP And its variants , Or focus on using MTSP Solve the real problem .

Common applications ：

1.  Transportation and delivery . For example, good delivery or package delivery , Or bus transportation . The vehicle is responsible for transporting the goods 、 A package or person is transported from a designated place to another place . In such applications , Vehicle capacity and time constraints shall be considered . Besides , Truck fleets can efficiently transport valuables , The UAV can transport small packages in a very short time .

2. And its parts I do not need to use , I will not translate the introduction in detail

MTSP Definition and variants of

MTSP It's been extensively studied , The original definition was , Given a set of cities 、 A starting point 、m A salesman and a cost function （ Such as time or distance ）,MTSP For the purpose of m A salesman determines a set of routes , send m The total cost of each route is minimized , So that each route starts and ends from the starting point , Each city is visited only once by a salesman .MTSP It has been applied in different application fields , This leads to a new variant of the optimization problem . In this section , We analyzed MTSP Different variants of , Then the main variants are formally described .