A new efficient hybrid algorithm for large scale multiple traveling salesman problems

Abstract Multiple traveling salesmen problem (MTSP) is not only a generalization of the traveling salesman problem (TSP), but also more suitable for modeling practical problems in the real life than TSP. For solving the MTSP with multiple depots, the requirement of minimum and maximum number of cities that each salesman should visit, a hybrid algorithm called ant colony-partheno genetic algorithms (AC-PGA) is provided by combining partheno genetic algorithms (PGA) and ant colony algorithms (ACO). The main idea in this paper is to divide the variables into two parts. In detail, it exploits PGA to comprehensively search the best value of the first part variables and then utilizes ACO to accurately determine the second part variables value. For comparative analysis, PGA, improved PGA (IPGA), two-part wolf pack search (TWPS), artificial bee colony (ABC) and invasive weed optimization (IWO) algorithms are adopted to solve MTSP and validated with publicly available TSPLIB benchmarks. The results of comparative experiments show that AC-PGA is sufficiently effective in solving large scale MTSP and has better performance than the existing algorithms.