A new approach for solving large traveling salesman problem
Cheng-Fa Tsai, Chun‐Wei Tsai, Ching‐Chang Tseng · 2003
This paper presents a novel metaheuristic approach called ACOMAC algorithm for solving the TSP (traveling salesman problem). It introduces the multiple ant clans concept from parallel genetic algorithms to search a solution space that uses different islands to avoid local minima and so as to obtain a global minimum for solving the traveling salesman problem. In addition, the paper presents two methods called multiple nearest neighbor (NN) and dual nearest neighbor (DNN) to ACOMAC to improve large TSPs thus obtaining good solutions quickly. According to our simulation results, the ACOMAC outperforms the ant colony system (ACS) in average length comparison of the traveling salesman problem. In this work, it is observed that ACOMAC or ACS adding DNN or NN approach as initial solutions can provide a significant improvement for obtaining a global optimum solution or a near global optimum solution in large TSPs.