К оценке эффективности алгоритмов погодной маршрутизации

Аннотация

В статье рассмотрены общая постановка двух базовых задач погодной маршрутизации, предложены меры оценки эффективности алгоритмов их решения, не зависящие от особенностей их реализации. Построение оптимального маршрута предполагается осуществлять в несколько этапов: генерация начального множества допустимых маршрутов, их оптимизация, выбор лучшего маршрута в соответствии с выбранным критерием. Для первого этапа исследована возможность использования варианта алгоритма А* с учетом заданного времени плавания и изменения скорости хода судна. Дискретизацию пространства поиска для третьего измерения (времени) предлагается осуществлять за счет решения оптимизационной задачи о выборе заданной скорости хода на участке маршрута. В качестве иллюстрации возможностей трехмерной версии алгоритма приведены примеры расчетов нескольких маршрутов с оценкой его эффективности в сравнении с версией алгоритма, использующей постоянную скорость хода в качестве параметра, для обоих типов задач. Показано, что возможность получения качественных экономичных маршрутов для трехмерной версии алгоритма достигается только при определенном выборе параметров, и характеризуется существенно большими вычислительными затратами. Для задачи о построении маршрутов с заданной длительностью трехмерная версия алгоритма обеспечивает лучшее качество маршрутов, но при этом также за счет роста вычислительных затрат.

Сведения об авторах

Maksim Vasilevich Korovkin, Санкт-Петербургский государственный университет

доцент кафедры компьютерных технологий и систем, факультет прикладной математики - процессов управления, кандидат физико-математических наук, доцент

Sergei Vladimirovich Pogozhev, Санкт-Петербургский государственный университет

доцент кафедры компьютерных технологий и систем, факультет прикладной математики - процессов управления, кандидат физико-математических наук, доцент

Margarita Victorovna Sotnikova, Санкт-Петербургский государственный университет

профессор кафедры компьютерных технологий и систем, факультет прикладной математики - процессов управления, доктор физико-математических наук, доцент

Литература

1. Walther L., Rizvanolli A., Wendebourg M., Jahn C. Modeling and Optimization Algorithms in Ship Weather Routing. International Journal of e-Navigation and Maritime Economy. 2016; 4:31-45. (In Eng.) DOI: https://doi.org/10.1016/j.enavi.2016.06.004
2. Topaj A.G., Tarovik O.V., Bakharev A.A., Kondratenko A.A. Optimal ice routing of a ship with icebreaker assistance. Applied Ocean Research. 2019; 86:177-187. (In Eng.) DOI: https://doi.org/10.1016/j.apor.2019.02.021
3. Pennino S., Gaglione S., Innac A., Piscopo V., Scamardella A. Development of a New Ship Adaptive Weather Routing Model Based on Seakeeping Analysis and Optimization. Journal of Marine Science and Engineering. 2020; 8(4):270. (In Eng.) DOI: https://doi.org/10.3390/jmse8040270
4. Szłapczyńska J., Smierzchalski R. Multicriteria Optimisation in Weather Routing. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation. 2009; 3(4):393-400. Available at: https://www.transnav.eu/Article_Multicriteria_Optimisation_in_Weather_Routing_Szłapczyńska,12,183.html (accessed 26.04.2021). (In Eng.)
5. Sotnikova M.V., Veremey E.I., Korovkin M.V. Transoceanic routes optimization using dynamic properties of ship and weather conditions. 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA). IEEE Press, St. Petersburg, Russia; 2017. p. 1-4. (In Eng.) DOI: https://doi.org/10.1109/CNSA.2017.7974017
6. Nocedal J., Wright S.J. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Second Edition. Springer, New York, NY; 2006. 664 p. (In Eng.) DOI: https://doi.org/10.1007/978-0-387-40065-5
7. Bekker J.F., Schmid J.P. Planning the safe transit of a ship through a mapped minefield. ORiON. 2006; 22(1):1-18. (In Eng.) DOI: https://doi.org/10.5784/22-1-30
8. Korovkin M., Pogozhev S. Improving the performance of weather routing algorithms. WIT Transactions on The Built Environment. 2019; 187:57-64. (In Eng.) DOI: https://doi.org/10.2495/MT190061
9. Sotnikova M.V., Veremey E.I. Algorithms for Motion Optimization on a Given Trajectory Taking into Account Weather Forecast and Constraints. IFAC-PapersOnLine. 2018; 51(32):389-394. (In Eng.) DOI: https://doi.org/10.1016/j.ifacol.2018.11.415
10. 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; 4(2):100-107. (In Eng.) DOI: https://doi.org/10.1109/TSSC.1968.300136
11. Avgouleas K., Sclavounos P.D. Fuel-Efficient Ship Routing. NAUSIVIOS CHORA. 2014; 5:C-39. Available at: https://nausivios.hna.gr/docs/2014C.pdf (accessed 26.04.2021). (In Eng.)
12. Ming-Cheng Tsou, Hung-Chih Cheng. An Ant Colony Algorithm for efficient ship routing. Polish Maritime Research. 2013; 20(3):28-38. (In Eng.) DOI: https://doi.org/10.2478/pomr-2013-0032
13. Padhy C.P., Sen D., Bhaskaran P.K. Application of wave model for weather routing of ships in the North Indian Ocean. Natural Hazards. 2008; 44(3):373-385. (In Eng.) DOI: https://doi.org/10.1007/s11069-007-9126-1
14. Szlapczynska J. Multi-objective Weather Routing with Customised Criteria and Constraints. Journal of Navigation. 2015; 68(2):338-354. (In Eng.) DOI: https://doi.org/10.1017/S0373463314000691
15. Wei S., Zhou P. Development of a 3D Dynamic Programming Method for Weather Routing. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation. 2012; 6(1):79-85. Available at: https://www.transnav.eu/Article_Development_of_a_3D_Dynamic_Programming_Wei,21,337.html (accessed 26.04.2021). (In Eng.)
16. Bijlsma S.J. A Computational Method for the Solution of Optimal Control Problems in Ship Routing. NAVIGATION. Journal of The Institute of Navigation. 2001; 48(3):145-154. (In Eng.)
17. Fletcher R. Practical Methods of Optimization. Second Edition. John Wiley & Sons, Inc.; 2000. 456 p. (In Eng.) DOI: https://doi.org/10.1002/9781118723203
18. Fang M.-C., Lin Y.-H. The optimization of ship weather-routing algorithm based on the composite influence of multi-dynamic elements (II): Optimized routings. Applied Ocean Research. 2015; 50:130-140. (In Eng.) DOI: https://doi.org/10.1016/j.apor.2014.12.005
19. Lin Y.-H., Fang M.-C., Yeung R. The optimization of ship weather-routing algorithm based on the composite influence of multi-dynamic elements. Applied Ocean Research. 2013; 43:184-194. (In Eng.) DOI: https://doi.org/10.1016/j.apor.2013.07.010
20. Tsou M. Integration of a Geographic Information System and Evolutionary Computation for Automatic Routing in Coastal Navigation. Journal of Navigation. 2010; 63(2):323-341. (In Eng.) DOI: https://doi.org/10.1017/S0373463309990385
21. Li X., Wang H., Wu Q. Multi-objective optimization in ship weather routing. 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA). IEEE Press, St. Petersburg, Russia; 2017. pp. 1-4. (In Eng.) DOI: https://doi.org/10.1109/CNSA.2017.7973982
22. Shen Z., Wang H., Liu H. An improved A* algorithm for fuel-efficient ship weather routing. 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA). IEEE Press, St. Petersburg, Russia; 2017. p. 1-3. (In Eng.) DOI: https://doi.org/10.1109/CNSA.2017.7973983
23. Panigrahi J.K., Misra S.K., Umesh P.A. Application of Oceansat-1 MSMR analysed winds to marine navigation. International Journal of Remote Sensing. 2010; 31(10):2623-2637. (In Eng.) DOI: https://doi.org/10.1080/01431160903032919
24. Hayashi M., Ishida H. Characteristics Analysis of Weather Routing by Practical Navigators. 2006 IEEE International Conference on Systems, Man and Cybernetics. IEEE Press, Taipei, Taiwan; 2006. p. 786-790. (In Eng.) DOI: https://doi.org/10.1109/ICSMC.2006.384483
25. Vettor R., Soares C.G. Development of a ship weather routing system. Ocean Engineering. 2016; 123:1-14. (In Eng.) DOI: https://doi.org/10.1016/j.oceaneng.2016.06.035
Опубликована
2021-06-30
Как цитировать
KOROVKIN, Maksim Vasilevich; POGOZHEV, Sergei Vladimirovich; SOTNIKOVA, Margarita Victorovna. К оценке эффективности алгоритмов погодной маршрутизации. Современные информационные технологии и ИТ-образование, [S.l.], v. 17, n. 2, p. 275-284, june 2021. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/757>. Дата доступа: 12 oct. 2024 doi: https://doi.org/10.25559/SITITO.17.202102.275-284.
Раздел
Когнитивные информационные технологии в системах управления