Please wait a minute...
浙江大学学报(工学版)  2022, Vol. 56 Issue (8): 1542-1552    DOI: 10.3785/j.issn.1008-973X.2022.08.008
土木与交通工程     
基于出行计划数据的最优路径规划方法
徐维祥1(),康楠1,徐婷2
1. 北京交通大学 交通运输学院,北京 100084
2. 清华大学 人文学院,北京 100084
Optimal path planning method based on travel plan data
Wei-xiang XU1(),Nan KANG1,Ting XU2
1. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100084, China
2. School of Humanities, Tsinghua University, Beijing 100084, China
 全文: PDF(2514 KB)   HTML
摘要:

现有基于交通流预测的路径规划方法大多使用历史或实时交通流数据,预测时效性有待提升. 针对上述问题,提出基于出行计划数据的路径规划方法(RPTP). 该方法能主动捕捉出行者的未来交通需求,为车辆提供更合理的出行路线.基于出行计划的思想,设计基于出行计划数据的路径规划整体框架;构建基于出行计划路线数据的未来时段路网密度估计算法;采用空间堆叠的方式融合未来多时段路网密度,以此为依据改进D*Lite算法的启发函数. 采用SUMO平台仿真验证,与静态路径规划方法(SPP)和滚动路径规划方法(RPP)进行对比分析.结果显示,在相同环境下RPTP方法能提高车辆的通行效率,缓解路网拥堵,有效验证了RPTP方法的优越性.

关键词: 智能交通最优路径规划D*Lite算法出行计划数据时变路网    
Abstract:

At present, the path planning methods based on short-term traffic flow prediction mostly use historical and real-time traffic flow data, and the timeliness of the prediction needs to be improved. In response to this problem, a path planning method based on travel plan data (RPTP) was proposed. The method can proactively obtain the future traffic demand of travelers and provide more reasonable routes for vehicles. Based on the idea of “travel plan”, the overall framework of optimal path planning was designed on the basis of travel plan data. An estimation algorithm was constructed to calculate the road network density in multiple future periods using the route data of the travel plan. The multi-period road network density was integrated using the spatial superposition method, based on which the heuristic function of the D*Lite algorithm was improved. Several simulation experiments were carried out using the SUMO simulation platform, and the simulation effects produced by the RPTP method were compared with that of static path planning method (SPP) and rolling path planning method (RPP) in the same condition. Experimental results show that the RPTP method can improve the traffic efficiency of the road network and alleviate the road traffic congestion, which effectively verifies the superiority of the RPTP method.

Key words: intelligent transportation    optimal path planning    D*Lite algorithm    travel plan data    time varying road network
收稿日期: 2021-08-20 出版日期: 2022-08-30
CLC:  U 492.4  
基金资助: 国家自然科学基金资助项目(61672002);国家铁路智能运输系统工程技术研究工程中心(中国铁道科学研究院集团有限公司)开放课题基金资助项目(RITS2021KF07)
作者简介: 徐维祥(1956—),男,教授,从事智能交通研究. orcid.org/0000-0002-1548-4066. E-mail: wxxu@bjtu.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
徐维祥
康楠
徐婷

引用本文:

徐维祥,康楠,徐婷. 基于出行计划数据的最优路径规划方法[J]. 浙江大学学报(工学版), 2022, 56(8): 1542-1552.

Wei-xiang XU,Nan KANG,Ting XU. Optimal path planning method based on travel plan data. Journal of ZheJiang University (Engineering Science), 2022, 56(8): 1542-1552.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2022.08.008        https://www.zjujournals.com/eng/CN/Y2022/V56/I8/1542

图 1  基于出行计划数据的路径规划框架
图 2  路网数据存储结构
图 3  基于出行计划的路网系统模型
图 4  车辆路线时空关系
图 5  路网权值堆叠示意
图 6  基于出行计划数据的路径规划算法流程
图 7  实验路网
图 8  密度和速度数据(部分)
图 9  速度-密度回归曲线
图 10  出行计划路线(部分)
图 11  车辆离开各路段的时刻(部分)
$ (i,j) $ $ {k_{ij}}(n) $/(辆?km?1) $ (i,j) $ $ {k_{ij}}(n) $/(辆?km?1)
0~100 s 100~200 s 0~100 s 100~200 s
(0, 3) 32. 87 14. 12 (3, 0) 7. 65 14. 72
(1, 4) 3. 70 24. 56 (4, 1) 8. 15 11. 46
(2, 5) 0. 98 6. 89 (5, 2) 1. 38 2. 11
(3, 4) 11. 22 29. 09 (4, 3) 8. 15 8. 13
(3, 6) 21. 67 12. 40 (6, 3) 1. 38 6. 06
(4, 5) 19. 49 17. 31 (5, 4) 1. 50 4. 26
(4, 7) 9. 76 40. 02 (7, 4) 9. 59 1. 18
(5, 8) 18. 38 25. 23 (8, 5) 16. 23 8. 57
(6, 7) 39. 61 3. 95 (7, 6) 9. 82 3. 90
(6, 9) 4. 29 19. 93 (9, 6) 3. 23 23. 09
(7, 8) 4. 81 13. 86 (8, 7) 7. 11 30. 60
(7, 10) 7. 23 4. 98 (10, 7) 10. 61 12. 37
(8, 11) 5. 90 7. 09 (11, 8) 2. 62 2. 71
表 1  不同时段各路段的车辆密度
图 12  各路径规划方法的路径规划结果
路径规划方法 出行路径 $ T $/s
SPP 路线1 203
RPP 路线2 189
RPTP 路线3 157
表 2  各出行路径的累计行程时间
图 13  不规则实验路网
图 14  各路径规划方法的路径规划结果
图 15  不同起终点下各路径规划方法的行程时间
图 16  不同方法下各车辆的距离-速度情况
图 17  不同方法下各路段的密度-流量情况
1 韩直, 徐冲聪, 韩嵩乔 基于短时交通流预测的广域动态交通路径诱导方法[J]. 交通运输系统工程与信息, 2020, 20 (1): 117- 123
HAN Zhi, XU Chong-cong, HAN Song-qiao Wide-area dynamic traffic route guidance method based on short-term traffic flow prediction[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20 (1): 117- 123
doi: 10.16097/j.cnki.1009-6744.2020.01.018
2 LIANG Z L, WAKAHARA Y Real-time urban traffic amount prediction models for dynamic route guidance systems[J]. EURASIP Journal on Wireless Communications and Networking, 2014, (1): 85- 98
3 YUAN C J, YU X X, LI D W, et al Overall traffic mode prediction by VOMM approach and AR mining algorithm with large-scale data[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20 (4): 1508- 1516
doi: 10.1109/TITS.2018.2852285
4 曹政才, 韩丁富, 王永吉 面向城市交通网络的一种新型动态路径寻优方法[J]. 电子学报, 2012, 40 (10): 2062- 2067
CAO Zheng-cai, HAN Ding-fu, WANG Yong-ji A novel dynamic path optimization method for urban traffic networks[J]. Acta Electronica Sinica, 2012, 40 (10): 2062- 2067
5 ZHU D J, DU H W, SUN Y D, et al Research on path planning model based on short-term traffic flow prediction in intelligent transportation system[J]. Sensors, 2018, 18 (12): 4275
doi: 10.3390/s18124275
6 LIEBIG T, PIATKOWSKI N, BOCKERMANN C, et al Dynamic route planning with real-time traffic predictions[J]. Information Systems, 2017, 64: 258- 265
doi: 10.1016/j.is.2016.01.007
7 郭畅. 基于VANETs的实时信息获取与交通路网负载均衡研究[D]. 上海: 东华大学, 2020.
GUO Chang. Real-time traffic information acquisition and traffic road network load balance based on vehicular ad hod networks [D]. Shanghai: Donghua University, 2020.
8 杜茂, 杨林, 金悦, 等 基于交通时空特征的车辆全局路径规划算法[J]. 汽车安全与节能学报, 2021, 12 (1): 52- 61
DU Mao, YANG Lin, JIN Yue, et al Vehicle global path planning algorithm based on spatiotemporal characteristics of traffic[J]. Journal of Automotive Safety and Energy, 2021, 12 (1): 52- 61
doi: 10.3969/j.issn.1674-8484.2021.01.005
9 LECLUYSE C, SRENSEN K, PEREMANS H A network-consistent time-dependent travel time layer for routing optimization problems[J]. European Journal of Operational Research, 2013, 226 (3): 395- 413
doi: 10.1016/j.ejor.2012.11.043
10 李妍峰, 高自友, 李军 基于实时交通信息的城市动态网络车辆路径优化问题[J]. 系统工程理论与实践, 2013, (7): 1813- 1819
LI Yan-feng, GAO Zi-you, LI Jun Vehicle routing problem in dynamic urban network with real-time traffic information[J]. System Engineering Theory and Practice, 2013, (7): 1813- 1819
doi: 10.3969/j.issn.1000-6788.2013.07.022
11 赵宏, 翟冬梅, 石朝辉 短时交通流预测模型综述[J]. 都市快轨交通, 2019, 32 (4): 50- 54
ZHAO Hong, ZHAI Dong-mei, SHI Zhao-hui Review of short-term traffic flow forecasting models[J]. Urban Rapid Rail Transit, 2019, 32 (4): 50- 54
doi: 10.3969/j.issn.1672-6073.2019.04.009
12 XU W X, GAO R X. Prediction of road conditions ahead based on travel plans [C]// 2019 IEEE 5th International Conference on Computer and Communications. Chengdu: ICCC, 2019: 262-266.
13 XU W X, ZHAO J M. Research on traffic flow time series model and shortest path algorithm of urban traffic based on travel plans [C]// 2019 International Conference on Intelligent Computing, Automation and Systems. Chongqing: IEEE, 2019: 369–373.
14 徐维祥, 于展. 一种5G车联网环境下前方道路透明化计算方法: 201911128861. 7 [P]. 2021-04-07.
15 XU W X, LI J J An improved algorithm for clustering uncertain traffic data streams based on Hadoop platform[J]. International Journal of Modern Physics B, 2019, 33 (19): 134- 142
16 徐维祥, 李娇娇. 一种基于出行计划预测未来交通拥堵状况方法及其系统: 201810240302. 4[P]. 2020-08-04.
17 中华人民共和国国务院. 国务院关于印发促进大数据发展行动纲要的通知[EB/OL]. (2015-08-31)[2021-08-25]. http://www.gov.cn/zhengce/content/2015-09/05/content_10137.htm.
18 中华人民共和国工业和信息化部. 工业和信息化部关于印发大数据产业发展规划(2016-2020年)的通知[EB/OL]. (2016-12-18)[2021-08-25]. https://wap.miit.gov.cn/zwgk/zcwj/wjfb/zh/art/2020/art_a4ea057ae84a47069933feb5bb9ba8ae.html.
19 北京市交通委员会. 北京市交通委员会关于印发《北京市交通出行数据开放管理办法(试行)》的通知[EB/OL]. (2019-11-01) [2021-08-25]. http://jtw.beijing.gov.cn/xxgk/tzgg/201912/t20191219_1287879.html.
20 ZHANG D G, CHEN L, ZHANG J, et al A multi-path routing protocol based on link lifetime and energy consumption prediction for mobile edge computing[J]. IEEE Access, 2020, 8 (1): 69058- 69071
21 ZHANG D G, CUI Y Y, ZHANG T New quantum-genetic based OLSR protocol (QG-OLSR) for mobile ad hoc network[J]. Applied Soft Computing, 2019, 80 (7): 285- 296
22 ZHANG D G, LI G, ZHENG K, et al An energy-balanced routing method based on forward-aware factor for wireless sensor networks[J]. IEEE Transactions on Industrial Informatics, 2013, 10 (1): 766- 773
23 ZHANG D G, ZHANG T, DONG Y, et al Novel optimized link state routing protocol based on quantum genetic strategy for mobile learning[J]. Journal of Network and Computer Applications, 2018, 2018 (122): 37- 49
[1] 徐小高,夏莹杰,朱思雨,邝砾. 基于强化学习的多路口可变车道协同控制方法[J]. 浙江大学学报(工学版), 2022, 56(5): 987-994, 1005.
[2] 张楠,董红召,佘翊妮. 公交专用道条件下公交车辆轨迹的Seq2Seq预测[J]. 浙江大学学报(工学版), 2021, 55(8): 1482-1489.
[3] 柴干, 赵倩, 蒋珉. 城市智能交通信号控制系统的设计与开发[J]. J4, 2010, 44(7): 1241-1246.
[4] 李威武 王慧 钱积新. 智能交通系统中路径诱导算法研究进展[J]. J4, 2005, 39(6): 819-825.
[5] 潘翔. 基于彩色信息和边缘特征的运动阴影检测[J]. J4, 2004, 38(4): 389-391.