Ant Colony Optimization with Neighborhood Search for Dynamic TSP
Ant Colony Optimization with Neighborhood Search for Dynamic TSP
复制标题
DOI：
10.1007/978-3-319-41000-5_43
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Yirui Wang;Zhe Xu;Jian Sun-;Fang Han;Yuki Todo;Shangce Gao
中科院分区：
文献类型：
--
作者：
Yirui Wang;Zhe Xu;Jian Sun-;Fang Han;Yuki Todo;Shangce Gao
Ant colony optimization (ACO) is one of the best heuristic algorithms for combinatorial optimization problems. Due to its distinctive search mechanism, ACO can perform successfully on the static traveling salesman problem(TSP). Nevertheless, ACO has some trouble in solving the dynamic TSP (DTSP) since the pheromone of the previous optimal trail attracts ants to follow even if the environment changes. Therefore, the quality of the solution is much inferior to that of the static TSP’s solution. In this paper, ant colony algorithm with neighborhood search called NS-ACO is proposed to handle the DTSP composed by random traffic factors. ACO utilizes the short-term memory to increase the diversity of solutions and three moving operations containing swap, insertion and 2-opt optimize the solutions found by ants. The experiments are carried out to evaluate the performance of NS-ACO comparing with the conventional ACS and the ACO with random immigrants (RIACO) on the DTSPs of different scales. The experimental results demonstrate our proposed algorithm outperforms the other algorithms and is a competitive and promising approach to DTSP.
