Нахождение оптимального маршрута судна с использованием модифицированного алгоритма A-Star

Темой исследования является проблема прокладки безопасного маршрута судна с учетом гидрометеорологической обстановки в районе его следования. Решение задачи предлагается с использованием теории графов. Кратчайшим маршрутом при океанском переходе является дуга большого круга, вокруг которой строится граф. Узлы графа отстоят друг от друга на расстоянии 12-часового перехода судна. Для узлов графа определяется текущая и прогностическая гидрометеорологическая информация о ветре, волнении и поверхностном течении. Для решения этой задачи предлагается использовать модифицированный алгоритм A* (A-Star). В качестве эвристической функции используется не расстояние, а кратчайшее время прохождения маршрута с учетом потерь или приращения скорости из-за влияния гидрометеорологических факторов на каждом отрезке пути между соседними вершинами графа. Предлагаемый алгоритм обладает высокой скоростью нахождения оптимального пути. Проведено компьютерное моделирование, иллюстрирующее результат работы предлагаемого модифицированного алгоритма. Полученные результаты показывают возможность значительной экономии времени при плавании по оптимальному маршруту по сравнению с плаванием по дуге большого круга. Предложенный метод может быть использован для создания систем автоматизированной прокладки оптимальных маршрутов с учетом меняющихся условий окружающей среды.

1. Веремей Е. И. Алгоритмы оптимизации маршрутов движения с учетом погодных условий / Е. И. Веремей, М. В. Сотникова // International Journal of Open Information Technologies. — 2016. — Т. 4. — № 3. — С. 55–61. — EDN VOQQTD.

2. Чабак А. А. Обзор актуальных алгоритмов по оптимизации маршрутов автономных судов / А. А. Чабак // Вестник государственного университета морского и речного флота им. адмирала С. О. Макарова. — 2024. — Т. 16. — № 2. — С. 259–270. DOI: 10.21821/2309-5180-2024-16-2-259-270. — EDN BSTKWV.

3. Chen G. Research on Ship Meteorological Route Based on A-Star Algorithm / G. Chen, T. Wu, Z. Zhou // Mathematical Problems in Engineering. — 2021. — Vol. 2021. — Is. 1. — Pp. 9989731. DOI: 10.1155/2021/9989731.

4. Walther L. Modeling and Optimization Algorithms in Ship Weather Routing / L. Walther, A. Rizvanolli, M. Wendebourg, C. Jahn // International Journal of e-Navigation and Maritime Economy. — 2016. — Vol. 4. — Pp. 31–45. DOI: 10.1016/j.enavi.2016.06.004.

5. Perera L. P. Weather routing and safe ship handling in the future of shipping / L. P. Perera, C. G. Soares // Ocean Engineering. — 2017. — Vol. 130. — Pp. 684–695. DOI: 10.1016/j.oceaneng.2016.09.007.

6. Goldberg A. V. Computing the shortest path: A search meets graph theory / A. V. Goldberg, C. Harrelson // Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms — Society for Industrial and Applied Mathematics, 2005. — Pp. 156–165.

7. OpenGribs [Электронный ресурс]. — Режим доступа: https://opengribs.org (дата обращения: 29.07.2024).

8. Ocean Surface Current Analyses Real-time (OSCAR) Surface Currents [Электронный ресурс]. — Режим доступа: https://podaac.jpl.nasa.gov (дата обращения: 29.07.2024).

9. Бояринов А. М. Анализ применимости формул расчета ветро-волновых потерь скорости хода морских судов / А. М. Бояринов, А. А. Ершов, С. М. Пылаев // Вестник государственного университета морского и речного флота им. адмирала С. О. Макарова. — 2017. — Т. 9. — № 6. — С. 1168–1174. DOI: 10.21821/2309-5180-2017-9-6-1168-1174. — EDN YLUEZI.

10. Shin Y. W. Near-Optimal Weather Routing by Using Improved A* Algorithm / Y. W. Shin, M. Abebe, Y. Noh, S. Lee, I. Lee, D. Kim, J. Bae, K. C. Kim // Applied Sciences. — 2020. — Vol. 10. — Is. 17. DOI: 10.3390/app10176010.