[1]潘义勇,马健霄.基于可靠性的随机交通网络约束最优路径问题[J].东南大学学报(自然科学版),2017,47(6):1263-1268.[doi:10.3969/j.issn.1001-0505.2017.06.028]
 Pan Yiyong,Ma Jianxiao.Constrained shortest path problem in stochastic traffic network based on reliability[J].Journal of Southeast University (Natural Science Edition),2017,47(6):1263-1268.[doi:10.3969/j.issn.1001-0505.2017.06.028]
点击复制

基于可靠性的随机交通网络约束最优路径问题()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
47
期数:
2017年第6期
页码:
1263-1268
栏目:
交通运输工程
出版日期:
2017-11-20

文章信息/Info

Title:
Constrained shortest path problem in stochastic traffic network based on reliability
作者:
潘义勇马健霄
南京林业大学汽车与交通工程学院, 南京 210037
Author(s):
Pan Yiyong Ma Jianxiao
College of Automobile and Traffic Engineering, Nanjing Forestry University, Nanjing 210037, China
关键词:
智能交通 随机网络 最优路径 资源约束 可靠性 分支定界
Keywords:
intelligent transportation stochastic network optimal path resource constraint reliability branch-and-bound
分类号:
U491
DOI:
10.3969/j.issn.1001-0505.2017.06.028
摘要:
为了仿真交通网络中资源约束条件下的路径选择行为,建立了随机交通网络约束最优路径问题数学模型并进行求解.采用期望-方差为路径目标函数,将约束最优路径问题建模为混合非线性整数约束优化问题,构造基于线性规划的分支定界算法以求解该问题.针对Sioux Falls网络展开数值试验,将无资源约束和不同资源约束条件下的交通网络最优路径计算结果进行比较分析.试验结果表明:无资源约束和有资源约束条件下交通网络中相同起迄点之间的最优值和最优路径是不同的;在不同资源上限的约束条件下,相同起迄点之间的最优值和最优路径也是不同的,约束上限值与最优值成反比例关系.交通网络中资源约束条件对最优路径的选择具有重大影响.
Abstract:
To simulate the behavior of the path choice under the resource constraints in the traffic network, the mathematical model of the constrained shortest path problem in the stochastic traffic network is established and solved. The mean-variance is defined as the objective function of the path. The constrained shortest path problem is modeled as a nonlinear mixed integer constrained optimization problem and solved by the proposed branch-and-bound algorithm based on linear programming. Numerical experiments in the Sioux Falls network are carried out, and the calculation results of the constrained shortest path without resource constraint and with different resource constraints are compared and analyzed. The experimental results show that the optimal values and the shortest paths obtained without resource constraints and with resource constraints are different. The optimal values and the shortest paths obtained with different resource constraints are also different, and the upper value of the resource constraints is in inverse proportion to the optimal value. The resource constraints have a great influence on the choice of the optimal path in the traffic network.

参考文献/References:

[1] Schrank D, Eisele B, Lomax T. TTI’s 2012 urban mobility report [EB/OL].(2012-08-01)[2016-07-10].http://www.pagregion.com/Portals/0/documents/HumanServices/2012MobilityReport.pdf.
[2] Joksch H C. The shortest route problem with constraints[J]. Journal of Mathematical Analysis and Applications, 1966, 14(2): 191-197. DOI:10.1016/0022-247x(66)90020-5.
[3] Avella P, Boccia M, Sforza A. A penalty function heuristic for the resource constrained shortest path problem[J]. European Journal of Operational Research, 2002, 142(2): 221-230. DOI:10.1016/s0377-2217(02)00262-x.
[4] 潘义勇, 余婷, 马健霄. 基于路段与节点的城市道路阻抗函数改进[J]. 重庆交通大学学报(自然科学版), 2017, 36(8): 76-81. DOI: 10.3969/j.issn.1674-0696.2017.08.14.
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. DOI:10.3969/j.issn.1674-0696.2017.08.14. (in Chinese)
[5] Pan Yiyong, Sun Lu. Characterizing heterogeneity in vehicular traffic speed using two-step cluster analysis[J]. Journal of Southeast University(English Edition), 2012, 28(4):480-484. DOI: 10.3969/j.issn.1003-7985.2012.04.019.
[6] 潘义勇. 动态随机交通网络环境下耗时最可靠路径研究[D]. 南京:东南大学交通学院, 2014.
[7] Wang L, Yang L, Gao Z. The constrained shortest path problem with stochastic correlated link travel times[J]. European Journal of Operational Research, 2016, 255(1): 43-57. DOI:10.1016/j.ejor.2016.05.040.
[8] Wu X, Nie Y. Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach[J]. Transportation Research Part A: Policy and Practice, 2011, 45(9): 896-915. DOI:10.1016/j.tra.2011.04.009.
[9] 潘义勇, 孙璐. 随机交通网络环境下自适应最可靠路径问题[J]. 吉林大学学报(工学版), 2014, 44(6): 1622-1627. DOI:10.13229/j.cnki.jdxbgxb201406014.
Pan Yiyong, Sun Lu. Adaptive reliable shortest path problem in stochastic traffic network[J]. Journal of Jilin University(Engineering and Technology Edition), 2014, 44(6): 1622-1627. DOI:10.13229/j.cnki.jdxbgxb201406014. (in Chinese)
[10] 潘义勇, 马健霄, 孙璐. 基于可靠度的动态随机交通网络耗时最优路径[J]. 吉林大学学报(工学版), 2016, 46(2): 412-417. DOI:10.13229/j.cnki.jdxbgxb201602012.
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. DOI:10.13229/j.cnki.jdxbgxb201602012. (in Chinese)
[11] 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.
[12] Khani A, Boyles S D. An exact algorithm for the mean-standard deviation shortest path problem[J]. Transportation Research Part B: Methodological, 2015, 81: 252-266. DOI:10.1016/j.trb.2015.04.002.
[13] Li W, Yang L, Wang L, et al. Eco-reliable path finding in time-variant and stochastic networks[J]. Energy, 2017, 121: 372-387. DOI:10.1016/j.energy.2017.01.008.
[14] Hillier F S. Introduction to operations research[M]. New York:Tata McGraw-Hill Education, 2012:125-156.
[15] Bar-Gera H. Transportation network test problems[EB/OL].(2013-08-01)[2016-07-10]. http://www. bgu. ac. il/bargera/tntp.

相似文献/References:

[1]江晟,王殿海,陈永恒,等.基于视频的行人运动轨迹再现与过街行为表达[J].东南大学学报(自然科学版),2012,42(6):1233.[doi:10.3969/j.issn.1001-0505.2012.06.038]
 Jiang Sheng,Wang Dianhai,Chen Yongheng,et al.Pedestrian movement trajectory reappearance and crossing feature expression based on video processing[J].Journal of Southeast University (Natural Science Edition),2012,42(6):1233.[doi:10.3969/j.issn.1001-0505.2012.06.038]
[2]宋翔,汤文成,李旭,等.基于两级滤波的车辆相对加速度估计[J].东南大学学报(自然科学版),2015,45(1):51.[doi:10.3969/j.issn.1001-0505.2015.01.010]
 Song Xiang,Tang Wencheng,Li Xu,et al.Estimation of vehicle relative acceleration based on two-level filter[J].Journal of Southeast University (Natural Science Edition),2015,45(6):51.[doi:10.3969/j.issn.1001-0505.2015.01.010]
[3]彭博,蔡晓禹,张有节,等.基于对称帧差和分块背景建模的无人机视频车辆自动检测[J].东南大学学报(自然科学版),2017,47(4):685.[doi:10.3969/j.issn.1001-0505.2017.04.010]
 Peng Bo,Cai Xiaoyu,Zhang Youjie,et al.Automatic vehicle detection from UAV videos based on symmetrical frame difference and background block modeling[J].Journal of Southeast University (Natural Science Edition),2017,47(6):685.[doi:10.3969/j.issn.1001-0505.2017.04.010]

备注/Memo

备注/Memo:
收稿日期: 2017-04-08.
作者简介: 潘义勇(1980—),男,博士,讲师,uoupanyg@163.com.
基金项目: 国家自然科学基金青年科学基金资助项目(51508280)、江苏省高等学校大学生创新创业训练计划资助项目(201610298037Z)、南京林业大学高学历人才基金资助项目(GXL2014031).
引用本文: 潘义勇,马健霄.基于可靠性的随机交通网络约束最优路径问题[J].东南大学学报(自然科学版),2017,47(6):1263-1268. DOI:10.3969/j.issn.1001-0505.2017.06.028.
更新日期/Last Update: 2017-11-20