Computation and Simulation Analysis of a Kind of Multiple Traveling Salesman problem

Traveling salesman problem is one of the classical problems in Combinatorial Optimization, and the multiple traveling salesman problem(MTSP) is a generalization of the well-known traveling salesman problem(TSP), where more than one salesman is allowed to be used in the solution.Moreover, the characteristics of the MTSP seem more appropriate for real-life applications, and it is also possible to extend the problem to a wide variety of vehicle routing problems(VRPs) by incorporating some additional side constraints.Although there exists a wide body of the literature for the TSP and the VRP, the MTSP has not received the same amount of attention.A special case of multiple traveling salesman problem was calculated by adopting Lin-Kernighan algorithm, then a two stage procedure was applied in order to make sure that the number of cities each traveling salesman visited are the same and the total tour length is minimized.The calculation and simulation results are satisfactory.