Метод определения надежного кратчайшего пути в зависящей от времен стохастической сети и его применение в геоинформационных задачах управления транспортом
Агафонов А.А., Мясников В.В.

 

Самарский государственный аэрокосмический университет имени академика С. П. Королёва (национальный исследовательский университет) (СГАУ), Самара, Россия,
Институт систем обработки изображений РАН, Самара, Россия

Аннотация:
Целью работы является разработка и исследование метода определения надёжного кратчайшего пути в зависящей от времени стохастической сети, учитывающего текущую и прогнозную информацию о параметрах транспортных потоков в сети, и его апробация на транспортной сети крупного мегаполиса (на примере города Самары). Разработанная модель сравнивается с известным алгоритмом. На основании проведённых вычислительных экспериментов показано, что предложенный метод при незначительном увеличении вычислительной сложности позволяет повысить вероятность успешного решения задачи определения надёжного кратчайшего пути в зависящей от времени стохастической сети.

Ключевые слова :
надёжный кратчайший путь, адаптивный маршрут, зависящая от времени сеть, стохастическая сеть.

Цитирование:
Агафонов, А.А. Метод определения надёжного кратчайшего пути в зависящей от времени стохастической сети и его применение в геоинформационных задачах управления транспортом / А.А. Агафонов, В.В. Мясников // Компьютерная оптика. – 2016. – Т. 40, № 2. – С. 275-283. – DOI: 10.18287/2412-6179-2016-40-2-275-283.

Литература:

  1. Chabini, I. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time / I. Chabini // Transportation Research Record. – 1998. – Vol. 1645. – P. 170-175.
  2. Gao, S. Optimal routing policy problems in stochastic time-dependent networks / S. Gao, I. Chabini // Transportation Research Part B. – 2006. – Vol. 40. – P. 93-122.
  3. Gao, S. Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks // S. Gao, H. Huang // Transportation Research Part C. – 2012. – Vol. 21. – P. 196-213.
  4. Nie, Y. Arriving-on-time problem: Discrete algorithm that ensures convergence / Y. Nie, Y. Fan // Transportation Research Record. – 2006. – Vol. 1964. – P. 193-200.
  5. Dong, W. Shortest paths in Stochastic time-dependent networks with link travel time correlation / W. Dong, H.L. Vu, Y. Nazarathy, B.Q. Vo, M. Li, S.P. Hoogendoorn // Transportation Research Record. – 2013. – Vol. 2338. – P. 58-64.
  6. Fu, L. Expected shortest paths in dynamic and stochastic traffic networks / L. Fu, L.R. Rilett // Transportation Research Part B. – 1998. – Vol. 32(7). – P. 499-516.
  7. Miller-Hooks, E.D. Least expected time paths in stochastic, time-varying transportation networks / E.D. Miller-Hooks, H.S. Mahmassani // Transportation Science. – 2000. – Vol. 34(2). – P. 198-215.
  8. Hall, R.W. The fastest path through a network with random time-dependent travel times / R.W. Hall // Transportation Science. – 1986. – Vol. 20(3). – P. 182-188.
  9. Samaranayake, S. A tractable class of algorithms for reliable routing in stochastic networks / S. Samaranayake, S. Blandin, A. Bayen // Transportation Research Part C. – 2012. – Vol. 20. – P. 199-217.
  10. Fan, Y. Optimal routing for maximizing the travel time reliability / Y. Fan, Y. Nie // Networks and Spatial Economics. – 2006. – Vol. 6(3-4). – P. 333-344.
  11. Pan, Y. Finding Reliable Shortest Path in Stochastic Time-dependent Network / Y. Pan, L. Sun, M. Ge // Procedia – Social and Behavioral Sciences. – 2013. – Vol. 96. – P. 451-460.
  12. Wu, X. Modeling heterogeneous risk-taking behavior in route choice: a stochastic dominance approach / X. Wu, Y. Nie // Transportation Research Part A. – 2011. – Vol. 45. – P. 896-915.
  13. Nie, Y. Shortest path problem considering on-time arrival probability / Y. Nie, X. Wu // Transportation Research Part B. – 2009. – Vol. 43(6). – P. 597-613.
  14. Chen, B.Y. Reliable Shortest Path Problems in Stochastic Time-Dependent Networks / B.Y. Chen, W.H.K. Lam, A. Sumalee, Q. Li, M.L. Tan // Journal of Intelligent Transportation Systems: Technology, Planning, and Operations. – 2014. – Vol. 18(2). – P. 177-189.
  15. Fu, L. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information / L. Fu // Transportation Research Part B: Methodological. – 2001. – Vol. 35(8). – P. 749-765.
  16. Gao, S. Adaptive route choice models in stochastic time-dependent networks / S. Gao, E. Frejinger, M. Ben-Akiva // Transportation Research Record. – 2008. – Vol. 2085(1). – P. 136-143.
  17. Ji, Z. Multi-criterion reliable path finding in stochastic networks with correlated link costs: a simulation-based multi-criterion genetic algorithm approach (SMOGA) / Z. Ji, Y.S. Kim, A. Chen // Expert Systems with Applications. – 2011. – Vol. 38. – P. 1515-1528.
  18. Agafonov, A. Traffic flow forecasting algorithm based on combination of adaptive elementary predictors / A. Agafonov, V. Myasnikov // Communications in Computer and Information Science. – 2015. – Vol. 542. – P. 163-174.

© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20