Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2022, Vol. 56 Issue (8): 1542-1552    DOI: 10.3785/j.issn.1008-973X.2022.08.008
    
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
Download: HTML     PDF(2514KB) HTML
Export: BibTeX | EndNote (RIS)      

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 wordsintelligent transportation      optimal path planning      D*Lite algorithm      travel plan data      time varying road network     
Received: 20 August 2021      Published: 30 August 2022
CLC:  U 492.4  
Fund:  国家自然科学基金资助项目(61672002);国家铁路智能运输系统工程技术研究工程中心(中国铁道科学研究院集团有限公司)开放课题基金资助项目(RITS2021KF07)
Cite this article:

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.

URL:

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


基于出行计划数据的最优路径规划方法

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


关键词: 智能交通,  最优路径规划,  D*Lite算法,  出行计划数据,  时变路网 
Fig.1 Path planning framework based on travel plan data
Fig.2 Storage structure of road network data
Fig.3 System model of road network based on travel plan
Fig.4 Temporal and spatial relationship of vehicle routes
Fig.5 Explanation of road network weight stacking
Fig.6 Path planning algorithm flow based on travel plan data
Fig.7 Experimental road network
Fig.8 Density and speed data (partial)
Fig.9 Speed-density regression curve
Fig.10 Travel plan routes (partial)
Fig.11 Moments when vehicles leave each section (partial)
$ (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
Tab.1 Traffic density of each section in different periods
Fig.12 Path planning results of each path planning method
路径规划方法 出行路径 $ T $/s
SPP 路线1 203
RPP 路线2 189
RPTP 路线3 157
Tab.2 Cumulative travel time of each path
Fig.13 Irregular experimental road network
Fig.14 Path planning results of each path planning method
Fig.15 Travel time of each path planning method under different starting and ending points
Fig.16 Vehicles’ distance-speed relationship under different methods
Fig.17 Density-flow relationship of sections using RPTP method
[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] Xiao-gao XU,Ying-jie XIA,Si-yu ZHU,Li KUANG. Cooperative control algorithm of multi-intersection variable-direction lanes based on reinforcement learning[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(5): 987-994, 1005.
[2] CHAI An, DIAO Qian, JIANG Min. Design and development of urban intelligent traffic signal control system[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(7): 1241-1246.