考虑干线协调控制的城市最优路径搜索算法

doi:10.13229/j.cnki.jdxbgxb201606007

吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (6): 1799-1806.doi: 10.13229/j.cnki.jdxbgxb201606007

考虑干线协调控制的城市最优路径搜索算法

周熙阳¹, 杨兆升^{1, 2, 3}, 张伟^{1, 2, 4}, 邴其春¹, 商强¹

1.吉林大学交通学院,长春 130022;
2.吉林大学汽车仿真与控制国家重点实验室,长春 130022;
3.吉林大学吉林省道路交通重点实验室,长春 130022;
4.山东高速公路股份有限公司,济南 250014

收稿日期:2016-02-22 出版日期:2016-11-20 发布日期:2016-11-20
通讯作者: 张伟(1978-),男,高级工程师,在站博士后.研究方向:智能交通关键理论与技术.E-mail:z_wei@126.com
作者简介:周熙阳(1989-),男,博士研究生.研究方向:智能交通关键理论与技术.E-mail:zhouxy14@mails.jlu.edu.cn
基金资助:
国家科技支撑计划项目(2014BAG03803)

Urban shortest path searching algorithm considering coordinate control of arterial intersections

ZHOU Xi-yang¹, YANG Zhao-sheng^{1, 2, 3}, ZHANG Wei^{1, 2, 4}, BING Qi-chun¹, SHANG Qiang¹

1.College of Transportation, Jilin University, Changchun 130022, China;
2.State Key Laboratory of Automotive Simulation and Control, Jilin University, Changchun 130022, China;
3.Jilin Province Key Laboratory of Road Traffic, Jilin University, Changchun 130022, China, 4.Shandong High-speed Co., Ltd., Ji'nan 250014, China

Received:2016-02-22 Online:2016-11-20 Published:2016-11-20

摘要/Abstract

摘要：

针对现有最优路径搜索算法没有考虑到干线协调控制的情况,导致搜索到的最优路径实际效果不佳等问题,提出了一种考虑干线协调控制的城市最优路径搜索算法。首先,将相位差引入到干线协调配时方案中,提出了一种改进的信号交叉口等待时间模型。然后,以IDA^*算法为基础,提出了一种考虑干线协调控制的改进IDA^*搜索算法(AICIDA^*算法),以路径总时间费用和运算时间为评价指标进行了算例验证。结果表明:与传统算法和考虑干线协调控制的A^*算法(AICA^*算法)相比,AICIDA^*算法能够在更短的时间内搜索到费用更低的路径。

关键词: 交通运输系统工程, 最优路径搜索算法, 干线协调控制, 信号交叉口等待时间, IDA&#x0002A, 算法

Abstract:

Existing shortest path searching algorithms do not consider the coordinate control of arterial intersections, which leads to unsatisfactory searching results. To overcome this drawback an urban shortest path algorithm is developed, which takes the coordinate control of arterial intersections into consideration. First, with the analysis of the coordinate signal timing at the arterial intersections and the offset parameter, an improved signal intersection waiting time model is proposed. Second, with the combination of IDA^* algorithm and the improved signal waiting time model, an improved IDA^* algorithm considering the coordinate control of arterial intersections (AICIDA^*) is developed. The AICIDA^* algorithm is compared with two traditional algorithms and an improved A^* algorithm considering the coordinate control of arterial intersections (AICA^*) through a case study, in which the path time cost and computing time are taken as the evaluation indexes. Results show that the proposed AICIDA^* algorithm can obtain the better path time cost in a shorter computing time.

Key words: engineering of communication and transportation system, shortest path searching algorithm, arterial intersections coordinate control, signal intersection waiting time, IDA&#x0002A, algorithm

中图分类号:

U491.1

周熙阳, 杨兆升, 张伟, 邴其春, 商强. 考虑干线协调控制的城市最优路径搜索算法[J]. 吉林大学学报(工学版), 2016, 46(6): 1799-1806.

ZHOU Xi-yang, YANG Zhao-sheng, ZHANG Wei, BING Qi-chun, SHANG Qiang. Urban shortest path searching algorithm considering coordinate control of arterial intersections[J]. 吉林大学学报(工学版), 2016, 46(6): 1799-1806.

参考文献

[1] 徐长斌,刘艳梅. 动态路径诱导算法研究[J]. 公路交通科技:应用技术版,2007,3(10):35-36.
Xu Chang-bin, Liu Yan-mei. The research of algorithm on dynamic path guidance[J]. Journal of Highway and Transportation Research and Development(Applied Technique),2007,3(10):35-36.
[2] Bolívar M A, Lozano L, Medaglia A L. Acceleration strategies for the weight constrained shortest path problem with replenishment[J]. Optimization Letters,2014,8(8):2155-2172.
[3] Klunder G A, Post H N. The shortest path problem on large-scale real-road networks[J]. Networks,2006,48(4):182-194.
[4] Kim J, Han W S. Processing time-dependent shortest path queries without pre-computed speed information on road networks[J]. Information Sciences, 2014,255(1):135-154.
[5] 盖文妹,邓云峰,蒋仲安,等. 双权重应急交通网络最优路径数学模型及算法研究[J]. 中南大学学报:自然科学版,2014(6):2366-2375.
Gai Wen-mei, Deng Yun-feng,Jiang Zhong-an,et al. Model and its fast approximation algorithm of optimal route in a dual-weight emergency transportation network[J]. Journal of Central South University(Science and Technology), 2014(6):2366-2375.
[6] 杨庆芳,梅朵. 基于云计算的城市路网最短路径遗传算法求解[J]. 华南理工大学学报:自然科学版,2014,42(3):47-58.
Yang Qing-fang, Mei Duo. Cloud computing-based genetic algorithm to solve the shortest path in urban road networks[J]. Journal of South China University of Technology(Natural Science Edition),2014,42(3):47-58.
[7] Hoang V D, Jo K H. Path planning for autonomous vehicle based on heuristic searching using online images[J]. Vietnam Journal of Computer Science, 2015,2(2):109-120.
[8] 杜长海,黄希樾. 改进的蚁群算法在动态路径诱导中的应用研究[J]. 计算机工程与应用,2008,44(27):236-239.
Du Chang-hai,Huang Xi-yue. Study on application of improved ant colony algorithm in dynamic route guidance[J]. Computer Engineering and Applications,2008,44(27):236-239.
[9] Frangioni A, Galli L, Scutellà M G. Delay-constrained shortest paths: approximation algorithms and second-order cone models[J]. Journal of Optimization Theory and Applications,2015,164(3):1051-1077.
[10] 高淑萍,赵会宾. 基于信号配时的动态路径诱导模型[J]. 中国公路学报,2011,24(1):109-114.
Gao Shu-ping, Zhao Hui-bin. Dynamic route guidance model based on signal lamp time assignment[J]. China Journal of Highway and Transport,2011,24(1):109-114.
[11] 杨琰,廖伟志,李文敬. 基于Petri网的顾及转向延误的最优路径算法[J]. 计算机工程与设计,2013(10):3643-3648.
Yang Yan, Liao Wei-zhi,Li Wen-jing. Intelligent routing algorithm considering turn delays based on Petri net[J]. Computer Engineering and Design,2013(10):3643-3648.
[12] 黄美灵,陆百川.考虑交叉口延误的城市道路最短路径[J]. 重庆交通大学学报:自然科学版,2009,28(6):1060-1063.
Huang Mei-ling, Lu Bai-chuan. Determination of the shortest path considering delays at intersections[J]. Journal of Chongqing Jiaotong University(Natural Science Edition),2009,28(6):1060-1063.
[13] 李继伟. 城市主次干路的路段行程时间估计与预测方法研究[D]. 长春:吉林大学交通学院,2012.
Li Ji-wei. Estimation and prediction of link travel time for urban trunk and secondary streets[D]. Changchun: College of Transportation, Jilin University, 2012.
[14] 杨帆,杨晓光. 考虑信号交叉口等待时间的最短路径算法[J]. 同济大学学报:自然科学版,2013,41(5):680-686.
Yang Fan, Yang Xiao-guang. Shortest path algorithm with a consideration of waiting time at signalized intersections[J]. Journal of Tongji University(Natural Science Edition),2013,41(5):680-686.
[15] Mencía C, Sierra M R, Varela R. Intensified iterative deepening A * with application to job shop scheduling[J]. Journal of Intelligent Manufacturing,2014,25(6):1245-1255.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

考虑干线协调控制的城市最优路径搜索算法

Urban shortest path searching algorithm considering coordinate control of arterial intersections

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	陈永恒,刘芳宏,曹宁博. 信控交叉口行人与提前右转机动车冲突影响因素[J]. 吉林大学学报(工学版), 2018, 48(6): 1669-1676.
[2]	常山,宋瑞,何世伟,黎浩东,殷玮川. 共享单车故障车辆回收模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1677-1684.
[3]	曲大义,杨晶茹,邴其春,王五林,周警春. 基于干线车流排队特性的相位差优化模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1685-1693.
[4]	代存杰,李引珍,马昌喜,柴获,牟海波. 不确定条件下危险品配送路线多准则优化[J]. 吉林大学学报(工学版), 2018, 48(6): 1694-1702.
[5]	吴蔚楠,崔乃刚,郭继峰,赵杨杨. 多异构无人机任务规划的分布式一体化求解方法[J]. 吉林大学学报(工学版), 2018, 48(6): 1827-1837.
[6]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[7]	周彦果,张海林,陈瑞瑞,周韬. 协作网络中采用双层博弈的资源分配方案[J]. 吉林大学学报(工学版), 2018, 48(6): 1879-1886.
[8]	赵伟强, 高恪, 王文彬. 基于电液耦合转向系统的商用车防失稳控制[J]. 吉林大学学报(工学版), 2018, 48(5): 1305-1312.
[9]	宗芳, 齐厚成, 唐明, 吕建宇, 于萍. 基于GPS数据的日出行模式-出行目的识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1374-1379.
[10]	刘翔宇, 杨庆芳, 隗海林. 基于随机游走算法的交通诱导小区划分方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1380-1386.
[11]	钟伟, 隽志才, 孙宝凤. 不完全网络的城乡公交一体化枢纽层级选址模型[J]. 吉林大学学报(工学版), 2018, 48(5): 1387-1397.
[12]	焦玉玲, 张鹏, 田广东, 邢小翠, 邹连慧. 基于多种群遗传算法的自动化立体库货位优化[J]. 吉林大学学报(工学版), 2018, 48(5): 1398-1404.
[13]	刘兆惠, 王超, 吕文红, 管欣. 基于非线性动力学分析的车辆运行状态参数数据特征辨识[J]. 吉林大学学报(工学版), 2018, 48(5): 1405-1410.
[14]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[15]	宗芳, 路峰瑞, 唐明, 吕建宇, 吴挺. 习惯和路况对小汽车出行路径选择的影响[J]. 吉林大学学报(工学版), 2018, 48(4): 1023-1028.