Методологія вибору оптимального міського автомобільного маршруту
DOI:
https://doi.org/10.26565/2304-6201-2022-53-07Ключові слова:
зважений орієнтований граф, A-star алгоритм, міський трафік, затори, Центр Керування Трафіком, графова модель міської транспортної мережіАнотація
Актуальність. Дослідження є принципово новим підходом до вирішення такої надзвичайно актуальної проблеми сучасності, як проблеми заторів у великих містах. Рішення зазначеної глобальної проблеми є прямим шляхом до реалізації основного завдання розумного міста.
Метою дослідження є створення базових елементів технології, які зможуть стабілізувати міський рух і привести його в якісно новий стан. Для досягнення поставленої мети були поставлені наступні завдання:
– створити модель транспортної мережі міста у вигляді орієнтованого зваженого неплоского мультиграфа з динамічно навантаженими дугами;
– активувати електронну карту міста в Центрі Керування Трафіком (ЦКТ) і за допомогою цієї карти супроводжувати кожен транспортний засіб;
– здійснювати оптимальну по часу навігацію за маршрутами для всіх транспортних засобів, які замовили такі маршрути;
– реалізувати роботу програмного алгоритму в режимі реального часу з постійним оновленням маршруту кожного супроводжуваного транспортного засобу.
Це дозволить своєчасно відслідковувати зміни у міському трафіку та вносити корективи в маршрут кожного супроводжуваного автомобіля.
Методи дослідження. Дослідження базується на використанні механізмів моделювання та роботи з різними мережами – теорії графів та алгоритму A-star. Останній простежує маршрут на графіку (транспортній мережі) між двома обраними позиціями транспортного засобу – початковою та кінцевою. Дослідження використовує евристичний алгоритм A-star – потужний обчислювальний метод теорії графів. Це дає змогу синхронізувати транспортні потоки, а тому міський рух виходить на якісно новий рівень.
Результати. Для навігації по маршруту транспортного засобу в мегаполісі вирішено проблему реєстрації транспортного навантаження транспортної мережі міста. Дані про рух реальної транспортної мережі відтворюються на електронній карті міста. Кожен транспортний засіб отримує унікальний маркер, що складається з пари «пункт відправлення - пункт призначення». Кожна така пара відстежується на електронній карті міста. Оскільки кожен транспортний засіб знаходиться під контролем ЦКТ, є можливість супроводжувати його по оптимальному маршруту з урахуванням міської динаміки руху. Підтримка надається через канал General Parket Radio Service (GPRS), який дозволяє кожному водієві отримувати інструкції щодо оптимального маршруту руху.
Висновки. У дослідженні запропоновано робочий програмний модуль, який забезпечує навігацію за оптимальними по часу маршрутами на графі, який є моделлю реальної транспортної мережі міста.
Посилання
J. Sewall, J. van den Berg, M. C. Lin, D. Manocha, “Virtualized Traffic: Reconstructing Traffic Flows from Discrete Spatiotemporal Data”. IEEE Transactions on Visualization and Computer Graphics, Vol. 17, Issue 1, P. 26-37, 2011. https://doi.org/10.1109/tvcg.2010.27
P. Jagannathan, S. Gurumoorthy, A. Stateczny, B. D. Parameshachari, J. Sengupta, “Collision-Aware Routing Using Multi-Objective Seagull Optimization Algorithm for WSN-Based IoT”. Sensors, Vol. 21, Issue 4, P. 8496- 8520, 2021. https://doi.org/10.3390/s21248496
A. I. J. Tostes, F. de LP Duarte-Figueiredo, R. Assunção, J. Salles, A. A. F. Loureiro, “From data to knowledge: City-wide Traffic Flows Analysis and Prediction Using Bing Maps”. “UrbComp '13: Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing, Vol. 12, P. 1-8, 2013. https://doi.org/10.1145/2505821.2505831
T.Sobral, T. Galvao, J. Bornes, “Visualization of Urban Mobility Data from Intelligent Transportation Systems”. Sensors, Vol. 19, Issue 2, P. 332-360, 2019. https://doi.org/10.3390/s19020332
S.Ganzfried, C. Laughlin, C. Morefield, “Parallel Algorithm for Nash Equilibrium in Multiplayer Stochastic Games with Application to Naval Strategic Planning” International Conference on Distributed Artificial Intelligence, P. 1-13, 2020. https://doi.org/10.1007/978-3-030-64096-5_1
H.-G. Min, Y.-K. Fang, X. Wu, G. Wu, X. Zhao, “On-ramp merging strategy for connected and automated vehicles based on complete information static game”. Journal of Traffic and Transportation Engineering (English Edition), Vol. 8, Issue 4, P. 582-595, 2021. https://doi.org/10.1016/j.jtte.2021.07.003
S. Rahimipour, R. Moeinfar, S. M. Hashemi, “Traffic prediction using a self-adjusted evolutionary neural network”, J. Mod. Transport, Vol. 27, P. 306–316. 2019. http://dx.doi.org/10.1016/j.trc.2015.02.2019
A. Emami, M. Sarvi, S. A. Bagloee, “Using Kalman filter algorithm for short-term traffic flow prediction in a connected vehicle environment”. J. Modern Transport, Vol. 27, P. 222 – 232, 2019. http://dx.doi.org/10.1155/2017/8241932.
A. Pompigna, F. Rupi, “Comparing practice-ready forecast models for weekly and monthly fluctuations of average daily traffic and enhancing accuracy by weighting methods”. Journal of Traffic and Transportation Engineering (English Edition), Vol. 5, Issue 4, 239-253, 2018. https://doi.org/10.1016/j.jtte.2018.01.002
H. Majid, C. Lu, H. Karim, “An integrated approach for dynamic traffic routing and ramp metering using sliding mode control”. Journal of Traffic and Transportation Engineering (English Edition), Vol. 5, Issue 2, P. 116-128, 2018. https://doi.org/10.1016/j.jtte.2017.08.002
E. Kidando, R. Moses, T. Sando, E. E. Ozguven, “An application of Bayesian multilevel model to evaluate variations in stochastic and dynamic transition of traffic conditions”. Journal of Modern Transportation, Vol. 27 Issue 4, P. 235–249, 2019. https://doi.org/10.1007/s40534-019-00199-2
A. Pidgurska, P. Nikolyuk, “Intelligent urban traffic”. CERES, Vol. 6, Issue 1, P. 33-61, 2020.
X. Liang, S. Guler Ilgin, V. Gayan, “An equtable traffic signal control scheme at isolated intersections using Connected Vehicle technology”. Transportation Research Part C, V. 110, P. 81-97. 2020. https://doi.org/10.1016/j.trc.2019.11.005
D.G. Boguto, K.K. Kadomskiy, P.K. Nikolyuk, A.I. Pidgurska, “Algorithm of intelligent urban traffic”. Bulletin of V. Karazin Kharkiv National University, Series "Mathematical Modeling. Information Technology. Automated Control System, V. 42, P. 12 – 25. 2019.
C. Xu, J. Xu, “Intelligent terminal based intelligent traffic light system and method”. Pat. CN104575066, China. 2015.
C. Xu, J. Xu, “A kind of intelligent transportation road capacity note broadcasting system”. Pat. CN104064049B, China. 2017.
A. Shu, X. Xu, L. Xu, B. Zhang, C. Liu, Y. Cai, “Urban artery traffic dynamic green wave signal control system and method based on real-time traffic flow data”. Pat. CN110136454 (A), China. 2019.
H. Zhang, T. Li, H. Hu, L. Li, Y. Hao, Q. Chen, W. Zhang, P. Chu, C. Jiang, W. Zhou, “Dynamic prediction intelligent traffic management method for urban road”. Pat. CN109920250(A), China. 2019.
T. Wang, A. Hussain, Y. Cao, G. Sangirov, “An improved channel estimation technique for IEEE 802.11p standard in vehicular communications”. Sensors, Vol. 19, Issue 1, P. 98. 2019. https://doi.org/10.3390/s19010098
H. Yu, R. Jiang, Z. Zheng, L. Li, R. Liu, X. Chen, “Automated vehicle-involved traffic flow studies: A survey of assumptions, models, speculations, and perspectives”. Transportation Research Part C, Vol. 127, 2021. https://doi.org/10.1016/j.trc.2021.103101
P.K.Nikolyuk, “A-Star algorithm”. GitHub: 2022. A-Star_algorithm/Astar.java at main • npk54/A-Star_algorithm (github.com)
J. Pan, I. S. Popa, K. Zeitouni, C. Borcea, “Proactive vehicular traffic rerouting for lower travel time”. IEEE Transactions on Vehicular Technology, Vol. 62, Issue 8, P. 3551-3568, 2013. https://doi.org/10.1109/TVT.2013.2260422
M. Hashemi, H. A. Karimi, “A weight-based map-matching algorithm for vehicle navigation in complex urban networks”. Journal Intelligent Transportation Systems: Technology, Planning, and Operations, Vol. 20, Issue 6, P. 573-590, 2016. URL: https://doi.org/10.1080/15472450.2016.1166058
T. Wenxin, W. Yanhui, “Real-Time Map Matching: A New Algorithm Integrating Spatio-Temporal Proximity and Improved Weighted Circle”. Open Geosciences, Vol. 11, Issue 1, P. 288-297, 2019. URL: https://doi.org/10.1515/geo-2019-0023
T. Sobral, T. Galvao, J. Bordes, “Visualization of Urban Mobility Data from Intelligent Transportation Systems”. Sensors, Vol. 19, Issue 2, P. 332-350, 2019. URL: https://doi.org/10.3390/s19020332
M. Quddus, S. Washington, “Shortest path and vehicle trajectory aided map-matching for low frequency GPS data”. Transportation Research Part C: Emerging Technologies, Vol. 55, P. 328-339, 2015. URL: https://doi.org/10.1016/j.trc.2015.02.017
X. Ma, Y. Li, P. Chen, “Identifying spatiotemporal traffic patterns in large-scale urban road networks using a modified nonnegative matrix factorization algorithm”. Journal of Traffic and Transportation Engineering (English Edition), Vol. 7, Issue 4, pp. 529-539, 2020. URL: https://doi.org/10.1016/j.jtte.2018.12.002
P. Dutta, S. Khatua, S. Choudhuri, “DB-corouting: Density Based Coordinated Vehicle Rerouting in Smart Environment”. International journal of intelligent transportation systems research, Vol. 19, P. 539-556, 2021. URL: https://link.springer.com/article/10.1007/s13177-021-00261-6
