全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

中心式诱导路径优化计算方法

, PP. 106-113

Keywords: 交通控制,中心式诱导,最短路径,多级网络分解,双端队列算法,出行者偏好

Full-Text   Cite this paper   Add to My Lib

Abstract:

基于并行计算技术和网络数据存储方法,考虑了出行者的偏好,分析了多级网络分解方法和双端队列最短路径计算方法,提出了一种新的中心式诱导路径优化计算方法。以长沙市和长春市城市路网的实际数据为基础,在普通PC机群、联想服务器机群及惠普工作站机群3种不同计算性能的并行计算平台上进行试验测试。测试结果表明使用网络数据存储方法,能够直接确定邻接节点与相应弧的存储位置,节点信息的查询时间明显减小;使用多级网络分解方法,主要路段作为被切割弧的概率降低,最短路径计算过程中处理器的通信量减小;使用双端队列最短路径计算方法,最短路径计算速度明显提升;使用新的计算方法,长沙市路网中400万条最短路径计算时间为46s,长春市路网中1170万条最短路径计算时间为72s,完全能够满足中心式诱导路径优化时间小于5min的要求。

References

[1]  TOMKEWITSCH R V. Dynamic route guidance and interactive transport management with ALI-SCOUT[J]. IEEE Transactions on Vehicular Technology, 1991, 40(1): 45-50.
[2]  DEO N, PANG Chi-yin. Shortest path algorithms: taxonomy and annotation[J]. Networks, 1984, 14(2): 275-323.
[3]  O’CEARBHAILL E A, O’MAHONY M. Parallel implementation of a transportation network model[J]. Journal of Parallel and Distributed Computing, 2005, 65(1): 1-14.
[4]  王 媛.大范围战略交通协调控制系统关键技术研究[D].长春:吉林大学,2009. WANG Yuan. Research on key technologies of large-scale strategic traffic coordination and control system[D]. Changchun: Jilin University, 2009.(in Chinese)
[5]  李丽丽.基于拓扑关系的导航电子地图增量更新关键技术研究[D].长春:吉林大学,2009. LI Li-li. Key technology research of incremental updating of electronic navigation map based on topological relationship[D]. Changchun: Jilin University, 2009.(in Chinese)
[6]  陈 洁,陆 锋.一种基于双端队列的交通网络最短路径Pallottino优化算法[J].中国图象图形学报,2006,11(3):419-424. CHEN Jie, LU Feng. An optimization algorithm of Pallottino implemented with two queues in transportation network[J]. Journal of Image and Graphics, 2006, 11(3): 419-424.(in Chinese)
[7]  SUNDELL H, TSIGAS P. Lock-free deques and doubly linked lists[J]. Journal of Parallel and Distributed Computing, 2008, 68(7): 1008-1020.
[8]  MEYERHENKE H, MONIEN B, SAUERWALD T. A new diffusion-based multilevel algorithm for computing graph partitions[J]. Journal of Parallel and Distributed Computing, 2009, 69(9): 750-761.
[9]  KARYPIS G, KUMAR V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel and Distributed Computing, 1998, 58(1): 96-129.
[10]  ZHAN F B, NOON C E. Shortest path algorithms: an evaluation using real road networks[J]. Transportation Science, 1998, 32(1): 65-73.
[11]  ZHAN F B. Three fastest shortest path algorithms on real road networks: data structures and procedures[J]. Journal of Geographic Information and Decision Analysis, 1997, 1(1): 70-82.
[12]  MEYER U. Design and analysis of sequential and parallel single-source shortest-paths algorithms[D]. Saarbrücken: Universit?t des Saarlandes, 2002.
[13]  MEYER U, SANDERS P. Δ-stepping: a parallelizable short-est path algorithm[J]. Journal of Algorithms, 2003, 49(1): 114-152.
[14]  KARYPIS G, KUMAR V. Multilevel k-way hypergraph partitioning[J]. VLSI Design, 2000, 11(3): 343-348.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133