Reliable path planning model and algorithm in transportation networks with heterogeneous stochastic travel time in road links
Article Text (Baidu Translation)
-
摘要: 为应对交通网络路段随机行程时间异质性分布情况下，出行者路径选择决策对行程时间可靠性和不可靠性方面的关注，以均值-超量行程时间为优化准则，构建了一种新的可靠路径规划模型；为刻画交通网络中不同路段随机行程时间的异质性分布，以行程时间前四阶矩为输入，解析估计了均值-超量行程时间，以免于现有研究均一化的分布假设；利用均值-超量行程时间的理论特性，提出了以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.
-
图 3 Anaheim网络中路段行程时间的异质性分布
Figure 3. Heterogeneous distributions of travel time in road links in Anaheim network
图 4 OD对(327, 405)在不同α下的最短均值-超量路径
Figure 4. Shortest mean-excess paths of OD pair (327, 405) under different α
图 6 两种算法下OD对中可选路径数比值直方图
Figure 6. Histogram of ratios of available paths in OD pairs under two algorithms
表 1 偏度和峰度系数对路径METT的影响
Table 1. Influences of skewness and kurtosis coefficient on path METT
路径 不同场景下的路径METT/min 场景1：S=-0.5，M=2.0 场景2：S=2.0，M=-0.5 场景3：S=0，M=0 路径1 14.00 14.98 14.29 路径2 13.78 15.20 14.20 路径3 13.66 15.55 14.23 
下载: 导出CSV
表 2 解析估计结果对比
Table 2. Comparison of analytical estimation results
路径 路段顺序 路径均值/min METT近似值/min METT真值/min 相对误差/% 路径1 1-2-3-6-9 31.8 37.70 37.65 0.13 路径2 1-2-5-6-9 29.9 37.63 37.64 -0.03 路径3 1-2-5-8-9 28.9 38.84 38.80 0.10 路径4 1-4-5-6-9 44.6 54.89 54.87 0.04 路径5 1-4-5-8-9 43.6 55.58 55.55 0.05 路径6 1-4-7-8-9 56.7 70.70 70.64 0.08
下载: 导出CSV
表 3 可靠性概率α的敏感性分析结果
Table 3. Sensitivity analysis results of reliability probability α
α 可选路径集路径数 最短均值-超量路径(路段顺序) METT/min 0.5 4 路径1：327-328-342-354-355-356-372-388-405 113.33 0.6 5 路径1：327-328-342-354-355-356-372-388-405 116.23 0.7 6 路径2：327-341-353-354-355-356-372-388-405 119.44 0.8 9 路径2：327-341-353-354-355-356-372-388-405 123.23 0.9 11 路径2：327-341-353-354-355-356-372-388-405 129.31
下载: 导出CSV
表 4 近似和精确两阶段算法计算效率比较
Table 4. Comparison of calculation efficiencies between approximate and exact two-stage algorithms
效率 算法 节点2 节点3 节点7 节点20 节点331 平均计算时间/s K=5近似两阶段算法 0.16 0.16 0.18 0.18 0.19 K=10近似两阶段算法 0.28 0.28 0.32 0.33 0.31 K=20近似两阶段算法 0.46 0.45 0.58 0.62 0.49 精确两阶段算法 5.80 2.76 36.92 18.24 1.35 平均可选路径数 K=5近似两阶段算法 4.3 4.2 4.5 4.6 4.4 K=10近似两阶段算法 7.6 7.3 8.4 8.6 7.8 K=20近似两阶段算法 12.3 12.0 15.0 16.1 12.5 精确两阶段算法 74.5 40.4 365.4 236.9 19.6
下载: 导出CSV
-
[1] 邵虎, 林兴强, 孟强, 等. 基于出行时间可靠性的交通配流问题[J]. 管理科学学报, 2009, 12(5): 27-35. doi: 10.3321/j.issn:1007-9807.2009.05.004SHAO 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) doi: 10.3321/j.issn:1007-9807.2009.05.004 [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. doi: 10.3969/j.issn.1671-1637.2016.02.017SUN 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) doi: 10.3969/j.issn.1671-1637.2016.02.017 [4] 胡大伟, 陈希琼, 高扬. 定位-路径问题综述[J]. 交通运输工程学报, 2018, 18(1): 111-129. doi: 10.3969/j.issn.1671-1637.2018.01.011HU 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) doi: 10.3969/j.issn.1671-1637.2018.01.011 [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. doi: 10.3969/j.issn.1671-1637.2018.04.014CHEN 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) doi: 10.3969/j.issn.1671-1637.2018.04.014 [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. doi: 10.1287/trsc.35.1.37.10141 [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. doi: 10.1016/j.cor.2007.10.016 [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. doi: 10.1016/j.trb.2011.06.004 [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. doi: 10.1016/j.trb.2017.04.006 [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. doi: 10.1016/j.trb.2018.12.011 [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. doi: 10.1016/j.tre.2013.07.002 [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. doi: 10.1080/19427867.2022.2092045 [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. doi: 10.1016/j.trb.2016.12.001 [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. -
点击查看大图
图(6) / 表(4)
计量
- 文章访问数: 504
- HTML全文浏览量: 164
- PDF下载量: 145
- 被引次数: 0
