Insertion ant colony optimization for solving the traveling salesman problem
MetadataShow full item record
Inspired from the ant foraging behavior, the ant colony algorithm has provided a new approach for solving discrete optimization problems--the traveling salesman problem (TSP), for instance, is usually tested as the benchmark. Since the ant colony algorithm was introduced in the 1990's, many refinements have been developed to improve the performance by refining the pheromone updating strategies, which have achieved great success on small- and medium-size of TSP instances. However, refining the pheromone updating strategies only can not further improve the performance of the traditional ant colony algorithms on large scale TSP instances. In this study, a new algorithm, insertion ant colony system (IACS) is proposed in order to overcome drawbacks that traditional ant colony algorithms may encounter while solving large scale TSP instances. By incrementally re-optimizing the initial solution, the IACS performs as well as the LK algorithm on large TSP instances.