大规模交通网络实时路径搜索算法研究

交通运输系统工程与信息 ›› 2009, Vol. 9 ›› Issue (5): 141-147 .

大规模交通网络实时路径搜索算法研究

李树彬^1，2 ;高自友^*1 ;林勇² ;吴建军¹;李珂²;许兆霞²;丁青燕¹

1北京交通大学交通运输学院，北京 100044; 2山东省科学院自动化研究所，济南　250014

收稿日期:2009-05-07 修回日期:2009-07-13 出版日期:2009-10-25 发布日期:2009-10-25
通讯作者: 高自友
作者简介:李树彬（1977-），男，山东人，博士生，助理研究员.
基金资助:
国家重点基础研究发展计划(973计划)(2006CB705500) ；国家自然科学基金（70801005，70871099）；公安部应用创新计划项目（2007YYCXSDST057）；山东省自然科学基金（Y2008F14）；山东省科学院博士基金项目（鲁科院字[2008]102号）.

Real-Time Path Searching Algorithm for Large Traffic Network

LI Shu-bin ^1,2; GAO Zi-you ¹;LIN Yong ²; WU Jian-jun ¹; LI Ke²;XU Zhao-xia²; DING Qing-yan¹

1 School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China)
(2 Institute of Automation, Shandong Academy of Sciences, Jinan 250014, China

Received:2009-05-07 Revised:2009-07-13 Online:2009-10-25 Published:2009-10-25
Contact: GAO Zi-you

摘要/Abstract

摘要： 对在研的DynaCHINA软件中大规模交通网络下的实时路径搜索问题进行了研究。提出了新的设计思想，给出了有效路径的产生算法，并设计了支持海量路径数据的存储及高效检索的数据结构。算法充分利用路径的递归特性，降低问题的规模，实现了较小空间花费下的海量路径随机查询。大大提高了大规模交通网络中实时路径搜索问题的计算速度，节省了计算机存储资源。通过与原有算法比较表明，本算法能够在较小的计算机存储资源下，快速有效的处理大规模交通网络中的实时路径搜索问题，具有广阔的应用前景和现实意义。

关键词: 大规模交通网络, 实时, 路径搜索, 递归算法, 动态中国

Abstract: In this paper, the real-time path searching problem for the larger traffic network is investigated in the developing software—DynaCHINA, and an effective path generation algorithm is proposed. Additionally, a new data structure is provided to store large count of paths and support high performance searching. By the recursive property, the new algorithm can reduce the size of problem which derives the paths with a small space required. As a result, it improves the computing speed greatly in real-time path searching and saves the computer memory resource significantly. Compared with original algorithms, it is found that the proposed algorithm deals with the real-time path searching problem in large traffic network quickly and effectively with a small computer memory. Therefore, the algorithm can be used in practical traffic management.

Key words: large traffic network, real-time;path searching, recursive algorithm, DynaCHINA

中图分类号:

F491.13

李树彬,高自友,林勇,吴建军,李珂,许兆霞,丁青燕. 大规模交通网络实时路径搜索算法研究[J]. 交通运输系统工程与信息, 2009, 9(5): 141-147 .

LI Shu-bin, GAO Zi-you,LIN Yong, WU Jian-jun, LI Ke,XU Zhao-xia, DING Qing-yan. Real-Time Path Searching Algorithm for Large Traffic Network[J]. Journal of Transportation Systems Engineering and Information Technology, 2009, 9(5): 141-147 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17879.shtml

http://www.tseit.org.cn/CN/Y2009/V9/I5/141

参考文献

[1] 卢开澄，卢华明.图论及其应用（第二版）[M].北京:清华大学出版社，1997。[LU K C，LU H M. Graph theory and applications (second edition) [M]. BeiJing: Tsinghua University Press,1997.]

[2] 米涅卡 E.网络和图的最优化算法[M].李家滢,赵关旗译.北京:中国铁道出版社，1984.[

Minieka E. Optimization algorithms for network and graphs [M]. LI J Y, ZHAO G Q Translation.BeiJing: China Railway Publishing House,1984.]

[3] 柴登峰,张登荣. 前n条最短路径问题的算法及应用[J]，浙江大学学报:工学版, 2002, 36(5): 531 -534.[CHAI D F; ZHANG D R. Algorithm and its application to N shortest paths problem[J], Journal of Zhejiang University(Engineering Science)，2002, 36(5): 531 -534.]

[4] 乐阳，龚健雅. Dijkstra 最短路径算法的一种高效率实现 [J]，武汉测绘科技大学学报,1999, 24(3):209-212.[YUE Y，GONG J Y. An efficient implementation of shortest path algorithm based on dijkstra algorithm[J]，Journal of Wuhan Technical University of Surveying and Mapping(Wtusm), 1999, 24(3):209-212.]

[5] 吴晓红. 关于最短路径问题的一种有效算法[J].系统工程与电子技术，2000,22( 11):95-98.[WU X H. On an effective algorithm of the shortest path problem [J]. Systems Engineering and Electronics, 2000,22( 11):95-98.]

[6] 王炜. 多路径交通分配模型的改进及节点分配算法[J]，东南大学学报 1994.06(24):21-26.[WANG W. Improved model of multipath assignment and quick algorithm─node assignment algorithm [J], Journal of Southeast University, 1994.06(24):21-26.]

[7] Huey-Kuo Chen , Cheng-Yi Chou. Comparisons of yen’s and a modified generalized floyd K-shortest-path algorithms [J]. Journal of the Eastern Asia Society for Transportation Studies, 1999, 3(1): 233-246.

[8] Zhan F B. Three fastest shortest path algorithms on real road networks [J]. Journal of Geographic Information and Decision Analysis, 1997, 1 (1): 69-82.

[1]	王福建, 俞佳浩, 赵锦焕, 梅振宇. 基于站点实时关联度的短时公交客流预测方法[J]. 交通运输系统工程与信息, 2021, 21(6): 131-144.
[2]	韦清波，苏跃江，高媛，杨敬锋，莫竣杰. 基于电子支付数据的公交车厢满载率实时估算方法[J]. 交通运输系统工程与信息, 2021, 21(1): 75-81.
[3]	张建旭，郭力玮. 基于在线地图交通态势分析的路网拥堵状态识别[J]. 交通运输系统工程与信息, 2018, 18(5): 75-81.
[4]	郇宁，谢俏，叶红霞，姚恩建. 基于改进KNN算法的城轨进站客流实时预测[J]. 交通运输系统工程与信息, 2018, 18(5): 121-128.
[5]	严海，刘润坤. 基于实时信息的公交运行速度控制策略与算法研究[J]. 交通运输系统工程与信息, 2018, 18(4): 61-68.
[6]	游锦明，方守恩，唐棠，张兰芳. 不良交通流状态实时监测支持向量机模型算法研究[J]. 交通运输系统工程与信息, 2018, 18(4): 83-87.
[7]	赵文忠，耿立艳，梁毅刚，张占福. 基于多维数据的高速公路服务水平实时判别方法[J]. 交通运输系统工程与信息, 2018, 18(4): 240-246.
[8]	黄家骏，徐瑞华，洪玲，黄肇红. 动态不确定性环境下的地铁车站应急疏散仿真建模[J]. 交通运输系统工程与信息, 2018, 18(2): 164-170.
[9]	周继彪，王群燕，张敏捷，董升，张水潮. 7 种因素对电动自行车忍耐时间的实证研究[J]. 交通运输系统工程与信息, 2017, 17(5): 242-249.
[10]	邓念，彭其渊，占曙光. 干扰条件下高速铁路列车运行实时调整问题研究[J]. 交通运输系统工程与信息, 2017, 17(4): 118-123.
[11]	陈玲娟，王殿海. 短时事故扰动下的逐日路网流量演化模型[J]. 交通运输系统工程与信息, 2017, 17(2): 112-118.
[12]	李颖宏，潘佳琪. 基于Optima 的实时在线交通流预测方法研究[J]. 交通运输系统工程与信息, 2017, 17(2): 119-125.
[13]	王钰，徐建闽，林培群. 基于GPS 数据的信号交叉口实时排队长度估算[J]. 交通运输系统工程与信息, 2016, 16(6): 67-73.
[14]	段宗涛*1,2，WANG Wei-xing3，康军 1,2,李莹 1，郑西彬 1，程豪 1，刘研 1. 面向城市交通网络的 K 最短路径集合算法[J]. 交通运输系统工程与信息, 2014, 14(3): 194-200.
[15]	李敏，黄敏*，钮中铭，李尔达. 考虑连接性标识的指引信息可达性分析及评价[J]. 交通运输系统工程与信息, 2014, 14(2): 226-231.