|Table of Contents|

Reliable path planning model and algorithm in transportation networks with heterogeneous stochastic travel time in road links(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2023年06期
Page:
257-269
Research Field:
交通运输规划与管理
Publishing date:
2023-12-30

Info

Title:
Reliable path planning model and algorithm in transportation networks with heterogeneous stochastic travel time in road links
Author(s):
HUANG Sen;  XU Xiang-dong
(Key Laboratory of Road and Traffic Engineering of Ministry of Education, Tongji University, Shanghai 201804, China)
Keywords:
transportation planning;  stochastic travel time;  heterogeneity;  reliable path planning;  mean-excess travel time;  two-stage algorithm
PACS:
U491.1
DOI:
10.19818/j.cnki.1671-1637.2023.06.017
Abstract:
In view of the concerns of travel time reliability and unreliability from travelers in path selection decisions under the heterogeneous distribution of stochastic travel time in road links in a transportation network, a new reliable path planning model was proposed with the mean-excess travel time(METT)as the optimization criterion. To characterize the heterogeneous distributions of stochastic travel times in different road links in the transportation network, the first four order moments of travel time were used as inputs to analytically estimate the METT, thus avoiding the assumption of homogenous distributions in existing studies. The exact and approximate two-stage algorithms based on the Dijkstra and K-shortest path algorithms were developed according to the theoretical properties of METT. The accuracy of the analytical estimation method of METT based on the first four order moments was verified by using the Monte Carlo simulation method as the benchmark. The accuracy and computational efficiency of the approximate two-stage algorithm were analyzed by finding the shortest mean-excess paths of all OD pairs in the test network. Research results indicate that the commonly used normal distribution assumption of stochastic travel time in road links in existing studies ignores the influences of skewness and kurtosis coefficient on the reliable path selection. The relative error between the approximated value from the analytical estimation method and the true value of the METT is not greater than 0.13%.When K is set as 10 in the K-shortest path algorithm, in the shortest mean-excess paths of OD pairs in the whole network solved by the approximate two-stage algorithm, the minimum mean-excess values of 0.11% OD pairs are different from those solved by the exact two-stage algorithm, with a maximum relative error of 3.35%. For the OD pairs composed of randomly selected five nodes and other nodes, the ratio range of average calculation time of the approximate two-stage algorithm to that of the exact two-stage algorithm is 0.87%-22.96%, indicating that the approximate two-stage algorithm can not only ensure the solution accuracy, but also can improve the calculation efficiency. The proposed model and algorithms can capture the realistic characteristics regarding the heterogeneous distributions of stochastic travel times in different road links, and the corresponding path planning results can better reflect travelers' concerns about the reliability of arriving on time and the risk of encountering delay. 4 tabs. 6 figs, 58 refs.

References:

[1] 邵 虎,林兴强,孟 强,等.基于出行时间可靠性的交通配流问题[J].管理科学学报,2009,12(5):27-35.
SHAO Hu, LIN Xing-qiang, MENG Qiang, et al. Travel time reliability-based traffic assignment problem[J]. Journal of Management Sciences in China, 2009, 12(5): 27-35.(in Chinese)
[2] 凃 强,程 琳,孙 超,等.截断随机出行时间下可靠网络均衡模型[J].东南大学学报(自然科学版),2020,50(1):175-181.
TU Qiang, CHENG Lin, SUN Chao, et al. Reliability-based network equilibrium model with truncated stochastic travel time[J]. Journal of Southeast University(Natural Science Edition), 2020, 50(1): 175-181.(in Chinese)
[3] 孙 健,张 颖,张 纯.基于驾驶人路径选择偏好的OD行程时间预测方法[J].交通运输工程学报,2016,16(2):143-149.
SUN Jian, ZHANG Ying, ZHANG Chun. Prediction method of OD travel time based on driver's route choice preference[J]. Journal of Traffic and Transportation Engineering, 2016, 16(2): 143-149.(in Chinese)
[4] 胡大伟,陈希琼,高 扬.定位-路径问题综述[J].交通运输工程学报,2018,18(1):111-129.
HU Da-wei, CHEN Xi-qiong, GAO Yang. Review on location-routing problem[J]. Journal of Traffic and Transportation Engineering, 2018, 18(1): 111-129.(in Chinese)
[5] 赵 星,吉 康,林 灏,等.基于多目标路径规划的应急资源配置模型[J].华南理工大学学报(自然科学版),2019,47(4):76-82.
ZHAO Xing, JI Kang, LIN Hao, et al. Resource allocation model based on multi-objective path planning in emergency management[J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(4): 76-82.(in Chinese)
[6] 陈喜群,刘教坤,胡浩强,等.网络行程时间可靠性评价方法与影响因素[J].交通运输工程学报,2018,18(4):132-142.
CHEN Xi-qun, LIU Jiao-kun, HU Hao-qiang, et al. Evaluation method and influence factors of network travel time reliability[J]. Journal of Traffic and Transportation Engineering, 2018, 18(4): 132-142.(in Chinese)
[7] 蒋 洋,孙会君,吴建军.不确定条件对交通网络设计的影响分析[J].交通运输系统工程与信息,2014,14(3):85-90,116.
JIANG Yang, SUN Hui-jun, WU Jian-jun. Comparative analysis of transportation network design problem under stochastic capacity[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 85-90, 116.(in Chinese)
[8] SEN S, PILLAI R, JOSHI S, et al. A mean-variance model for route guidance in advanced traveler information systems[J]. Transportation Science, 2001, 35(1): 37-49.
[9] HUSTON K R, SHIER D R. Extended dominance and a
stochastic shortest path problem[J]. Computers and Operations Research, 2009, 36(2): 584-596.
[10] XING Tao, ZHOU Xue-song. Finding the most reliable path with and without link travel time correlation: a Lagrangian substitution based approach[J]. Transportation Research Part B: Methodological, 2011, 45(10): 1660-1679.
[11] ZHANG Yu-li, SHEN M Z J, SONG Shi-ji. Lagrangian
relaxation for the reliable shortest path problem with correlated link travel times[J]. Transportation Research Part B: Methodological, 2017, 104: 501-521.
[12] ZHANG Yu-feng, KHANI A. An algorithm for reliable
shortest path problem with travel time correlations[J]. Transportation Research Part B: Methodological, 2019, 121: 92-113.
[13] SHAHABI M, UNNIKRISHNAN A, BOYLES S D. An outer approximation algorithm for the robust shortest path problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2013, 58: 52-66.
[14] SONG Mao-can, CHENG Lin. A generalized Benders decomposition approach for the mean-standard deviation shortest path problem[J]. Transportation Letters, 2023, 15(8): 823-833.
[15] KHANI A, BOYLES S D. An exact algorithm for the mean-standard deviation shortest path problem[J]. Transportation Research Part B: Methodological, 2015, 81(1): 252-266.
[16] 潘义勇,马健霄.基于可靠性的随机交通网络约束最优路径问题[J].东南大学学报(自然科学版),2017,47(6):1263-1268.
PAN Yi-yong, MA Jian-xiao. Constrained shortest path problem in stochastic traffic network based on reliability[J]. Journal of Southeast University(Natural Science Edition), 2017, 47(6): 1263-1268.(in Chinese)
[17] TAYLOR M A P. Fosgerau's travel time reliability ratio and the Burr distribution[J]. Transportation Research Part B: Methodological, 2017, 97: 50-63.
[18] YU Gang, YANG Jian. On the robust shortest path problem[J]. Computers and Operations Research, 1998, 25(6): 457-468.
[19] BERTSIMAS D, SIM M. Robust discrete optimization and network flows[J]. Mathematical Programming, 2003, 98(1): 49-71.
[20] ZHANG Yu-li, SONG Shi-ji, SHEN M Z J, et al. Robust shortest path problem with distributional uncertainty[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(4): 1080-1090.
[21] WANG Zhuo-lin, YOU Ke-you, SONG Shi-ji, et al. Wasserstein distributionally robust shortest path problem[J]. European Journal of Operational Research, 2020, 284(1): 31-43.
[22] KETKOVS S, PROKOPYEV O A, BURASHNIKOV E P. An approach to the distributionally robust shortest path problem[J]. Computers and Operations Research, 2021, 130: 105212.
[23] FRANK H. Shortest paths in probabilistic graphs[J]. Operations Research, 1969, 17(4): 583-599.
[24] CHEN A, JI Zhao-wang. Path finding under uncertainty[J]. Journal of Advanced Transportation, 2005, 39(1): 19-37.
[25] NIE Yu, WU Xing. Shortest path problem considering on-time arrival probability[J]. Transportation Research Part B: Methodological, 2009, 43(6): 597-613.
[26] MIRCHANDANI P. Shortest distance and reliability of probabilistic networks[J]. Computers and Operations Research, 1976, 3(4): 347-355.
[27] FAN Yue-yue, KALABA R E, MOORE J E. Arriving on
time[J]. Journal of Optimization Theory and Applications, 2005, 127(3): 497-513.
[28] CHEN Bi-yu, SHI Chao-yang, ZHANG Jun-long, et al. Most reliable path-finding algorithm for maximizing on-time arrival probability[J]. Transportmetrica B: Transport Dynamics, 2017, 5(3): 248-264.
[29] LEE J, JOUNG S, LEE K. A fully polynomial time approximation scheme for the probability maximizing shortest path problem[J]. European Journal of Operational Research, 2022, 300(1): 35-45.
[30] LU Jian-gang, BAN Xue-gang, QIU Zhi-jun, et al. Robust route guidance model based on advanced traveler information systems[J]. Transportation Research Record, 2005(1935): 1-7.
[31] ZHOU Zhong, CHEN A, MARTIMO M. The α-reliable mean-excess path finding model in stochastic networks[C]∥ASCE. Tenth International Conference of Chinese Transportation Professionals. Reston: ASCE, 2010: 1973-1983.
[32] CHEN Bi-yu, LAM W H K, SUMALEE A, et al. Reliable shortest path finding in stochastic networks with spatial correlated link travel times[J]. International Journal of Geographical Information Science, 2012, 26(2): 365-386.
[33] CHEN Bi-yu, LAM W H K, SUMALEE A, et al. Finding reliable shortest paths in road networks under uncertainty[J]. Networks and Spatial Economics, 2013, 13(2): 123-148.
[34] TU Qiang, CHENG Lin, YUAN Teng-fei, et al. The constrained reliable shortest path problem for electric vehicles in the urban transportation network[J]. Journal of Cleaner Production, 2020, 261: 121130.
[35] 凃 强,程 琳,林 芬,等.考虑出行者风险态度的最优路径搜索[J].吉林大学学报(工学版),2019,49(3):720-726.
TU Qiang, CHENG Lin, LIN Fen, et al. Finding shortest path considering traveler's risk attitude[J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 720-726.(in Chinese)
[36] SHEN Liang, SHAO Hu, WU Ting, et al. An energy-efficient reliable path finding algorithm for stochastic road networks with electric vehicles[J]. Transportation Research Part C: Emerging Technologies, 2019, 102: 450-473.
[37] SHEN Liang, SHAO Hu, WU Ting, et al. Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 144: 450-473.
[38] ZENG Wei-liang, MIWA T, WAKITA Y, et al. Application of Lagrangian relaxation approach to α-reliable path finding in stochastic networks with correlated link travel times[J]. Transportation Research Part C: Emerging Technologies, 2015, 56: 309-334.
[39] POLUS A. A study of travel time and reliability on arterial routes[J]. Transportation, 1979, 8(2): 141-151.
[40] FAN Yue-yue, NIE Yu. Optimal routing for maximizing the travel time reliability[J]. Networks and Spatial Economics, 2006, 6(3/4): 333-344.
[41] LO H K, LUO X W, SIU B W Y. Degradable transport
network: travel time budget of travelers with heterogeneous risk aversion[J]. Transportation Research Part B: Methodological, 2006, 40(9): 792-806.
[42] SHAO Hu, LAM W H K, MENG Qiang, et al. Demand-driven traffic assignment problem based on travel time reliability[J]. Transportation Research Record, 2006(1985): 220-230.
[43] KAPARIAS I, BELL M G H, BELZNER H. A new measure of travel time reliability for in-vehicle navigation systems[J]. Journal of Intelligent Transportation Systems, 2008, 12(4): 202-211.
[44] ZANG Zhao-qi, XU Xiang-dong, QU Kai, et al. Travel time reliability in transportation networks: a review of methodological developments[J]. Transportation Research Part C: Emerging Technologies, 2022, 143: 103866.
[45] CHEN A, ZHOU Zhong. The α-reliable mean-excess traffic equilibrium model with stochastic travel times[J]. Transportation Research Part B: Methodological, 2010, 44(4): 493-513.
[46] ROCKAFELLAR R T, URYASEV S. Optimization of conditional value-at-risk[J]. The Journal of Risk, 2000, 2(3): 21-41.
[47] ROCKAFELLAR R T, URYASEV S. Conditional value-at-risk for general loss distributions[J]. Journal of Banking and Finance, 2002, 26(7): 1443-1471.
[48] XU Xiang-dong, CHEN A, CHENG Lin, et al. Modeling
distribution tail in network performance assessment: a mean-excess total travel time risk measure and analytical estimation method[J]. Transportation Research Part B: Methodological, 2014, 66: 32-49.
[49] JING Wei-wei, XU Xiang-dong, PU Yi-chao. Route redundancy-based approach to identify the critical stations in metro networks: a mean-excess probability measure[J]. Reliability Engineering and System Safety, 2020, 204: 107204.
[50] ZHAO Hui, ZHANG Cui-ping, GAO Zi-you, et al. Risk-
based transit schedule design for a fixed route from the view of equity[J]. Journal of Transportation Engineering, 2013, 139(11): 1086-1094.
[51] 许项东.需求不确定环境下的道路网络均衡建模与系统优化[D].南京:东南大学,2012.
XU Xiang-dong. Equilibrium modeling and system-wide optimization of road networks under demand uncertainty[D]. Nanjing: Southeast University, 2012.(in Chinese)
[52] ACERBI C, TASCHE D. On the coherence of expected shortfall[J]. Journal of Banking and Finance, 2002, 26(7): 1487-1503.
[53] CORNISH E A, FISHER R A. Moments and cumulants in the specification of distributions[J]. Review of the International Statistical Institute, 1938, 5(4): 307-320.
[54] ZANG Zhao-qi, XU Xiang-dong, YANG Chao, et al. A closed-form estimation of the travel time percentile function for characterizing travel time reliability[J]. Transportation Research Part B: Methodological, 2018, 118: 228-247.
[55] 李小静,刘林忠,牟海波.基于四阶矩的路网总行程时间可靠性评价[J].交通运输系统工程与信息,2019,19(1):145-150.
LI Xiao-jing, LIU Lin-zhong, MU Hai-bo. Evaluation of road network total travel time reliability based on fourth-moment[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(1): 145-150.(in Chinese)
[56] SHEN Jin-xing, LIU Kun, MA Chang-xi, et al. Bibliometric analysis and system review of vehicle routing optimization for emergency material distribution[J]. Journal of Traffic and Transportation Engineering(English Edition), 2022, 9(6): 893-911.
[57] YEN J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716.
[58] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.

Memo

Memo:
-
Last Update: 2023-12-30