吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (6): 1622-1627.doi: 10.13229/j.cnki.jdxbgxb201406014

• • 上一篇    下一篇

随机交通网络环境下自适应最可靠路径问题

潘义勇1, 2, 孙璐2, 3   

  1. 1.南京林业大学 汽车与交通工程学院;
    2.东南大学 交通学院,南京 210096;
    3.美国Catholic大学 土木工程系,美国 华盛顿特区 200064
  • 收稿日期:2013-12-25 出版日期:2014-11-01 发布日期:2014-11-01
  • 通讯作者: 孙璐(1972-),男,教授,博士生导师.研究方向:交通工程,道路工程.E-mail:sunl@cua.edu.cn
  • 作者简介:潘义勇(1980-),男,博士研究生.研究方向:交通网络最优路径.E-mail:
  • 基金资助:
    国家自然科学基金重点项目(U1134206); 国家自然科学基金外青学者项目(51250110075, 51050110143); 交通运输部西部项目(0901005C); 江苏省自然科学基金创新学者攀登计划项目(SBK200910046); 美国国家科学基金总统奖项目(CMMI-0408390); 美国国家科学基金项目(CMMI-0644552)

Adaptive reliable shortest path problem in stochastic traffic network

PAN Yi-yong1, 2, SUN Lu2, 3   

  1. 1.College of Automobile and Traffic Engineering,Nanjing Forestry University,Nanjing 210037,China;
    2.School of Transportation, Southeast University, Nanjing 210096, China;
    3.Department of Civil Engineering, The Catholic University of America, Washington DC 200064, USA
  • Received:2013-12-25 Online:2014-11-01 Published:2014-11-01

RICH HTML

0   

PDF (PC)

532

摘要： 为了研究交通网络耗时最优路径选择问题,建立了随机网络环境下自适应最可靠路径问题的数学模型。首先,建立随机网络模型反映交通网络的耗时随机特性;其次,在该网络环境下定义最可靠路径策略和最可靠状态链,并且证明最可靠状态链满足动态规划的 Bellman's准则;第三,构造基于动态规划的逐次逼近算法求解该问题,并且证明提出的逐次逼近算法是多项式时间算法;最后,编写基于MATLAB计算机语言的算法程序,并针对实际交通网络Sioux Falls (SF) network展开数值试验,计算结果验证了该算法的正确性和可行性。

关键词: 智能交通, 随机网络, 可靠性, 动态规划, 最短路

Abstract: In order to analyze the problem of selecting optimal path in traffic network, adaptive reliable shortest path problem is addressed in stochastic network. First, the mathematical model of stochastic traffic network is established to reflect the stochastic characteristic of traffic time in traffic network. Second, the optimal-reliable routing policy and optimal-reliable state chain based on reliability theory are uniformly defined in stochastic network; and the optimal-reliable state chain satisfies Bellman's principle that is the core of dynamic programming. Third, a successive approximation algorithm based on the dynamic programming is developed to solve the adaptive reliable shortest path problem in stochastic network, whose complexity is polynomial time. Finally, a computer program using Matlab language is developed to compute on the Sioux-Falls (SF) network. Numerical results in typical transportation network show the validity and feasibility of the successive approximation algorithm.

Key words: intelligent transportation, stochastic network, reliability, dynamic programming, shortest path

中图分类号: 

  • U491
[1] 黄卫,张宁. 智能交通系统理论研究与实践[M]. 南京:江苏科学技术出版社,2011.
[2] 杨兆升. 城市交通流诱导系统理论与模型[M]. 北京:人民交通出版社, 2000.
[3] Hall R W. The fastest path through a network with random time-dependent travel times[J]. Transportation Science, 1986, 20(3): 182-188.
[4] Schrank D, Lomax T. The 2012 annual urban mobility report[R]. Texas:Texas Transportation Institute, The Texas A&M University, 2012.
[5] Gao S, Chabini I. Optimal routing policy problems in stochastic time-dependent networks[J]. Transportation Research Part B: Methodological, 2006, 40(2): 93-122.
[6] Miller-Hooks E D. Adaptive least-expected time paths in stochastic, time-varying transportation and data networks[J]. Networks, 2001, 37(1): 35-52.
[7] Miller-Hooks E D, Mahmassani H S. Least expected time paths in stochastic, time-varying transportation networks[J]. Transportation Science, 2000, 34(2): 198-215.
[8] Huang H, Gao S. Optimal paths in dynamic networks with dependent random link travel times[J]. Transportation Research Part B: Methodological, 2012, 46(5): 579-598.
[9] Gao S, Huang H. Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks[J]. Transportation Research Part C: Emerging Technologies, 2012, 21(1): 196-213.
[10] Wu X, Nie Y. Modeling heterogeneous risk-taking behavior in route choice: a stochastic dominance approach[J]. Transportation Research Part A, 2011, 45(9):896-915.
[11] Miller-Hooks E D, Mahmassani H S.Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks[J]. European Journal of Operational Research, 2003, 146 (2):67-82.
[12] Miller-Hooks E D, Mahmassani H S. Least possible time paths in stochastic,time-varying transportation networks[J]. Computers & Operations Research,1998,25(12): 1107-1125.
[13] Nie Y M, Wu X. Reliable a Priori Shortest Path Problem with Limited Spatial and Temporal Dependencies[M].Transportation and traffic theory 2009: golden jubilee. Springer US, 2009: 169-195.
[14] 张志华.可靠性理论及工程应用[M]. 北京: 科学出版社, 2012.
[15] Bar-Gera H. Transportation network test problems website[EB/OL].http://www.bgu.ac.jl/~bargera/tntp/.2011-1-1/2013-12-1.
[1] 席利贺,张欣,孙传扬,王泽兴,姜涛. 增程式电动汽车自适应能量管理策略[J]. 吉林大学学报(工学版), 2018, 48(6): 1636-1644.
[2] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[3] 周炳海, 徐佳惠, 彭涛. 基于新型线边集成超市的周期性物料配送优化[J]. 吉林大学学报(工学版), 2018, 48(2): 588-595.
[4] 于繁华, 刘仁云, 张义民, 张晓丽, 孙秋成. 机械零部件动态可靠性稳健优化设计的群智能算法[J]. 吉林大学学报(工学版), 2017, 47(6): 1903-1908.
[5] 宋传学, 周放, 肖峰. 基于动态规划的复合电源能量管理优化[J]. 吉林大学学报(工学版), 2017, 47(1): 8-14.
[6] 吴娇蓉, 王宇沁, 魏明, 林彬. 路侧公交专用道设置长度对公交线路运行可靠性的影响[J]. 吉林大学学报(工学版), 2017, 47(1): 82-91.
[7] 张英芝, 刘津彤, 申桂香, 戚晓艳, 龙哲. 基于故障相关性分析的数控机床系统可靠性建模[J]. 吉林大学学报(工学版), 2017, 47(1): 169-173.
[8] 孟广伟, 冯昕宇, 周立明, 李锋. 基于降维算法的结构可靠性分析[J]. 吉林大学学报(工学版), 2017, 47(1): 174-179.
[9] 赵丁选, 王倩, 张祝新. 基于层次分析法的可拓学理论对舰载直升机可靠性的评估[J]. 吉林大学学报(工学版), 2016, 46(5): 1528-1531.
[10] 于繁华, 刘仁云, 张义民, 孙秋成, 张晓丽. 机械结构动态可靠性设计的智能计算方法[J]. 吉林大学学报(工学版), 2016, 46(4): 1269-1275.
[11] 潘义勇, 马健霄, 孙璐. 基于可靠度的动态随机交通网络耗时最优路径[J]. 吉林大学学报(工学版), 2016, 46(2): 412-417.
[12] 刘玉梅, 赵聪聪, 熊明烨, 郭文翠, 张志远. 基于物元模型的高速轨道车辆传动系可靠性评价[J]. 吉林大学学报(工学版), 2015, 45(4): 1063-1068.
[13] 徐光明, 王英姿, 史峰, 秦进. 基于出行时间可靠性的支路网络均衡分析[J]. 吉林大学学报(工学版), 2015, 45(3): 755-760.
[14] 杨兆军, 杨川贵, 陈菲, 郝庆波, 郑志同, 王松. 基于PSO算法和SVR模型的加工中心可靠性模型参数估计[J]. 吉林大学学报(工学版), 2015, 45(3): 829-836.
[15] 王晓燕，申桂香，张英芝，孙曙光，戚晓艳，荣峰. 基于故障链的复杂系统故障相关系数建模[J]. 吉林大学学报(工学版), 2015, 45(2): 442-447.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发