A discrete particle swarm optimization with random selection solution for the shortest path problem

This article proposes a discrete particle swarm optimization (DPSO) for solution of the shortest path problem (SPP). The proposed DPSO adopts a new solution mapping which incorporates a graph decomposition and random selection of priority value. The purpose of this mapping is to reduce the searching space of the particles, leading to a better solution. Detailed descriptions of the new solution and the DPSO algorithm are elaborated. Computational experiments involve an SPP dataset from previous research and road network from Malaysia. The DPSO is compared with a genetic algorithm (GA) using naive and new solution mapping. The results indicate that the proposed DPSO is highly competitive and shows good performance in both fitness value and processing time.