随机交通网络最小条件风险路径问题

doi:10.3969/j.issn.1674-0696.2019.05.18

摘要/Abstract

摘要： 为了研究风险性对于拥挤交通网络车辆的路径选择行为的影响，定义条件风险值为路径目标函数，建立随机交通网络环境下最小条件风险路径问题数学模型，证明了路径的条件风险值的次可加性，把最小条件风险路径问题转化为基于路段的最小条件风险路径问题，构造基于动态规划的标号算法求解该问题，针对Sioux Falls Network展开数值试验，对在不同风险置信水平条件下随机交通网络最小条件风险路径的计算结果进行了比较分析。结果表明：不同风险置信水平条件下求解的最小条件风险路径是不同的，风险置信水平对最优路径的选择具有重大影响。

关键词: 交通运输工程, 随机网络, 最优路径, 条件风险值, 标号算法

Abstract: In order to study the impact of risk on vehicle routing choice behavior in congested traffic network, the mathematical model of conditional value-at-risk shortest path problem in stochastic traffic network was established through defining the conditional value-at-risk as the objective function of path. The subadditivity of conditional value-at-risk of path was proved, and the conditional value-at-risk shortest path problem was transformed into the conditional value-at-risk shortest path problem based on road segments. A labeling algorithm based on dynamic programming was constructed to solve the problem. Based on the numerical experiments of Sioux Falls network, the calculation results of the conditional value-at-risk shortest path in stochastic traffic network under different risk confidence levels were compared and analyzed. Numerical results show that the conditional value-at-risk shortest path obtaining under different risk confidence levels is different, and the level of risk confidence has a significant impact on the choice of the optimal path.

Key words: traffic and transportation engineering, stochastic network, optimal path, conditional value-at-risk, labeling algorithm

中图分类号:

U491.1+3

潘义勇，陈璐，丁袁. 随机交通网络最小条件风险路径问题[J]. 重庆交通大学学报（自然科学版）, 2019, 38(05): 102-107.

PAN Yiyong, CHEN Lu, DING Yuan. Conditional Value-at-Risk Shortest Path in Stochastic Traffic Network[J]. Journal of Chongqing Jiaotong University(Natural Science), 2019, 38(05): 102-107.

参考文献

［1］〖ZK(#〗〖WB〗潘义勇, 余婷, 马健霄. 基于路段与节点的城市道路阻抗函数改进［J］ . 重庆交通大学学报 (自然科学版), 2017, 36(8): 76-81.〖DW〗PAN Yiyong, YU Ting, MA Jianxiao. Improvement of urban road impedance function based on section impedance and node impedance［J］ . Journal of Chongqing Jiaotong University (Natural Science) , 2017, 36(8): 76-81.［2］ GAO S, CHABINI I. Optimal routing policy problems in stochastic time-dependent networks［J］ . Transportation Research Part B: Methodological, 2006, 40(2): 93-122.［3］ WU, X., NIE, Y., Modeling heterogeneous risk-taking behavior in route choice: a stochastic dominance approach ［J］ . Transportation Research Part A, 2011, 45(1):896-915.［4］ BELL M G H, CASSIR C. Risk-averse user equilibrium traffic assignment: an application of game theory［J］ . Transportation Research Part B: Methodological, 2002, 36(8): 671-681.［5］ 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.［6］潘义勇, 马健霄. 随机交通网络最小期望
-均方差路径问题罚函数解法［J］ . 重庆交通大学学报 (自然科学版), 2017 (4): 98-101. 〖DW〗PANYiyong, MA Jianxiao. A penalty function algorithm for solving the mean-standard deviation shortest path problem in stochastic traffic network［J］ . Journal of Chongqing Jiaotong University(Natural Science), 2017 (4): 98-101.［7］ XING T, ZHOU X. 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.［8］潘义勇, 马健霄. 基于可靠性的随机交通网络约束最优路径问题研究［J］ . 东南大学学报（自科版）, 2017,47(6):1263-1268. 〖DW〗PAN Yiyong, MA Jianxiao. The constrained shortest path problem in stochastic traffic network based on the reliability［J］ . Journal of Southeast University (Natural Science Edition), 2017,47(6):1263-1268.［9］潘义勇, 孙璐. 随机交通网络环境下自适应最可靠路径问题［J］ . 吉林大学学报:工学版, 2014 (6): 1622-1627. 〖DW〗PAN Yiyong and SUN Lu. Adaptive reliable shortest path problem in stochastic traffic network［J］ . Journal of Jilin University (Engineering and Technolo
gy Edition), 2014 (6): 1622-1627.〖ZK)〗［10］〖ZK(#〗〖WB〗NIE Y, Wu X. Shortest path problem considering on-time arrival probability［J］ . Transportation Research Part B: Methodological, 2009, 43(6): 597-613.［11］ HOLTON olton G A. Value-at-risk: theory and practice［M］ . New York: Academic Press, 2003.［12］潘义勇, 马健霄, 孙璐. 基于可靠度的动态随机交通网络耗时最优路径［J］ . 吉林大学学报 (工学版), 2016, 46(2): 412-417.〖DW〗PAN yiyong, MA Jianxiao, Sun Lu. Optimal path in dynamic network with random link travel times based on reliability［J］ . Journal of Jilin University (Engineering and Technology Edition), 2016, 46(2): 412-417. ［1］潘义勇, 余婷, 马健霄. 基于路段与节点的城市道路阻抗函数改进［J］. 重庆交通大学学报 (自然科学版), 2017, 36(8): 76-81.
PAN Yiyong, YU Ting, MA Jianxiao. Improvement of urban road impedance function based on section impedance and node impedance［J］. Journal of Chongqing Jiaotong University (Natural Science), 2017, 36(8): 76-81.
［2］ GAO S, CHABINI I. Optimal routing policy problems in stochastic time-dependent networks ［J］.Transportation Research Part B: Methodological, 2006, 40(2): 93-122.
［3］ WU Xing, NIE Yu, Modeling heterogeneous risk-taking behavior in route choice: a stochastic dominance approach ［J］. Transportation Research Part A, 2011, 45:896-915.
［4］ BELL M G H, CASSIR C. Risk-averse user equilibrium traffic assign-
ment: an application of game theory ［J］. Transportation Research Part B: Methodological, 2002, 36(8): 671-681.
［5］ KHANI A, BOYLES S D. An exact algorithm for the mean-standard deviation shortest path problem ［J］. Transportation Research Part B: Methodological, 2015, 49(4): 252-266.
［6］潘义勇,马健霄.随机交通网络最小期望-均方差路径问题罚函数解法［J］. 重庆交通大学学报 (自然科学版), 2017, 36 (4): 96-101.
PAN Yiyong, MA Jianxiao. A penalty function algorithm for solving the mean-standard deviation shortest path problem in stochastic traffic network［J］. Journal of Chongqing Jiaotong University (Natural Science), 2017, 36 (4): 96-101.
［7］ XING T, ZHOU X. 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.
［8］潘义勇, 马健霄. 基于可靠性的随机交通网络约束最优路径问题研究［J］. 东南大学学报(自然科学版),2017,47 (6): 1263-1268.
PAN Yiyong, MA Jianxiao. The constrained shortest path problem in stochastic traffic network based on the reliability ［J］. Journal of Southeast University (Natural Science Edition), 2017, 47(6): 1263-1268.
［9］潘义勇, 孙璐. 随机交通网络环境下自适应最可靠路径问题［J］. 吉林大学学报(工学版), 2014, 44(6): 1622-1627.
PAN Yiyong, SUN Lu. Adaptive reliable shortest path problem in stoch-
astic traffic network ［J］. Journal of Jilin University (Engineering and Technology Edition), 2014, 44(6): 1622-1627.
［10］ NIE Y, WU X. Shortest path problem considering on-time arrival probability［J］. Transportation Research Part B, 2009, 43(6):597-613.
［11］ HOLTON G A. Value-at-risk: Theory and Practice ［M］. New York: Academic Press, 2003.
［12］潘义勇, 马健霄, 孙璐. 基于可靠度的动态随机交通网络耗时最优路径［J］. 吉林大学学报 (工学版), 2016, 46(2): 412 - 417.
PAN Yiyong, MA Jianxiao, SUN Lu. Optimal path in dynamic network with random link travel times based on reliability ［J］. Journal of Jilin University (Engineering and Technology Edition), 2016, 46(2): 412-417.
［13］邬岚, 陈学武, 陆涛. 基于快速公交系统不同配置的潜在客流分析［J］ . 东南大学学报(自然科学版), 2014, 44(6):1299-1303.
WU Lan, CHEN Xuewu, LU Tiao. Potential ridership analysis based on different configurations of BRT［J］ . Journal of Southeast University( Natual Science Edition), 2014, 44(6):1299-1303.

[1]	李晶1,2，钟鹏1，吕靖1,2. 基于系统动力学的陆港与城市经济互动研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 1-7.
[2]	李军1，朱云升2. 三角模糊层次分析的综合评价在黄河库区船舶安全评估中的应用[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 16-22.
[3]	邓萍1,2，宋莲1，黄承锋1,2. 三峡坝区过闸船舶拥堵成本测算及对坝区货物总价值影响研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 23-30.
[4]	程谦1 ，朱晓宁2 ，卢万胜3. 中长运距城际旅客出行方式选择行为模型——以高铁、民航为例[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 39-45.
[5]	连齐才1，李涵1，石小林1，闫章存2. 基于面板数据Mixed logit模型的自动驾驶选择行为分析[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 46-52.
[6]	戚春华，王笑男，朱守林，李航天. 基于驾驶员视觉兴趣区域的交通工程设施信息量阈值研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 53-60.
[7]	李升朝，吴越，白雪萌，王玥，张海. 基于TOPSIS与灰色关联的危货车辆违规报警研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 61-66.
[8]	杨庆芳1,2,3，王立强2，郑黎黎1,2,3，孟凡运2. 一种环形交叉口交通排放及燃油消耗模型研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(07): 67-73.
[9]	白翰，张康宇，王修光，燕翔，冯启龙. 合放交通流条件下城市交叉口通行能力研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 12-20.
[10]	张重阳,黄淑萍. 路网抗震可靠性及震后运输调度路径选择研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 43-51.
[11]	郭文文1，计明军2，祝慧灵3，周文杰2. 集装箱码头场桥调度优化模型研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(06): 66-72.
[12]	李广儒，张新，朱庆辉. 基于Adaboost的改进Elman神经网络港口吞吐量预测方法[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 1-5.
[13]	孙元广1，茧敏2，金华2，陈绍宽2. 城市轨道交通列车故障救援延误计算与仿真[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 6-12.
[14]	王宏刚1,2，白朋1，邹庆茹2，赵玲1. 地铁车辆段股道运用优化模型[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 13-18.
[15]	孙延浩1,2，张琦1,2，任禹谋1,2,3，孙鹏举4. 高速铁路列车调度员应急处置能力评价研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(05): 19-25.