Метод определения надежного кратчайшего пути в стохастической сети с использованием параметрически заданных устойчивых распределений вероятностей
Ключевые слова:
надежный кратчайший путь, стохастическая транспортная сеть, устойчивые распределения, распределение ЛевиАннотация
Тенденция к увеличению количества транспортных средств, особенно в крупных городах, а также неспособность существующей дорожно-транспортной инфраструктуры распределять транспортные потоки, ведут к чрезмерной загрузке транспортных сетей и образованию дорожных заторов. Нерешенность данных проблем подчеркивает актуальность навигационных задач нахождения кратчайшего пути или оптимального маршрута движения. Несмотря на популярность этих задач, многие существующие коммерческие системы строят маршрут движения в детерминированных сетях, не учитывая зависящие от времени и стохастические свойства транспортных потоков. В работе рассматривается задача нахождения надежного маршрута движения в стохастической транспортной сети, максимизирующего вероятность прибытия в пункт назначения в течение заданного интервала времени. Надежный кратчайший путь учитывает дисперсию времени прохождения сегментов дорожной сети, что делает его более применимым для решения задач маршрутизации в транспортных сетях по сравнению со стандартными алгоритмами поиска кратчайшего пути, учитывающими только среднее время прохождения дорожных сегментов. Для описания времени прохождения сегментов дорожной сети предлагается использовать параметрически заданные устойчивые распределения вероятностей Леви. Использование устойчивых распределений позволяет перейти от операции вычисления свертки для определения надежности пути к пересчету параметров плотности распределения, что значительно сокращает время исполнения алгоритма. В работе решается задача нахождения адаптивного маршрута движения. Адаптивность подразумевает зависимость выбора следующего используемого дорожного сегмента от времени прибытия в вершину графа и определяется реальным состоянием дорожной сети. Экспериментальный анализ алгоритма, проведенный на крупномасштабной транспортной сети города Самара, показал, что представленный алгоритм позволяет значительно сократить время решения задачи нахождения надежного маршрута движения при незначительном увеличении времени проезда.Литература
1. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. vol. 1. no. 1. pp. 269–271.
2. Nie Y.M., Wu X. Shortest path problem considering on-time arrival probability // Transportation Research Part B: Methodological. 2009. vol. 43. no. 6. pp. 597–613.
3. Samaranayake S., Blandin S., Bayen A. A tractable class of algorithms for reliable routing in stochastic networks // Transportation Research Part C: Emerging Technologies. 2012. vol. 20. no. 1. pp. 199–217.
4. Chen P., Tong R., Lu G., Wang Y. The alpha-reliable path problem in stochastic road networks with link correlations: A moment-matching-based path finding algorithm // Expert Systems with Applications. 2018. vol. 110. pp. 20–32.
5. Hall R.W. The fastest path through a network with random time-dependent travel times // Transportation Science. 1986. vol. 20. no. 3. pp. 182–188.
6. Fu L., Rilett L. Expected shortest paths in dynamic and stochastic traffic networks // Transportation Research Part B: Methodological. 1998. vol. 32. no. 7. pp. 499–516.
7. Gao S., Chabini I. Optimal routing policy problems in stochastic time-dependent networks // Transportation Research Part B: Methodological. 2006. vol. 40. no. 2. pp. 93–122.
8. Chen A., Ji Z. Path finding under uncertainty // Journal of Advanced Transportation. 2005. vol. 39. no. 1. pp. 19–37.
9. Chen B.Y. et al. Finding reliable shortest paths in road networks under uncertainty // Networks and Spatial Economics. 2013. vol. 13. no. 2. pp. 123–148.
10. Fan Y., Nie Y. Optimal routing for maximizing the travel time reliability // Networks and Spatial Economics. 2006. vol. 6. no. 3-4. pp. 333–344.
11. Nie Y., Fan Y. Arriving-on-time problem: Discrete algorithm that ensures convergence // Transportation Research Record. 2006. vol. 1964. no. 1. pp. 193–200.
12. Chen P., Yin K., Sun J. Application of finite mixture of regression model with varying mixing probabilities to estimation of urban arterial travel times // Transportation Research Record. 2014. vol. 2442. no. 1. pp. 96–105.
13. Chen B.Y., Li Q., Lam W.H. Finding the k reliable shortest paths under travel time uncertainty // Transportation Research Part B: Methodological. 2016. vol. 94. pp. 189–203.
14. Nie Y.M., Wu X., Dillenburg J.F., Nelson P.C. Reliable route guidance: A case study from chicago // Transportation Research Part A: Policy and Practice. 2012. vol. 46. no. 2. pp. 403–419.
15. Chen B.Y. et al. Most reliable path-finding algorithm for maximizing on-time arrival probability // Transportmetrica B: Transport Dynamics. 2017. vol. 5. no. 3. pp. 253–269.
16. Cao Z. et al. Maximizing the probability of arriving on time: A practical q-learning method // Thirty-First AAAI Conference on Artificial Intelligence. 2017. pp. 4481–4487.
17. Flajolet A., Blandin S., Jaillet P. Robust adaptive routing under uncertainty // Operations Research. 2018. vol. 66. no. 1. pp. 210–229.
18. Yang L., Zhou X. Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations // Transportation Research Part B: Methodological. 2017. vol. 96. pp. 68–91.
19. Zhang Y., Khani A. An algorithm for reliable shortest path problem with travel time correlations // Transportation Research Part B: Methodological. 2019. vol. 121. pp. 92–113.
20. Agafonov A., Myasnikov V. Traffic flow forecasting algorithm based on combination of adaptive elementary predictors // International Conference on Analysis of Images, Social Network and Texts. 2015. vol. 542. pp. 163–174.
21. Агафонов А.А., Юмаганов А.С., Мясников В.В. Анализ больших данных в геоинформационной задаче краткосрочного прогнозирования параметров транспортного потока на базе метода k ближайших соседей // Компьютерная оптика. 2018. Т. 42. № 6. С. 1101–1111.
22. Агафонов А.А., Мясников В.В. Метод определения надёжного кратчайшего пути в зависящей от вермени стохастической сети и его применение в геоинформационных задачах управления транспортом // Компьютерная оптика. 2016. Т. 40. № 2. С. 275–283.
23. Samaranayake S., Blandin S., Bayen A. Speedup techniques for the stochastic on-time arrival problem // OpenAccess Series in Informatic. 2012. vol. 25. pp. 83–96.
24. Niknami M., Samaranayake S. Tractable pathfinding for the stochastic on-time arrival problem // International Symposium on Experimental Algorithms. 2016. vol. 9685. pp. 231–245.
25. Sabran G., Samaranayake S., Bayen A. Precomputation techniques for the stochastic on-time arrival problem // 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). 2014. pp. 138–146.
26. Abeydeera M., Samaranayake S. GPU parallelization of the stochastic on-time arrival problem // 2014 21st International Conference on High Performance Computing (HiPC). 2014. pp. 1–8.
2. Nie Y.M., Wu X. Shortest path problem considering on-time arrival probability // Transportation Research Part B: Methodological. 2009. vol. 43. no. 6. pp. 597–613.
3. Samaranayake S., Blandin S., Bayen A. A tractable class of algorithms for reliable routing in stochastic networks // Transportation Research Part C: Emerging Technologies. 2012. vol. 20. no. 1. pp. 199–217.
4. Chen P., Tong R., Lu G., Wang Y. The alpha-reliable path problem in stochastic road networks with link correlations: A moment-matching-based path finding algorithm // Expert Systems with Applications. 2018. vol. 110. pp. 20–32.
5. Hall R.W. The fastest path through a network with random time-dependent travel times // Transportation Science. 1986. vol. 20. no. 3. pp. 182–188.
6. Fu L., Rilett L. Expected shortest paths in dynamic and stochastic traffic networks // Transportation Research Part B: Methodological. 1998. vol. 32. no. 7. pp. 499–516.
7. Gao S., Chabini I. Optimal routing policy problems in stochastic time-dependent networks // Transportation Research Part B: Methodological. 2006. vol. 40. no. 2. pp. 93–122.
8. Chen A., Ji Z. Path finding under uncertainty // Journal of Advanced Transportation. 2005. vol. 39. no. 1. pp. 19–37.
9. Chen B.Y. et al. Finding reliable shortest paths in road networks under uncertainty // Networks and Spatial Economics. 2013. vol. 13. no. 2. pp. 123–148.
10. Fan Y., Nie Y. Optimal routing for maximizing the travel time reliability // Networks and Spatial Economics. 2006. vol. 6. no. 3-4. pp. 333–344.
11. Nie Y., Fan Y. Arriving-on-time problem: Discrete algorithm that ensures convergence // Transportation Research Record. 2006. vol. 1964. no. 1. pp. 193–200.
12. Chen P., Yin K., Sun J. Application of finite mixture of regression model with varying mixing probabilities to estimation of urban arterial travel times // Transportation Research Record. 2014. vol. 2442. no. 1. pp. 96–105.
13. Chen B.Y., Li Q., Lam W.H. Finding the k reliable shortest paths under travel time uncertainty // Transportation Research Part B: Methodological. 2016. vol. 94. pp. 189–203.
14. Nie Y.M., Wu X., Dillenburg J.F., Nelson P.C. Reliable route guidance: A case study from chicago // Transportation Research Part A: Policy and Practice. 2012. vol. 46. no. 2. pp. 403–419.
15. Chen B.Y. et al. Most reliable path-finding algorithm for maximizing on-time arrival probability // Transportmetrica B: Transport Dynamics. 2017. vol. 5. no. 3. pp. 253–269.
16. Cao Z. et al. Maximizing the probability of arriving on time: A practical q-learning method // Thirty-First AAAI Conference on Artificial Intelligence. 2017. pp. 4481–4487.
17. Flajolet A., Blandin S., Jaillet P. Robust adaptive routing under uncertainty // Operations Research. 2018. vol. 66. no. 1. pp. 210–229.
18. Yang L., Zhou X. Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations // Transportation Research Part B: Methodological. 2017. vol. 96. pp. 68–91.
19. Zhang Y., Khani A. An algorithm for reliable shortest path problem with travel time correlations // Transportation Research Part B: Methodological. 2019. vol. 121. pp. 92–113.
20. Agafonov A., Myasnikov V. Traffic flow forecasting algorithm based on combination of adaptive elementary predictors // International Conference on Analysis of Images, Social Network and Texts. 2015. vol. 542. pp. 163–174.
21. Агафонов А.А., Юмаганов А.С., Мясников В.В. Анализ больших данных в геоинформационной задаче краткосрочного прогнозирования параметров транспортного потока на базе метода k ближайших соседей // Компьютерная оптика. 2018. Т. 42. № 6. С. 1101–1111.
22. Агафонов А.А., Мясников В.В. Метод определения надёжного кратчайшего пути в зависящей от вермени стохастической сети и его применение в геоинформационных задачах управления транспортом // Компьютерная оптика. 2016. Т. 40. № 2. С. 275–283.
23. Samaranayake S., Blandin S., Bayen A. Speedup techniques for the stochastic on-time arrival problem // OpenAccess Series in Informatic. 2012. vol. 25. pp. 83–96.
24. Niknami M., Samaranayake S. Tractable pathfinding for the stochastic on-time arrival problem // International Symposium on Experimental Algorithms. 2016. vol. 9685. pp. 231–245.
25. Sabran G., Samaranayake S., Bayen A. Precomputation techniques for the stochastic on-time arrival problem // 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). 2014. pp. 138–146.
26. Abeydeera M., Samaranayake S. GPU parallelization of the stochastic on-time arrival problem // 2014 21st International Conference on High Performance Computing (HiPC). 2014. pp. 1–8.
Опубликован
2019-06-07
Как цитировать
Агафонов, А. А., & Мясников, В. В. (2019). Метод определения надежного кратчайшего пути в стохастической сети с использованием параметрически заданных устойчивых распределений вероятностей. Труды СПИИРАН, 18(3), 558-582. https://doi.org/10.15622/sp.2019.18.3.557-581
Раздел
Робототехника, автоматизация и системы управления
Copyright (c) 2019 Антон Александрович Агафонов, Владислав Валерьевич Мясников
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).