面向城市交通网络的 K 最短路径集合算法

在城市交通网络中，为了优化交通流，需要搜索到符合出行需求 K 最短路径，并 将 OD（Origin-Destination）交通流合理分配到这些路径上.本文主要对搜索符合出行需 求的 K 最短路径搜索算法进行了研究，解决了已有算法仅能搜索出单条满足最短及 K 最 短条件路径的问题.根据 Wardrop 第二原则及路段阻抗函数理论，分析了路径集合搜索方 法对优化城市交通流的必要性，并定义了城市交通网络中 K 最短路径集合的概念及选择 条件，提出了一种面向城市交通网络的具有多项式时间复杂度的 K 最短路径集合搜索算 法.仿真结果表明，本文所提算法可以搜索出满足出行需求的所有 K 最短路径集合，在该 路径集合上进行交通流分配的效果明显优于传统方法.

A K-th Shortest Path Set Algorithm for Urban Traffic Network

In urban traffic network，it is important to optimize traffic flow of the K- th shortest path that meets the travel demand and then allocate the OD traffic flow onto the paths. This paper investigates the algo- rithm of searching K-th shortest path that meets the travel demand. The method overcomes the weakness of the traditional algorithm that can only get single K-th shortest path. According to the second principle of War- drop and the road impedance function theory, the paper analyzes the necessity of the path set searching meth- od for optimizing traffic flow, and proposes the definition and criterions of the K-th shortest path set in urban traffic network. Then, it presents an algorithm with the polynomial time complexity for searching K-th short- est path set in urban traffic network. The simulation results show that all of the K-th shortest path which meet the travel demand can be obtained effectively, and the feasibility of traffic allocation on above path set is proved with comparison of traditional algorithms.