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

Previous Articles     Next Articles

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)

540

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

CLC Number: 

  • 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] XI Li-he,ZHANG Xin,SUN Chuan-yang,WANG Ze-xing,JIANG Tao. Adaptive energy management strategy for extended range electric vehicle [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1636-1644.
[2] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[3] ZHOU Bing-hai, XU Jia-hui, PENG Tao. Optimization of cyclic part feeding with novel line-integrated supermarket [J]. 吉林大学学报(工学版), 2018, 48(2): 588-595.
[4] YU Fan-hua, LIU Ren-yun, ZHANG Yi-min, ZHANG Xiao-li, SUN Qiu-cheng. Swarm intelligence algorithm of dynamic reliability-based robust optimization design of mechanic components [J]. 吉林大学学报(工学版), 2017, 47(6): 1903-1908.
[5] SONG Chuan-xue, ZHOU Fang, XIAO Feng. Energy management optimization of hybrid energy storage system (HESS) based on dynamic programming [J]. 吉林大学学报(工学版), 2017, 47(1): 8-14.
[6] WU Jiao-rong, WANG Yu-qin, WEI Ming, LIN Bin. Impact of length of road-side bus lane on bus operational reliability [J]. 吉林大学学报(工学版), 2017, 47(1): 82-91.
[7] ZHANG Ying-zhi, LIU Jin-tong, SHEN Gui-xiang, QI Xiao-yan, LONG Zhe. Reliability modeling of CNC machine tools system based on failure correlation analysis [J]. 吉林大学学报(工学版), 2017, 47(1): 169-173.
[8] MENG Guang-wei, FENG Xin-yu, ZHOU Li-ming, Li Feng. Structural reliability analysis based on dimension reduction algorithm [J]. 吉林大学学报(工学版), 2017, 47(1): 174-179.
[9] ZHOU Xi-yang, YANG Zhao-sheng, ZHANG Wei, BING Qi-chun, SHANG Qiang. Urban shortest path searching algorithm considering coordinate control of arterial intersections [J]. 吉林大学学报(工学版), 2016, 46(6): 1799-1806.
[10] ZHAO Ding-xuan, WANG Qian, ZHANG Zhu-xin. Extenics theory for reliability assessment of carrier helicopter based on analytic hierarchy process [J]. 吉林大学学报(工学版), 2016, 46(5): 1528-1531.
[11] YU Fan-hua, LIU Ren-yun, ZHANG Yi-min, SUN Qiu-cheng, ZHANG Xiao-li. Intelligent algorithm for optimized dynamic reliability design of mechanic structure [J]. 吉林大学学报(工学版), 2016, 46(4): 1269-1275.
[12] CAO Shan-shan, LEI Jun-qing. Fatigue life prediction of steel structure considering interval uncertainty [J]. 吉林大学学报(工学版), 2016, 46(3): 804-810.
[13] PAN Yi-yong, MA Jian-xiao, SUN Lu. Optimal path in dynamic network with random link travel times based on reliability [J]. 吉林大学学报(工学版), 2016, 46(2): 412-417.
[14] SI Wei, MA Biao, REN Jun-ping, WANG Hai-nian, GE-Sang Ze-ren. Analysis of asphalt pavement performance under freeze-thaw cycles using reliability method [J]. 吉林大学学报(工学版), 2016, 46(1): 126-132.
[15] LIU Yu-mei, ZHAO Cong-cong, XIONG Ming-ye, GUO Wen-cui, ZHANG Zhi-yuan. Reliability assessment of high-speed railway drivetrain based on matter-element model [J]. 吉林大学学报(工学版), 2015, 45(4): 1063-1068.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd