Particle Swarm Optimization Combined with Local Search and Velocity Re-Initialization for Shortest Path Computation in Networks

This paper presents the application of particle swarm optimization (PSO) based search algorithm for solving the single source shortest path problem (SPP) commonly encountered in graph theory. A new particle encoding/decoding scheme has been devised for representing the SPP parameters as a particle. In order to enhance the search capability of PSO, a selective local search mechanism and periodic velocity re-initialization of particles have been incorporated. Simulation results on several networks with random topologies are used to illustrate the efficiency of the proposed hybrid PSO algorithm for computation of shortest paths in networks