Method for the reliable shortest path search in time-dependent stochastic networks and its application to GIS-based traffic control
A.A. Agafonov, V.V. Myasnikov

 

Samara State Aerospace University, Samara, Russia,
Image Processing Systems Institute, Russian Academy of Sciences, Samara, Russia

Full text of article: Russian language.

 PDF

Abstract:
A reliable shortest path problem in time-dependent stochastic networks is considered in this paper. We develop and research a method for reliable routing that uses actual and forecast information of traffic flow parameters. We compare the performance of the proposed algorithm with that of a well-known algorithm on a real traffic network in the city of Samara, Russia. On the basis of computing experiments it is shown that while being a bit more computationally challenging, the proposed method increases the possibility of successfully solving the shortest path problem in a time-dependent stochastic network.

Keywords:
reliable shortest path, adaptive routing, time-dependent network, stochastic network.

Citation:
Agafonov AA, Myasnikov VV. Method for the reliable shortest path search in time-dependent stochastic networks and its application to GIS-based traffic control. Computer Optics 2016; 40(2): 275-283. – DOI: 10.18287/2412-6179-2016-40-2-275-283.

References:

  1. Chabini I. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record 1998; 1645: 170-175.
  2. Gao S, Chabini I. Optimal routing policy problems in stochastic time-dependent networks. Transportation Research Part B 2006; 40: 93-122. DOI: 10.1016/j.trb.2005.02.001.
  3. Gao S, Huang H. Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks. Transportation Research Part C 2012; 21: 196-213. DOI: 10.1016/j.trc.2011.09.007.
  4. Nie Y, Fan Y. Arriving-on-time problem: Discrete algorithm that ensures convergence. Transportation Research Record 2006; 1964: 193-200.
  5. Dong W, Vu HL, Nazarathy Y, Vo BQ, Li M, Hoogendoorn SP. Shortest paths in Stochastic time-dependent networks with link travel time correlation. Transportation Research Record 2013; 2338: 58-64. DOI: 10.3141/2338-07.
  6. Fu L, Rilett LR. Expected shortest paths in dynamic and stochastic traffic networks. Transportation Research Part B 1998; 32(7): 499-516.
  7. Miller-Hooks ED, Mahmassani HS. Least expected time paths in stochastic, time-varying transportation networks. Transportation Science 2000; 34(2): 198-215.
  8. Hall RW. The fastest path through a network with random time-dependent travel times. Transportation Science 1986; 20(3): 182-188.
  9. Samaranayake S, Blandin S, Bayen A. A tractable class of algorithms for reliable routing in stochastic networks. Transportation Research Part C 2012; 20: 199-217. DOI: 10.1016/j.trc.2011.05.009.
  10. Fan Y, Nie Y. Optimal routing for maximizing the travel time reliability. Networks and Spatial Economics 2006; 6(3-4): 333-344. DOI: 10.1007/s11067-006-9287-6.
  11. Pan Y, Sun L, Ge M. Finding Reliable Shortest Path in Stochastic Time-dependent Network. Procedia – Social and Behavioral Sciences 2013; 96: 451-460.
  12. Wu X, Nie Y. Modeling heterogeneous risk-taking behavior in route choice: a stochastic dominance approach. Transportation Research Part A 2011; 45: 896-915. DOI: 10.1016/j.tra.2011.04.009.
  13. Nie Y, Wu X. Shortest path problem considering on-time arrival probability. Transportation Research Part B 2009; 43(6): 597-613. DOI: 10.1016/j.trb.2009.01.008.
  14. Chen BY, Lam WH, Sumalee A, Li Q, Tam ML. Reliable Shortest Path Problems in Stochastic Time-Dependent Networks. Journal of Intelligent Transportation Systems: Technology, Planning, and Operations 2014; 18(2): 177-189. DOI: 10.1080/15472450.2013.806851.
  15. Fu L. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information. Transportation Research Part B: Methodological 2001; 35(8): 749-765. DOI: 10.1016/S0191-2615(00)00019-9.
  16. Gao S, Frejinger E, Ben-Akiva M. Adaptive route choice models in stochastic time-dependent networks. Transportation Research Record 2008; 2085(1): 136-143. DOI: 10.3141/2085-15.
  17. Ji Z, Kim YS, Chen A. Multi-criterion reliable path finding in stochastic networks with correlated link costs: a simulation-based multi-criterion genetic algorithm approach (SMOGA). Expert Systems with Applications 2011; 38: 1515-1528.
  18. Agafonov A, Myasnikov V. Traffic flow forecasting algorithm based on combination of adaptive elementary predictors. Communications in Computer and Information Science 2015; 542: 163-174. DOI: 10.1007/978-3-319-26123-2_16.
© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: journal@computeroptics.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20