Particle Swarm Optimization For K-Shortest Paths Via Designated Points

In the fields of road traffic,network communication,logistics transportation,intelligent navigation and so on,with the advent of shortest path problem,the development of the shortest paths problem via designated points and the K-shortest path problem,the K-shortest paths problem via designated points has been paid more and more attention by scholars.In addition to considering that the path must contain a set of designated points,the user also wants to obtain the second short,secondary short path,and multiple selectable optimal paths that can satisfy the user's needs to the greatest extent.For the K-shortest paths problem via designated points,the problems to be solved are as follows:(1)The initialized path must contain designated points,and the node in the nodes set must have and can only occur once;(2)The swarm intelligence algorithm takes the optimal solution set as the optimization goal;(3)The algorithm is less affected by the network topology size,the number of designated points,and the number of the K-shortest paths.This paper proposes an improved particle swarm optimization algorithm.Firstly,a two-time coding based on natural code is constructed to represent a particle.Starting from the characteristics of increasing initial bird population diversity,a method of elastic stretching of the seed path segment is designed to solve the problem that the path contains a set of designated points.Secondly,using the discrete particle evolution mechanism,an efficient path search process is established through the exchange of information between particles and Pbest and Gbest.Finally,in order to solve the problem of using K-shortest paths as the optimization target,population collaboration and local search and archive archiving strategy are proposed.The idea of population collaboration and local search is to divide the particle group into K subgroups.According to the cooperation between the populations and the local search of the subgroups,the algorithm can obtain the K-shortest paths in each search process.The purpose of archive archiving strategy is to effectively preserve the diversity in particle evolution by creating a file of K-shortest paths collections to ensure that the document can store the K-shortest paths set after each iteration update.On the different topological maps with 26 nodes 65 edges,60 nodes 328 edges and 80 nodes 410 edges,a large number of different source and destination nodes and designated points are selected,and the proposed algorithm is tested and analyzed.Experimental results show that with the increase of the size of the topological map,the number of designated points,and the number of the K-shortest paths,the time consumption of the algorithm remains basically the same magnitude,and the algorithm converges fast and must be solved in the solution.There is a clear advantage in solving the problem of the ring-free the K-shortest paths problem via designated points.