Обзор статьи

Алгоритмы маршрутизации в дорожно-транспортной системе

УДК: 

656.022

DOI: 

10.23968/1999-5571-2021-18-2-181-188

Страницы: 

181-188

Аннотация: 

Проанализированы стандартные алгоритмы и на их основе программное обеспечение для определения оптимальных маршрутов перемещения грузов в дорожно-транспортных системах. Выявлено, что актуальным вопросом маршрутизации является решение задачи оптимизации по нескольким критериям эффективности, один из которых - сокращение объемов вычислительных процедур. Предложено оригинальное решение данной проблемы.

Список цитируемой литературы: 

  1. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959

  2. Boris V. Cherkassky, Andrew V. Goldberg, and Tomasz Radzik. Shortest paths algorithms. Mathematical Programming, Series A, 73:129-174, 1996

  3. Boris V. Cherkassky, Andrew V. Goldberg, and Craig Silverstein. Buckets, heaps, lists, and monotone priority queues. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97), pages 83-92. IEEE Computer Society Press, 1997

  4. George B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1962

  5. Eric V. Denardo and Bennett L. Fox. Shortest-route methods: 1. Reaching, pruning, and buckets. Operations Research, 27(1):161-186, 1979

  6. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Alternative routes in road networks. ACM Journal of Experimental Algorithmics, 18(1):1-17, 2013

  7. Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, July 1987

  8. Andrew V. Goldberg. A practical shortest path algorithm with linear expected time. SIAM Journal on Computing, 37:1637-1655, 2008

  9. Ulrich Meyer. Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’01), pр. 797-806, 2001

  10. Mikkel Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. In 35th ACM Symposium on Theory of Computing, pp. 149-158, New York, NY, USA, 2003. ACM

  11. Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16:87-90, 1958

  12. Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys, 46(4), 2014

  13. Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing, 73(7):940-952, 2013

  14. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning in road networks. submitted for publication, 2013

  15. Robert Geisberger and Christian Vetter. Efficient routing in road networks with turn costs. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11). Vol. 6630 of Lecture Notes in Computer Science, pp. 100-111. Springer, 2011

  16. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Hierarchical hub labelings for shortest paths. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA’12). Vol. 7501 of Lecture Notes in Computer Science, pp. 24-35. Springer, 2012

  17. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. Combining hierarchical and goal-directed speed-up techniques for Dijkstra’s algorithm. ACM Journal of Experimental Algorithmics, 15(2.3):1-31, January 2010. Special Section devoted to WEA’08

  18. Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Hub label compression. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13), volume 7933 of Lecture Notes in Computer Science, pp.18-29. Springer, 2013

  19. Терентьев А. В., Прудовский Б. Д. Методы принятия решений в условиях неопределенного состояния «внешней среды» // Транспортное планирование и моделирование: сб. тр. Междунар. науч.-практич. конф. (26-27 мая 2016). СПб.: СПбГАСУ, 2016. С. 145-149

Ключевые слова: 

Полный текст (файл): 

PDF

Авторы: 

Андреев А. Ю. Санкт-Петербургский государственный архитектурно-строительный университет Санкт-Петербург, Россия

Егоров В. Д. Санкт-Петербургский государственный архитектурно-строительный университет Санкт-Петербург, Россия

Терентьев А. В. Санкт-Петербургский государственный архитектурно-строительный университет Санкт-Петербург, Россия

Другие статьи авторов: 

Выпуск журнала

№ 2 (85) Апрель 2021