吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (05): 1210-1214.doi: 10.7964/jdxbgxb201305010

• paper • Previous Articles     Next Articles

Ant colony optimization for the shortest path of urban road network based on cloud computing

YANG Qing-fang1,2, MEI Duo2, HAN Zhen-bo3, ZHANG Biao2   

  1. 1. State Key Laboratory of Automotive Simulation and Control, Jilin University, Changchun 130022, China;
    2. College of Transportation, Jilin University, Changchun 130022, China;
    3. Municipal Science and Technology Commission of Hexi District, Tianjin 300202, China
  • Received:2012-08-24 Online:2013-09-01 Published:2013-09-01

Abstract:

In order to solve the problem of large amount of data encountered in solving the shortest path of urban road network, in this paper, an ant colony optimization algorithm based on cloud computing is proposed. The algorithm combines the simulated annealing algorithm, to compensate for the shortcomings of the ant colony algorithm. Compared to Message Passing Interface (MPI) parallel ant colony algorithm, with the increase in the nodes the running speed of the proposed algorithm is accelerated noticeably.

Key words: engineering of communications and transportation system, urban road network, shortest path, cloud computing, ant colony optimization

CLC Number: 

  • U491.2

[1] 倪安宁. 交通网络分析中的最短路径并行算法研究与实现[D]. 长春:吉林大学交通学院,2004. Ni An-ning. Study and implement of parallel shortest path algorithms in transportation network analysis[D]. Changchun:College of Transportation, Jilin University,2004.

[2] 章昭辉,闫春钢,丁志军,等. 交通信息网格中的最短出行路径并行算法[J]. 同济大学学报:自然科学版,2006,34(12):1606-1611. Zhang Zhao-hui,Yan Chun-gang, Ding Zhi-jun, et al. A parallel algorithm of the shortest travel path in traffic information grid[J].Journal of Tongji University(Natural Science),2006,34(12):1606-1611.

[3] 马明全,周明全,耿国华,等.基于社区分析的最短路径计算[J].计算机应用与软件,2009,25(4):177-181. Ma Ming-quan,Zhou Ming-quan,Geng Guo-hua, et al. Study on network partition and shortest path based upon community analysis[J].Computer Applications and Software, 2009,25(4):177-181.

[4] 王磊,曹菡. 基于TBB和Cilk++的并行蚁群算法在路径寻优中的应用[J]. 计算机应用,2010,30(10):2781-2784. Wang Lei,Cao Han. Application of parallel ant colony algorithm based on TBB and Cilk++in path optimization[J]. Journal of Computer Applications,2010,30(10):2781-2784.

[5] 卢照. 基于城市路网最短路径并行搜索算法的研究[D]. 西安:陕西师范大学计算机科学学院,2010. Lu Zhao. Research on parallel search algorithm based on the shortest path of the urban road network[D].Xi'an:College of Computer Science, Shanxi Normal University,2010.

[6] 杨庆芳,刘冬,杨兆升. 基于MPI+OpenMP混合编程模型的城市路网最短路径并行算法[J]. 吉林大学学报:工学版,2011,41(6):1581-1584. Yang Qing-fang, Liu Dong, Yang Zhao-sheng. Parallel algorithm for urban road network shortest path based on MPI+OpenMP hybrid programming model[J].Journal of Jilin University(Engineering and Technology Edition),2011,41(6):1581-1584.

[7] 刘鹏.云计算[M]. 北京:电子工业出版社,2011.

[8] Plimpton Steven J, Devine Karen D. MapReduce in MPI for large-scale graph algorithms[J].Parallel Computing, 2011,37:610-632.

[9] McCubbin Christopher, Perozzi Bryan,Levine Andrew,et al.Finding the ‘Needle': locating interesting nodes using the K-shortest paths algorithm in MapReducep[C]//The 11th IEEE International Conference on Data Mining Workshops,Vancouver,2011.

[10] Kambatla Karthik, Rapolu Naresh, Jagannathan Suresh,et al.Asynchronous algorithms in MapReduce[C]//2010 IEEE International Conference on Cluster Computing,Heraklion,Crete,Greece,2010.

[11] 杨玲,李仁发,唐卓. 基于MapReduce的单源最短路径算法研究[J].微计算机信息,2011,27(12):97-99. Yang Ling, Li Ren-fa, Tang Zhuo. Research on single shortest parh algorithm using MapReduce[J]. Microcomputer Information, 2011,27(12):97-99.

[12] 许明军. 若干随机性全局优化算法的研究[D].大连:大连理工大学数学科学学院,2004. Xu Ming-jun. Study on some stochastic global optimization algorithms[D]. Dalian:College of Mathematical Science, Dalian University of Technology,2004.

[1] CHEN Yong-heng,LIU Fang-hong,CAO Ning-bo. Analysis of conflict factors between pedestrians and channelized right turn vehicles at signalized intersections [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1669-1676.
[2] LIU Xiang-yu, YANG Qing-fang, KUI Hai-lin. Traffic guidance cell division based on random walk algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1380-1386.
[3] LIU Zhao-hui, WANG Chao, LYU Wen-hong, GUAN Xin. Identification of data characteristics of vehicle running status parameters by nonlinear dynamic analysis [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1405-1410.
[4] LUAN Xin, DENG Wei, CHENG Lin, CHEN Xin-yuan. Mixed Logit model for understanding travel mode choice behavior of megalopolitan residents [J]. 吉林大学学报(工学版), 2018, 48(4): 1029-1036.
[5] CHEN Yong-heng, LIU Xin-shan, XIONG Shuai, WANG Kun-wei, SHEN Yao, YANG Shao-hui. Variable speed limit control under snow and ice conditions for urban expressway in junction bottleneck area [J]. 吉林大学学报(工学版), 2018, 48(3): 677-687.
[6] WANG Zhan-zhong, LU Yue, LIU Xiao-feng, ZHAO Li-ying. Improved harmony search algorithm on truck scheduling for cross docking system [J]. 吉林大学学报(工学版), 2018, 48(3): 688-693.
[7] CHEN Song, LI Xian-sheng, REN Yuan-yuan. Adaptive signal control method for intersection with hook-turn buses [J]. 吉林大学学报(工学版), 2018, 48(2): 423-429.
[8] SU Shu-jie, HE Lu. Transient dynamic congestion evacuation model of pedestrian at walk traffic planning crossroads [J]. 吉林大学学报(工学版), 2018, 48(2): 440-447.
[9] WANG Zhan-zhong, ZHAO Li-ying, JIAO Yu-Ling, CAO Ning-bo. Social force model of pedestrian-bike mixed flow at signalized crosswalk [J]. 吉林大学学报(工学版), 2018, 48(1): 89-97.
[10] HOU Xian-yao, CHEN Xue-wu. Use of public transit information market segmentation based onattitudinal factors [J]. 吉林大学学报(工学版), 2018, 48(1): 98-104.
[11] GAO Kun, TU Hui-zhao, SHI Heng, LI Zhen-fei. Effect of low visibility in haze weather condition on longitudinal driving behavior in different car-following stages [J]. 吉林大学学报(工学版), 2017, 47(6): 1716-1727.
[12] WEI Li-ying, CUI Yu-feng, WEI Jia-rong. Cellular automata model based on local maximum entropy lane-changing rules for electric bicycle flow [J]. 吉林大学学报(工学版), 2017, 47(5): 1436-1445.
[13] YAO Rong-han, ZHANG Xiao-tong, LIAN Lian. Optimization model for controlling reversible approach lanes at signalized intersections [J]. 吉林大学学报(工学版), 2017, 47(4): 1048-1054.
[14] FANG Rui-wei, ZHANG Xie-dong, JIANG Pan. Planning of urban rapid transportation based on SWOT-AHP analysis [J]. 吉林大学学报(工学版), 2017, 47(4): 1055-1060.
[15] LI Ming-da, KUI Hai-lin, MEN Yu-zhuo, BAO Cui-zhu. Aerodynamic drag of heavy duty vehicle with complex underbody structure [J]. 吉林大学学报(工学版), 2017, 47(3): 731-736.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[5] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[6] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[7] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[8] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[9] XIAO Yun, LEI Jun-qing, ZHANG Kun, LI Zhong-san. Fatigue stiffness degradation of prestressed concrete beam under multilevel amplitude cycle loading[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .
[10] XIAO Rui, DENG Zong-cai, LAN Ming-zhang, SHEN Chen-liang. Experiment research on proportions of reactive powder concrete without silica fume[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .