[1]黄 森,许项东.考虑路段随机行程时间异质性的交通网络可靠路径规划模型和算法[J].交通运输工程学报,2023,23(06):257-269.[doi:10.19818/j.cnki.1671-1637.2023.06.017]
　HUANG Sen,XU Xiang-dong.Reliable path planning model and algorithm in transportation networks with heterogeneous stochastic travel time in road links[J].Journal of Traffic and Transportation Engineering,2023,23(06):257-269.[doi:10.19818/j.cnki.1671-1637.2023.06.017]
点击复制

考虑路段随机行程时间异质性的交通网络可靠路径规划模型和算法()
分享到：

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

卷:
第23卷
期数:
2023年06期
页码:
257-269
栏目:
交通运输规划与管理
出版日期:
2023-12-30

文章信息/Info

Title:
Reliable path planning model and algorithm in transportation networks with heterogeneous stochastic travel time in road links
文章编号:
1671-1637(2023)06-0257-13
作者:
黄 森; 许项东
(同济大学 道路与交通工程教育部重点实验室,上海 201804)
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
分类号:
U491.1
DOI:
10.19818/j.cnki.1671-1637.2023.06.017
文献标志码:
A
摘要:
为应对交通网络路段随机行程时间异质性分布情况下,出行者路径选择决策对行程时间可靠性和不可靠性方面的关注,以均值-超量行程时间为优化准则,构建了一种新的可靠路径规划模型; 为刻画交通网络中不同路段随机行程时间的异质性分布,以行程时间前四阶矩为输入,解析估计了均值-超量行程时间,以免于现有研究均一化的分布假设; 利用均值-超量行程时间的理论特性,提出了以Dijkstra最短路算法和K-最短路算法为基础的精确和近似两阶段算法; 以Monte Carlo模拟方法为基准,验证了基于前四阶矩的均值-超量行程时间解析估计方法的精确性; 通过求解算例网络中所有OD对的最短均值-超量路径,分析了近似两阶段算法的精确性和计算效率。研究结果表明:现有研究中常用的路段随机行程时间正态分布假设会忽略偏度和峰度系数对可靠路径选择结果的影响,而均值-超量行程时间解析估计方法所得近似值与真值的相对误差不超过0.13%; 当K-最短路算法中K为10时,近似两阶段算法求解的全网络OD对最短均值-超量路径中,有0.11%的OD对的最小均值-超量与精确两阶段算法求解结果不同,最大相对误差为3.35%; 针对由随机选择的5个节点与其他节点组成的OD对,近似两阶段算法平均计算时间与精确两阶段算法平均计算时间的比值范围为0.87%～22.96%,表明近似两阶段算法不仅保证了其求解准确性,还可有效提高计算效率; 提出的模型和算法能够接纳网络中不同路段随机行程时间分布具有异质性的现实特征,其路径规划结果能够更好地体现出行者对按时到达可靠性和迟到风险的关注诉求。
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.

相似文献/References:

[1]鲜于建川,隽志才,朱泰英.后悔理论视角下的出行选择行为[J].交通运输工程学报,2012,12(03):67.
　XIANYU Jian-chuan,JUAN Zhi-cai,ZHU Tai-ying.Travel choice behavior based on regret theory view[J].Journal of Traffic and Transportation Engineering,2012,12(06):67.
[2]赵建有,周孙锋,崔晓娟,等.基于模糊线性回归模型的公路货运量预测方法[J].交通运输工程学报,2012,12(03):80.
　ZHAO Jian-you,ZHOU Sun-feng,CUI Xiao-juan,et al.Predictive method of highway freight volume based on fuzzy linear regression model[J].Journal of Traffic and Transportation Engineering,2012,12(06):80.
[3]胡 卉,程 菱,宣登殿,等.容量限制与运输模式联合选择的综合客运枢纽布局模型[J].交通运输工程学报,2012,12(04):59.
　HU Hui,CHENG Ling,XUAN Deng-dian,et al.Comprehensive passenger hub layout model of combined selection for capacity limitation and transportation mode[J].Journal of Traffic and Transportation Engineering,2012,12(06):59.
[4]蔚欣欣,陆化普,李阳阳,等.随机供给与随机需求的交通网络设计模型[J].交通运输工程学报,2012,12(04):67.
　YU Xin-xin,LU Hua-pu,LI Yang-yang,et al.Design model of traffic network based on stochastic supply and stochastic demand[J].Journal of Traffic and Transportation Engineering,2012,12(06):67.
[5]龙雪琴,关宏志,秦焕美.城市道路最大出行距离计算模型[J].交通运输工程学报,2012,12(04):75.
　LONG Xue-qin,GUAN Hong-zhi,QIN Huan-mei.Calculation model of maximum travel distance on urban road[J].Journal of Traffic and Transportation Engineering,2012,12(06):75.
[6]张卫华,杨 博,陈俊杰.基于复杂网络的城市路网结构分析方法[J].交通运输工程学报,2012,12(05):64.
　ZHANG Wei-hua,YANG Bo,CHEN Jun-jie.Analysis method of urban road network structure based on complex network[J].Journal of Traffic and Transportation Engineering,2012,12(06):64.
[7]杨忠振,邬珊华,罗红红,等.道路网单向交通优化设计模型[J].交通运输工程学报,2012,12(05):72.
　YANG Zhong-zhen,WU Shan-hua,LUO Hong-hong,et al.Optimization design model of one-way traffic for road network[J].Journal of Traffic and Transportation Engineering,2012,12(06):72.
[8]徐亚华,冯立光.公共交通优先发展现状及战略规划[J].交通运输工程学报,2010,10(06):64.
　XU Ya-hua,FENG Li-guang.Situation and strategy planning of public transit priority development[J].Journal of Traffic and Transportation Engineering,2010,10(06):64.
[9]陈 荔,马荣国.基于支持向量机的都市圈客运量预测模型[J].交通运输工程学报,2010,10(06):75.
　CHEN Li,MA Rong-guo.Prediction model of passenger transport volume in metropolitanregion based on support vector machine[J].Journal of Traffic and Transportation Engineering,2010,10(06):75.
[10]霍娅敏,陈坚,李啸虎,等.城市建设项目交通影响后评价模型[J].交通运输工程学报,2012,12(01):79.
　HUO Ya-min,CHEN Jian,LI Xiao-hu,et al.Traffic impact post-evaluation model of urban construction project[J].Journal of Traffic and Transportation Engineering,2012,12(06):79.

备注/Memo

备注/Memo:
收稿日期:2023-06-29
基金项目:国家自然科学基金项目(72021002); 中央高校基本科研业务费专项资金项目(22120230192)
作者简介:黄 森(1992-),男,安徽阜阳人,同济大学工学博士研究生,从事交通网络可靠性研究。
导师简介:许项东(1985-),男,安徽霍山人,同济大学教授,工学博士。
更新日期/Last Update: 2023-12-30