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

作者：段宗涛; WANGWei xing; 康军; 李莹; 郑西彬; 程豪; 刘研

来源：交通运输系统工程与信息, 2014, (03): 194-200.

DOI：10.16097/j.cnki.1009-6744.2014.03.035

• 城市交通
• 路径搜索算法
• K最短路径集合
• 城市路网
• 交通流优化 urban traffic
• path searching algorithm
• K-th shortest path set
• urban traffic network
• traffic flow Optimization

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

• 出版日期2014
• 单位长安大学; Royal Institute of Technology