A novel hybrid approach for solving the multiple traveling salesmen problem

Abstract The multiple Travelling Salesmen Problem (mTSP) is one of the most popular and important operational research problems. It is a problem where n salesmen have to visit m cities such that each salesman has to visit at least one city and all the cities should be visited exactly once, starting and ending at one specific city. In this paper a new hybrid approach called AC2OptGA is proposed to solve the mTSP. AC2OptGA is a combination of three algorithms: Modified Ant Colony, 2-Opt, and Genetic Algorithm. Ant Colony-based algorithm is used to generate solutions on which the 2-Opt edge exchange algorithm is applied to enhance the obtained solutions. A Genetic Algorithm is then used to again improve the quality of the solutions. The reason behind combining the above-mentioned algorithms is to exploit their strengths in both global and local searches. The proposed approach is evaluated using various data instances from standard benchmarks. Using the TSPLIB benchmarks for large-sized instances, AC2OptGA shows better results than M-GELS, the current best known approach. For medium and small-sized data instances, AC2OptGA shows better results than other approaches and comparable results to M-GELS. Using the MTSP benchmarks (MTSP-51, MTSP-100 and MTSP-150), AC2OptGA outperforms other methods for number of salesmen less than 10 and is competitive with NMACO (BKS) for 10 salesmen