Dynamic Shortest Paths of Emergency Vehicles in Expressway Network Based on Shuffled Frog Leaping Algorithm

Abstract

Abstract:

Considering the discrete dynamic characteristic of the expressway network, a novel shuffled frog leaping algorithm is proposed to solve the shortest paths of emergency vehicles. In this paper, a random coding scheme is designed firstly, and then the concept of node travel time degree is introduced to improve the coding scheme. Then a backward marking update rule is put forward. The entering node moment and the link travel time of the worst individual are compared with those of the advantaged group, and the update rule makes the vehicle enter a shorter road section at the earlier time. Finally, the dynamic link travel time distributed in a normal is used as the weights, and the algorithm is verified by the example of expressway network of Dong Cheng District and Chao Yang District in Beijing. The results show that the proposed shuffled frog leaping algorithm can search the shortest path in one second. The calculation speed of the algorithm based on node travel time degree is raised by 100% comparing to the random coding scheme, and the average accuracy rate of the former is raised by 4.3% comparing to the latter.

Key words: highway transportation, non- FIFO dynamic shortest paths, shuffled frog leaping algorithm, expressway network, emergency vehicle shortest paths

摘要：

针对路网离散动态特性，提出一种求解应急车辆最短路径的混合蛙跳算法.首先设计一种随机编码方案，并引入节点时间度概念对编码方案进行了改进.然后，提出一种逆向标记迭代策略，通过对比优势族群与劣势个体的进入节点时刻和路段行程时间，促使车辆在最佳时刻进入最短路段.最后，以北京市东城区和朝阳区路网为例，将服从正态分布的动态路段行程时间作为权值，对算法进行了验证.验证结果表明，所提混合蛙跳算法能在1s内求得最短路径，基于节点时间度编码方案的混合蛙跳算法较随机编码方案计算速度提高一倍，平均计算准确率提高4.3%.

关键词: 公路运输, 非FIFO动态最短路径, 混合蛙跳算法, 路网, 应急车辆最短路径

CLC Number:

U495

DUAN Xiao-hong，ZHAO Jian-dong，SONG Shou-xin. Dynamic Shortest Paths of Emergency Vehicles in Expressway Network Based on Shuffled Frog Leaping Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(3): 181-186.

段晓红，赵建东，宋守信. 基于混合蛙跳的路网应急车辆动态最短路径[J]. 交通运输系统工程与信息, 2016, 16(3): 181-186.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/abstract/abstract19203.shtml

http://www.tseit.org.cn/EN/Y2016/V16/I3/181

References

[1] 王树西，吴政学. 改进的Dijkstra最短路径算法及其应用研究[J]. 计算机科学，2012，39(5)：223-228. [WANG S X, WU Z X. Improved dijkstra shortest path algorithm and its application[J]. Computer Science, 2012, 39(5): 223-228.]

[2] Pradhan A, Mahinthakumar G. Finding all- pairs shortest path for a large- scale transportation network using parallel floyd-warshall and parallel dijkstra algorithms[J]. Journal of Computing in Civil Engineering, 2013, 27(3): 263-273.

[3] 周培德. 交通道路网中任意两点之间最短路径的快速算法[J]. 计算机工程与科学，2002，24(4)：35-37. [ZHOU P D. A fast algorithm for finding the shortest path between arbitrary two points in a traffic road net[J]. Computer Engineering & Science, 2002, 24(4): 35-37. ]

[4] Yuan Y, Wang D. Path selection model and algorithm for emergency logistics management[J]. Computers & Industrial Engineering, 2009, 56(3): 1081-1094.

[5] 刘张雷，史忠科. 一种基于路网变化的动态路径规划策略[J]. 交通运输系统工程与信息，2010，10(3)：147- 152. [LIU Z L, SHI Z K. A dynamic route planning strategy based on road network changes[J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 10(3): 147-152.]

[6] Kaufman D, Smith R. Fastest paths in time-dependent networks for intelligent vehicle highway systems application[J]. Journal of Intelligent Transportation Systems, 1993, 1(1): 1-11.

[7] Nannicini G, Delling D, Schultes D, et al. Bidirectional A* search on time- dependent road networks[J]. Networks, 2012, 59(2): 240-251.

[8] Delling D, Nannicini G. Core routing on dynamic timedependent road networks[J]. Informs Journal on Computing, 2012, 24(2), 187-201.

[9] 谭国真，高文. 时间依赖的网络中最小时间路径算法[J]. 计算机学报，2002，25(2): 165-172. [TAN G Z, GAO W. Shortest path algorithm in time-dependent networks[J]. Chinese Journal of Computers, 2002, 25(2): 165-172.]

[10] WEN H, XU J, ZOU L. Genetic algorithm- based computation of the shortest path in discrete-time dynamic networks[J]. Journal of South China University of Technology (Natural Science Edition), 2008, 36(2): 13-16.

[11] 马炫，刘庆. 求解k 条最短路径问题的混合蛙跳算法[J]. 信息与控制，2011，40(5)：614-618. [MA X，LIU Q. A shuffled frog leaping algorithm for k-shortest paths problem[J]. Information and Control, 2011, 40(5): 614- 618.]

[12] DUAN X, SONG S, ZHAO J, et al. Emergency vehicle dispatching based on shuffled frog leaping algorithm[J]. Journal of Computational Information Systems, 2013, 9 (24): 9875-9884.

[13] Elbeltagi E, Hegazy T, Grierson D. Comparison among five evolutionary-based optimization algorithms[J]. Advanced Engineering Informatics, 2005(19): 43-53.

[14] 李长城，文涛，刘小明，等. 基于高速公路收费数据的行程时间可靠性模型研究[J]. 公路交通科技，2014，31 (12): 110-115. [LI C C, WEN T, LIU X M, et al. Study on reliability model of travel time based on expressway toll data[J]. Journal of Highway and Transportation Research and Development, 2014, 31(12):110-115.]

[1]	WANG Ning, ZHANG Jia-rui, ZHAO Jiao. Vehicle Routing Problem of Intercity Transportation Platform for Less-than-truck-load Cargo [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 163-177.
[2]	TAN Er-long , LI Hong-hai , ZHONG Hou-yue , HUO En-ze , MA Xiao-lei . Estimating Truck Spontaneous Platoon Fuel-saving Potential Based on Trajectory Data [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 74-84.
[3]	JIA Shu-yan , SONG Yu-tong, YANG Zi-du. Process of Peak Carbon Emissions of Trucks During Operating Activities Based on Growth Curve Function [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 310-318.
[4]	GAN Mi, QING San-dong, LIU Xiao-bo, LI Dan-dan. Review on Application of Truck Trajectory Data in Highway Freight System [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(5): 91-101.
[5]	LI Gen, ZHAI Wei, ZHU Xing-bei, YANG Sheng, WU Lan. Influence of Lateral Collision Risk on Merging Behavior of Weaving Area [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(4): 204-210.
[6]	LI Tao-ying,WANG Ting, ZHANG Yu-qi. Highway Traffic Flow Prediction Model with Multi-features [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(3): 101-111.
[7]	YUAN Fang, YANG Zhen, ZHOU Xiong-feng. Impact of Curve Radius and Spiral Length on Steering Behavior on Two-lane Highway [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(1): 116-123.
[8]	HU Li-wei, HE Yue-ren, LI Yao-ping, MENG Ling, YIN Xiu-fen. Commercial Truck Driving Risk Evaluation Based on Artificial Immune Mechanism [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(1): 149-155.
[9]	JI Xiao-feng, WU Ya-xin, HAO Jing-jing, FANG Rui, HU Cheng-yu. Severity Factors Analysis Model of Traffic Accident on Combined Horizontal and Vertical Alignments [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(6): 197-204.
[10]	. Evaluation of Eco-driving Behavior and Fuel-saving Potential of Large Freight Vehicles [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(6): 253-258.
[11]	DUAN Li-zhen, LUAN Qing-xiong, ZHAO Xin. Improved Statistical Method Measuring Freight Traffic Volume in Regional Road Network [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(4): 28-33.
[12]	LIU Yu, WU Zhi-xin, LI Meng-liang, YU Han-zheng-nan,. Development of China Light-duty Passenger Car Test Cycle [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(3): 233-240.
[13]	HE Yong-ming, PEI Yu-long, RAN Bin. Superhighway Virtual Track System Based on Intelligent Road Button [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(2): 55-60.
[14]	WANG Hai-xing,WANG Xiang-yu,WANG Zhao-xian, LI Xue-dong. Dangerous Driving Behavior Clustering Analysis for Hazardous Materials Transportation Based on Data Mining [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(1): 183-189.
[15]	YANG Tao,WANG Peng, ZHU Ji-ping, ZHAO Jian-dong. Optimization of Lane Number of Highway Toll Station Based on Multiple Payments [J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(5): 212-218.