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

摘要： 提出了一种解决指定必经点[k]条最优路径问题的粒子群优化算法。算法以[k]条最优路径集合作为优化目标，将粒子种群划分为[k]个子种群，通过各子种群的局部搜索和子种群间的相互协作，使种群在搜索过程中易于找到[k]条最优路径。为了提高含有多必经节点的初始生成路径的多样性，设计了基于弹性拉伸原理的种群初始化方法。在随机生成的26个节点65条边，50个节点262条边和80个节点410条边的拓扑图中，分别选取不同的源节点和目的节点，以及必经节点对算法进行了测试。数值实验结果表明，提出的算法在求解网络规模比较大、必经点数比较多的无环[k]条最优路径问题中具有比较好的性能。

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