Open Access

ARTICLE

A Scheme Library-Based Ant Colony Optimization with 2-Opt Local Search for Dynamic Traveling Salesman Problem

Chuan Wang^1,*, Ruoyu Zhu², Yi Jiang³, Weili Liu⁴, Sang-Woon Jeon⁵, Lin Sun², Hua Wang⁶

1 College of Software, Henan Normal University, Xinxiang, 453007, China
2 College of Computer and Information Engineering, Henan Normal University, Xinxiang, 453007, China
3 School of Computer Science and Engineering, South China University of Technology, Guangzhou, 510006, China
4 School of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, 510665, China
5 Department of Military Information Engineering, Hanyang University, Ansan, 15588, South Korea
6 College of Engineering and Science, Institute for Sustainable Industries and Liveable Cities, Victoria University, Melbourne, VIC 8001, Australia

* Corresponding Author: Chuan Wang. Email:

(This article belongs to the Special Issue: Swarm Intelligence and Applications in Combinatorial Optimization)

Computer Modeling in Engineering & Sciences 2023, 135(2), 1209-1228. https://doi.org/10.32604/cmes.2022.022807

Received 27 March 2022; Accepted 06 June 2022; Issue published 27 October 2022

Abstract

The dynamic traveling salesman problem (DTSP) is significant in logistics distribution in real-world applications in smart cities, but it is uncertain and difficult to solve. This paper proposes a scheme library-based ant colony optimization (ACO) with a two-optimization (2-opt) strategy to solve the DTSP efficiently. The work is novel and contributes to three aspects: problem model, optimization framework, and algorithm design. Firstly, in the problem model, traditional DTSP models often consider the change of travel distance between two nodes over time, while this paper focuses on a special DTSP model in that the node locations change dynamically over time. Secondly, in the optimization framework, the ACO algorithm is carried out in an offline optimization and online application framework to efficiently reuse the historical information to help fast respond to the dynamic environment. The framework of offline optimization and online application is proposed due to the fact that the environmental change in DTSP is caused by the change of node location, and therefore the new environment is somehow similar to certain previous environments. This way, in the offline optimization, the solutions for possible environmental changes are optimized in advance, and are stored in a mode scheme library. In the online application, when an environmental change is detected, the candidate solutions stored in the mode scheme library are reused via ACO to improve search efficiency and reduce computational complexity. Thirdly, in the algorithm design, the ACO cooperates with the 2-opt strategy to enhance search efficiency. To evaluate the performance of ACO with 2-opt, we design two challenging DTSP cases with up to 200 and 1379 nodes and compare them with other ACO and genetic algorithms. The experimental results show that ACO with 2-opt can solve the DTSPs effectively.

---

Keywords

---