Adjustability of a discrete particle swarm optimization for the dynamic TSP

Abstract

This paper presents a detailed study of the discrete particle swarm optimization algorithm (DPSO) applied to solve the dynamic traveling salesman problem which has many practical applications in planning, logistics and chip manufacturing. The dynamic version is especially important in practical applications in which new circumstances, e.g., a traffic jam or a machine failure, could force changes to the problem specification. The DPSO algorithm was enriched with a pheromone memory which is used to guide the search process similarly to the ant colony optimization algorithm. The paper extends our previous work on the DPSO algorithm in various ways. Firstly, the performance of the algorithm is thoroughly tested on a set of newly generated DTSP instances which differ in the number and the size of the changes. Secondly, the impact of the pheromone memory on the convergence of the DPSO is investigated and compared with the version without a pheromone memory. Moreover, the results are compared with two ant colony optimization algorithms, namely the (Formula presented.)–(Formula presented.) ant system (MMAS) and the population-based ant colony optimization (PACO). The results show that the DPSO is able to find high-quality solutions to the DTSP and its performance is competitive with the performance of the MMAS and the PACO algorithms. Moreover, the pheromone memory has a positive impact on the convergence of the algorithm, especially in the face of dynamic changes to the problem’s definition.