Dynamic swarm intelligence algorithms with reuse strategy for dynamic traveling salesman problem
Yan Cao, Xiao-Min Hu, Jun Zhang · 2017
Dynamic Traveling salesman problem (DTSP) is a theoretical mathematical model and has been widely applied in dynamic problems in reality. Most of the existing methods used to model DTSP lack a realistic foundation, and cannot provide convenient and polytrophic operations to simulate real-world scenarios. In this paper, a reality-based method is proposed to model DTSP. The model features good controllability and reality by changing the weight of some edges and the nodes needed to be visited at different moments. Besides, for DTSP, some edges are actually added to or deleted from the optimal solution because of environmental changes. A reuse strategy (Rs) is proposed for DTSP so as to excavate the useful information from the historical search experience and reuse them in the new environment to avoid overlapping search. Based on the reuse strategy, the two state-of-the-art optimizers in discrete space, i.e. S-CLPSO and ACS, are extended to SRs-CLPSO and Rs-ACS respectively. By reusing the historical search experience, SRs-CLPSO and Rs-ACS can find a better solution with faster convergence speed. The performance of SRs-CLPSO is compared with Rs-ACS algorithm in fifty instances of TSPLIB. Experimental results indicate that the proposed Rs is efficient for DTSP, and the SRs-CLPSO algorithm is a better solver for DTSP.