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

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

作　　者：段宗涛[1,2] WANG Wei-xing 康军[1,2] 李莹[1] 郑西彬 程豪[1] 刘研[1] 

机构地区：[1]长安大学信息工程学院,西安710064 [2]陕西省道路交通智能检测与装备工程技术研究中心,西安710064 [3]Royal Institute of Technology, Stockholm, Sweden

出　　处：《交通运输系统工程与信息》2014年第3期194-200,共7页Journal of Transportation Systems Engineering and Information Technology

基　　金：国家自然科学基金(51278058,61303041);中央高校科研资金项目(2013G2241020,2013G1241119);交通运输部应用基础研究项目(2014319812150);陕西省科技攻关项目(2014K05-28)

摘　　要：在城市交通网络中,为了优化交通流,需要搜索到符合出行需求K最短路径,并将OD(Origin-Destination)交通流合理分配到这些路径上.本文主要对搜索符合出行需求的K最短路径搜索算法进行了研究,解决了已有算法仅能搜索出单条满足最短及K最短条件路径的问题.根据Wardrop第二原则及路段阻抗函数理论,分析了路径集合搜索方法对优化城市交通流的必要性,并定义了城市交通网络中K最短路径集合的概念及选择条件,提出了一种面向城市交通网络的具有多项式时间复杂度的K最短路径集合搜索算法.仿真结果表明,本文所提算法可以搜索出满足出行需求的所有K最短路径集合,在该路径集合上进行交通流分配的效果明显优于传统方法.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 algorithm 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 Wardrop and the road impedance function theory, the paper analyzes the necessity of the path set searching method 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 shortest 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.

关 键 词：城市交通 路径搜索算法 K最短路径集合 城市路网 交通流优化 

分 类 号：U495[交通运输工程—交通运输规划与管理]