Методологія вибору оптимального міського автомобільного маршруту
Анотація
Актуальність. Дослідження є принципово новим підходом до вирішення такої надзвичайно актуальної проблеми сучасності, як проблеми заторів у великих містах. Рішення зазначеної глобальної проблеми є прямим шляхом до реалізації основного завдання розумного міста.
Метою дослідження є створення базових елементів технології, які зможуть стабілізувати міський рух і привести його в якісно новий стан. Для досягнення поставленої мети були поставлені наступні завдання:
– створити модель транспортної мережі міста у вигляді орієнтованого зваженого неплоского мультиграфа з динамічно навантаженими дугами;
– активувати електронну карту міста в Центрі Керування Трафіком (ЦКТ) і за допомогою цієї карти супроводжувати кожен транспортний засіб;
– здійснювати оптимальну по часу навігацію за маршрутами для всіх транспортних засобів, які замовили такі маршрути;
– реалізувати роботу програмного алгоритму в режимі реального часу з постійним оновленням маршруту кожного супроводжуваного транспортного засобу.
Це дозволить своєчасно відслідковувати зміни у міському трафіку та вносити корективи в маршрут кожного супроводжуваного автомобіля.
Методи дослідження. Дослідження базується на використанні механізмів моделювання та роботи з різними мережами – теорії графів та алгоритму 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
Sewall J., Van den Berg J., Lin M. C., 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
Jagannathan P., Gurumoorthy S., Stateczny A., Parameshachari B. D., Sengupta J. 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
Tostes A. I. J., Duarte-Figueiredo F. de LP, Assunção R., Salles J., Loureiro A. A. F. 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
Sobral T., Galvao T., Bornes J. Visualization of Urban Mobility Data from Intelligent Transportation Systems. Sensors, Vol. 19, Issue 2, P. 332-360, 2019. https://doi.org/10.3390/s19020332
Ganzfried S., Laughlin C., Morefield C. 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
Min H.-G., Fang Y.-K., Wu X., Wu G., Zhao X. 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
Rahimipour S., Moeinfar R., Hashemi S. M. 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
Emami A., Sarvi M., Bagloee S. A. 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.
Pompigna A., Rupi F. 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
Majid H., Lu C. Karim H. 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
Kidando E., Moses R., Sando T., Ozguven E. E. 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
Pidgurska A., Nikolyuk P. Intelligent urban traffic. CERES, Vol. 6, Issue 1, P. 33-61, 2020.
Liang X., Guler Ilgin S., Gayan V. 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
Boguto D.G., Kadomskiy K.K., Nikolyuk P.K., Pidgurska A.I. 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.
Xu C., Xu J. 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.
Shu A., Xu X., Xu L., Zhang B., Liu C., Cai Y. Urban artery traffic dynamic green wave signal control system and method based on real-time traffic flow data. Pat. CN110136454 (A), China. 2019.
Zhang H., Li T., Hu H., Li L., Hao Y., Chen Q., Zhang W., Chu P., Jiang C., Zhou W. Dynamic prediction intelligent traffic management method for urban road. Pat. CN109920250(A), China. 2019.
Wang T., Hussain A., Cao Y., Sangirov G. 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
Yu H., 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
Nikolyuk P.K. A-Star algorithm. GitHub: 2022. A-Star_algorithm/Astar.java at main • npk54/A-Star_algorithm (github.com)
Pan J., Popa I. S., Zeitouni K., Borcea C. 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
Hashemi M., Karimi H. A. 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
Wenxin T., Yanhui W. 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
Sobral T., Galvao T., Bordes J. 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
Quddus M., Washington S. 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
Ma X., Li Y., Chen P. 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
Dutta P., Khatua S., Choudhuri S. 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
