基于混合蛙跳的路网应急车辆动态最短路径

交通运输系统工程与信息 ›› 2016, Vol. 16 ›› Issue (3): 181-186.

基于混合蛙跳的路网应急车辆动态最短路径

段晓红^a，赵建东*^a，宋守信^b

北京交通大学a. 机械与电子控制工程学院；b. 经济管理学院，北京100044

收稿日期:2015-10-29 修回日期:2015-11-20 出版日期:2016-06-25 发布日期:2016-06-27
作者简介:段晓红（1988-），女，青海海东人，博士生.
基金资助:
中央高校基本科研业务费专项资金/The Fundamental Research Funds for the Central Universities（2016JBM053）.

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

DUAN Xiao-hong^a，ZHAO Jian-dong^a，SONG Shou-xin^b

a. School of Mechanical and Electronic Control Engineering; b. School of Economics and Management, Beijing Jiaotong University, Beijing 100044, China

Received:2015-10-29 Revised:2015-11-20 Online:2016-06-25 Published:2016-06-27

摘要/Abstract

摘要：

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

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

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

中图分类号:

U495

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

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.

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

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

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

参考文献

[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]	王宁, 张佳蕊, 赵姣. 城际零担货运平台车辆路径问题研究[J]. 交通运输系统工程与信息, 2022, 22(2): 163-177.
[2]	谭二龙, 李宏海, 钟厚岳, 霍恩泽, 马晓磊. 基于轨迹数据的货车自发编队节油潜力估计[J]. 交通运输系统工程与信息, 2022, 22(1): 74-84.
[3]	卢凯, 周志洁, 张勇刚, 赵世杰, 徐广辉. 面向单向交通路网的绿波协调设计方法[J]. 交通运输系统工程与信息, 2021, 21(6): 74-83.
[4]	贾术艳, 宋雨童, 杨紫都. 基于生长曲线函数的货车运营环节碳达峰研究[J]. 交通运输系统工程与信息, 2021, 21(6): 310-318.
[5]	甘蜜, 卿三东, 刘晓波, 李丹丹. 货车轨迹数据在公路货运系统中应用研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 91-101.
[6]	张伟斌, 张蒲璘, 苏子毅, 孙锋. 基于自注意力机制与图自编码器的路网交通流数据修复模型[J]. 交通运输系统工程与信息, 2021, 21(4): 90-98.
[7]	李根, 翟伟, 朱兴贝, 杨晟, 邬岚. 侧向碰撞风险对交织区汇合行为的影响[J]. 交通运输系统工程与信息, 2021, 21(4): 204-210.
[8]	李桃迎，王婷，张羽琪. 考虑多特征的高速公路交通流预测模型[J]. 交通运输系统工程与信息, 2021, 21(3): 101-111.
[9]	袁方，杨轸，周雄峰. 双车道公路弯道半径及回旋线长度对转向行为的影响[J]. 交通运输系统工程与信息, 2021, 21(1): 116-123.
[10]	管德永，张树鹏，刘海青. 基于换道轨迹规划模型的车道级行程时间估计方法研究[J]. 交通运输系统工程与信息, 2021, 21(1): 124-131.
[11]	胡立伟，何越人，李耀平，孟玲，殷秀芬. 基于人工免疫机制的营运货车运行风险评价研究[J]. 交通运输系统工程与信息, 2021, 21(1): 149-155.
[12]	张凌煊，帅斌，丁冬，张士行，王睿. 考虑超级街区的城市路网边界控制策略研究[J]. 交通运输系统工程与信息, 2020, 20(6): 91-98.
[13]	戢晓峰，吴亚欣，郝京京，房锐，胡澄宇. 平纵组合路段事故严重程度致因辨识模型[J]. 交通运输系统工程与信息, 2020, 20(6): 197-204.
[14]	程颖，张佳乐，张少君，郭继孚，张达. 大型货运车辆生态驾驶及节油潜力评估[J]. 交通运输系统工程与信息, 2020, 20(6): 253-258.
[15]	代亮，梅洋，李曙光，钱超，汪贵平. 基于对称残差U型网络的路网交通流量数据修复[J]. 交通运输系统工程与信息, 2020, 20(5): 93-99.