关键词: [k]条最优路径, 必经点, 粒子群优化算法

Abstract: A particle swarm optimization algorithm is proposed to solve the problem of the [k]-shortest paths via designated points. The [k]-shortest path set is taken as the optimization objective. The particle population is divided into [k] subpopulations, and through the local search of each subpopulation and the collaboration among subpopulations, it is easy for the population to find [k]-shortest paths in the search process. In order to enhance the diversity of the initial path with designated points, a population initialization method based on elastic stretching principle is designed. In the topological graph of randomly generated 26 nodes with 65 edges, 50 nodes with 262 edges and 80 nodes with 410 edges, different source node and destination node and designated points are selected for testing. The experimental results show that the proposed algorithm has better performance in solving the problem of the ring-free [k]-shortest paths with larger network size and more designated points.

Key words: [k]-shortest paths, designated points, particle swarm optimization