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

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

Цитирование:
Агафонов, А.А. Метод определения надёжного кратчайшего пути в зависящей от времени стохастической сети и его применение в геоинформационных задачах управления транспортом / А.А. Агафонов, В.В. Мясников // Компьютерная оптика. – 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