An Adaptive Ant Colony Algorithm for Dynamic Traveling Salesman Problem

馬安香(AN-XIANG MA) ； 張曉紅(XIAO-HONG ZHANG) ； 張長勝(CHANG-SHENG ZHANG) ； 張斌(BIN ZHANG) ； 高岩(YAN GAO)

《Journal of Information Science and Engineering》 35卷6期 (2019/11) Pp. 1263-1277

https://doi.org/10.6688/JISE.201911_35(6).0006

摘要

Compared with the traditional static traveling salesman problem, it is more practical to study the dynamic traveling salesman problem in dynamic environment. In this paper, the dynamic optimization problem is considered as a combination of a series of static optimization problems, and an adaptive ant colony algorithm is proposed to solve the dynamic traveling salesman problem. When traveling salesman problem changes, we firstly analyze the environmental changing degree of traveling salesman problem, then an adaptive pheromone initialization mechanism adaptable to changing degree is presented, so as to ensure faster convergence speed without affecting the accuracy of problem solving. In addition, to further improve the quality of solution, we propose an optimization guidance based search mechanism and integrate it into the adaptive ant colony algorithm proposed. Finally, the algorithm is analyzed and compared with the related algorithms on several common real data sets. The results show that the adaptive ant colony algorithm proposed in this paper can solve the dynamic traveling salesman problem more effectively.

關鍵字

ant colony algorithm ； adaptive ant colony algorithm ； dynamic traveling salesman problem ； optimization guidance