基于云计算的大规模交通路网最短路径算法

doi:10.3969/j.issn.1000-565X.2018.12.017

华南理工大学学报（自然科学版） ›› 2018, Vol. 46 ›› Issue (12): 139-146.doi: 10.3969/j.issn.1000-565X.2018.12.017

• 交通运输工程 • 上一篇

基于云计算的大规模交通路网最短路径算法

张东波^{1， 2} 林永杰^2† 卢凯² 首艳芳³ 徐建闽²

1．广东省智能制造研究所∥广东省现代控制技术重点实验室∥广东省现代控制与光机电技术公共实验室，广东广州 510070;
2．华南理工大学土木与交通学院，广东广州 510641;
3．华南理工大学广州现代产业技术研究院，广东广州 510641)

收稿日期:2018-01-21 修回日期:2018-09-04 出版日期:2018-12-25 发布日期:2018-11-01
通信作者: 林永杰( 1987-) ，男，博士，讲师，主要从事交通信号控制和数据挖掘研究 E-mail:linyjscut@scut.edu.cn
作者简介:张东波(1984-) ，男，博士，讲师，主要从事大数据处理和人工智能研究
基金资助:
国家自然科学基金项目( 61773168) ;
广东省科技计划项目( 2016A030305001) ;
广东省科学院实施创新驱动发展能力建设专项( 2017GDASCX-0115， 2018GDASCX-0115)

The Shortest Path Algorithm for Large-scale Traffic Network based on Cloud Computing

ZHANG Dongbo^{1， 2} LIN Yongjie² LU Kai² SHOU Yanfang³ XU Jianmin²

1． Guangdong Institute of Intelligent Manufacturing，Key Laboratory of Modern Control Technology of Guangdong Province，Open Laboratory of Modern Control ＆ Optical，Mechanical and Electronic Technology of Guangdong Province，Guangzhou 510070， Guangdong，China; 2． School of Civil Engineering and Transportation，South China University of Technology，Guangzhou 510641，Guangdong，China;
3． Guangzhou Institute of Modern Industrial Technology，South China University of Technology， Guangzhou 510641，Guangdong，China

Received:2018-01-21 Revised:2018-09-04 Online:2018-12-25 Published:2018-11-01
Contact: 林永杰( 1987-) ，男，博士，讲师，主要从事交通信号控制和数据挖掘研究 E-mail:linyjscut@scut.edu.cn
About author:张东波(1984-) ，男，博士，讲师，主要从事大数据处理和人工智能研究
Supported by:
The National Natural Science Foundation of China( 61773168) and the Science and Technology Planning Project of Guangdong Province( 2016A030305001)

摘要/Abstract

摘要： 云计算通常是通过互联网来提供动态易扩展且经常是虚拟化的计算资源，并已经拓展到各个领域，尤其是交通海量数据处理。MapReduce并行编程模型是一种支持云计算算法设计的新框架，可利用网络中大量不同位置的计算机进行集群式海量数据处理。本文基于MapReduce构建一个新的计算框架，建立了基于子图分割的并行搜索方法，实现超大规模真实交通路网中最短路径搜索。案例分析证明：该方法能够在可接受的计算时间内提供高质量的最短路径搜索服务。

关键词: 最短路径, 大规模路网, 并行计算, 子图分割

Abstract: Cloud computing usually provides dynamically scalable and virtualized computing resources through the Internet, and has widely been used in various fields, especially mass traffic processing. The MapReduce parallel programming model is a novel framework that supports the design of cloud computing algorithms, and can invoke clustered computers at different locations to conduct huge data processing. This study proposed a new computing logic on the base of MapReduce, and developed a parallel searching algorithm with subgraph partitions to search the shortest path in large-scale real traffic networks. In tests of the field networks, the proposed method can provide high-quality shortest path searching service within acceptable calculation time.

Key words:

shortest path, largescale network, parallel computing, sub-graph partition

中图分类号:

张东波林永杰卢凯首艳芳徐建闽. 基于云计算的大规模交通路网最短路径算法[J]. 华南理工大学学报（自然科学版）, 2018, 46(12): 139-146.

ZHANG Dongbo LIN Yongjie LU Kai SHOU Yanfang XU Jianmin. The Shortest Path Algorithm for Large-scale Traffic Network based on Cloud Computing[J]. Journal of South China University of Technology (Natural Science Edition), 2018, 46(12): 139-146.

[1]	康文雄许耀钊. 节点约束型最短路径的分层Dijkstra 算法[J]. 华南理工大学学报（自然科学版）, 2017, 45(1): 66-73.
[2]	徐建闽王钰林培群. 大数据环境下的动态最短路径算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(10): 1-7.
[3]	胡学萱奚建清林妙. 基于 GPU 的可扩展哈希方法[J]. 华南理工大学学报（自然科学版）, 2015, 43(1): 111-117.
[4]	杨庆芳梅朵郑黎黎马明辉王伟. 基于云计算的城市路网最短路径遗传算法求解[J]. 华南理工大学学报（自然科学版）, 2014, 42(3): 47-51,58.
[5]	董守玲李佳张凌. 基于距离的IPv6校园网拓扑发现整合算法[J]. 华南理工大学学报(自然科学版), 2012, 40(8): 69-75.
[6]	颜小洋张伟文布社辉邓辉舫. 基于MPI /OPENMP 混合编程的三维粒子模拟并行优化[J]. 华南理工大学学报(自然科学版), 2012, 40(4): 71-78.
[7]	李珊珊钱大琳王九州. 基于多核的并行混合交通微观仿真系统[J]. 华南理工大学学报(自然科学版), 2012, 40(2): 57-62.
[8]	温惠英徐建闽邹亮 . 基于遗传算法的离散时间动态网络最短路径求解[J]. 华南理工大学学报（自然科学版）, 2008, 36(2): 13-16,28.
[9]	邹亮徐建闽. 公共交通路网描述方法及诱导模型设计[J]. 华南理工大学学报（自然科学版）, 2005, 33(9): 41-44.

基于云计算的大规模交通路网最短路径算法

The Shortest Path Algorithm for Large-scale Traffic Network based on Cloud Computing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价