Efficient DPSO Neighbourhood for Dynamic Traveling Salesman Problem

This paper introduces a new Discrete Particle Swarm Optimization algorithm for solving Dynamic Traveling Salesman Problem (DTSP). An experimental environment is stochastic and dynamic. Changeability requires quick adaptation ability from the algorithm. The introduced technique presents a set of advantages that fulfill this requirement. The proposed solution is based on the virtual pheromone first applied in Ant Colony Optimization. The pheromone serves as a communication topology and information about the landscape of global discrete space. To improve a time bound, the alpha-measure proposed by Helsgaun's have been used for the neighborhood. Experimental results demonstrate the effectiveness and efficiency of the algorithm.