Система пошуку оптимального маршруту для громадського транспорту: вибір і модифікація алгоритму
DOI:
https://doi.org/10.20535/1560-8956.47.2025.340182Ключові слова:
пошук маршруту, алгоритм A*, громадський транспорт, ALT- оптимізація, часові евристики, мобільні застосунки, динамічні графиАнотація
У статті розглядається задача побудови оптимального маршруту для мобільної системи управління громадським транспортом. Проаналізовано особливості реалізації маршрутизації в умовах змінного транспортного потоку, динамічних затримок, розкладів руху та потреб перевізників. Акцент зроблено на обґрунтуванні вибору алгоритму A* як базового та подальшій його адаптації до особливостей міського середовища шляхом урахування часових характеристик та орієнтирної оптимізації (ALT). Запропоновано архітектуру програмного модуля пошуку маршруту з описом ключових компонентів, алгоритмічних підходів і можливих способів удосконалення швидкодії системи.
Бібл. 5, іл. 3, табл. 1
Посилання
Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. – 1959. – Vol. 1. – P. 269-271. DOI: 10.1007/BF01386390
Hart P.E., Nilsson N.J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE Transactions on Systems Science and Cybernetics. – 1968. – Vol.4, No.2. – P. 100-107. DOI: 10.1109/TSSC.1968.300136
Goldberg A.V., Harrelson C. Computing the shortest path: A* meets graph theory // ACM-SIAM SODA. – 2005. – P. 156-165.
Bast H., Delling D., Goldberg A. et al. Route Planning in Transportation Networks // Algorithm Engineering. – 2016. – P. 19-80. DOI: 10.1007/978-3-319-49487-6_2
Gutman R. Reach-based routing: A new approach to shortest path algorithms optimized for road networks // ALENEX. – 2004. – P. 100-111.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
1.Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у нашому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована нашим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у нашому журналі.
3. Політика журналу дозволяє і заохочує розміщення рукопису роботи авторами в мережі Інтернет (наприклад, на arXiv.org або на особистих веб-сайтах). Причому рукописи статей можуть бути розміщенні у відкритих архівах як до подання рукопису до редакції, так і під час його редакційного опрацювання. Це сприяє виникненню продуктивної наукової дискусії, позитивно позначається на оперативності ознайомлення наукової спільноти з результатами Ваших досліджень і як наслідок на динаміці цитування вже опублікованої у журналі роботи. Детальніше про це: The Effect of Open Access.
