交通运输系统工程与信息

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (3): 194-200.

• 系统工程理论与方法 • 上一篇    下一篇

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

段宗涛*1,2，WANG Wei-xing3，康 军 1,2 ，李 莹 1，郑西彬 1，程 豪 1，刘 研 1   

  1. 1、长安大学信息工程学院，西安 710064；2、陕西省道路交通智能检测与装备工程技术研究中心，西安 710064； 3、Royal Institute of Technology, Stockholm, Sweden
  • 收稿日期:2014-01-21 修回日期:2014-03-08 出版日期:2014-06-25 发布日期:2014-07-10
  • 作者简介:段宗涛（1977－），男，陕西凤翔人，副教授，工学博士.
  • 基金资助:

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

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

DUAN Zong-tao 1,2，WANG Wei-xing 3，KANG Jun1，LI Ying1， ZHENG Xi-bin1，CHENG Hao1，LIU Yan1   

  1. 1. School of Information Engineering , Chang’an University, Xi’an 710064, Shaanxi ,China; 2. Shaanxi Road and Traffic Detection Engineering and Technical Research Center, Xi’an 710064, Shaanxi, China; 3. Royal Institute of Technology, Stockholm, Sweden
  • Received:2014-01-21 Revised:2014-03-08 Online:2014-06-25 Published:2014-07-10

PDF

被引次数

25

摘要：

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

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

Abstract:

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.

Key words: urban traffic, path searching algorithm, K- th shortest path set, urban traffic network, traffic flow Optimization

中图分类号: