К оценке эффективности алгоритмов погодной маршрутизации
Аннотация
В статье рассмотрены общая постановка двух базовых задач погодной маршрутизации, предложены меры оценки эффективности алгоритмов их решения, не зависящие от особенностей их реализации. Построение оптимального маршрута предполагается осуществлять в несколько этапов: генерация начального множества допустимых маршрутов, их оптимизация, выбор лучшего маршрута в соответствии с выбранным критерием. Для первого этапа исследована возможность использования варианта алгоритма А* с учетом заданного времени плавания и изменения скорости хода судна. Дискретизацию пространства поиска для третьего измерения (времени) предлагается осуществлять за счет решения оптимизационной задачи о выборе заданной скорости хода на участке маршрута. В качестве иллюстрации возможностей трехмерной версии алгоритма приведены примеры расчетов нескольких маршрутов с оценкой его эффективности в сравнении с версией алгоритма, использующей постоянную скорость хода в качестве параметра, для обоих типов задач. Показано, что возможность получения качественных экономичных маршрутов для трехмерной версии алгоритма достигается только при определенном выборе параметров, и характеризуется существенно большими вычислительными затратами. Для задачи о построении маршрутов с заданной длительностью трехмерная версия алгоритма обеспечивает лучшее качество маршрутов, но при этом также за счет роста вычислительных затрат.
Литература
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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
