A Hybrid Discrete Particle Swarm Optimization with Pheromone 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, based on Benchmark Generator was prepared for testing DTSP solvers. 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. Experimental results demonstrate the effectiveness and efficiency of the algorithm.