Multi-Objective Route Planning Model for Ocean-Going Ships Based on Bidirectional A-Star Algorithm Considering Meteorological Risk and IMO Guidelines
Source abstract
Abstract
In this study, a new route planning model is proposed to help ocean-going ships avoid dangerous weather conditions and ensure safe ship navigation. First, we integrate ocean-going ship vulnerability into the study of the influence of meteorological and oceanic factors on navigational risk. A multi-layer fuzzy comprehensive evaluation model for weather risk assessment is established. A multi-objective nonlinear route planning model is then constructed by comprehensively considering the challenges of fuel consumption, risk, and time during ship navigation. The International Maritime Organization (IMO) guidelines are highlighted as constraints in the calculations, and wind, wave, and calm water resistance to ships in the latest ITTC method is added to the fuel consumption and sailing time in the objective function. Finally, considering the large amount of data required for ocean voyages, the bidirectional A* algorithm is applied to solve the model and reduce the planning time. Furthermore, our model is applied to the case of an accident reported in the Singapore Maritime Investigation Report, and the results show that the model-planned route is very close to the original planned route using the Towing Manual, with an average fit of 98.22%, and the overall meteorological risk of the model-planned route is 11.19% smaller than the original route; our model can therefore be used to plan a safer route for the vessel. In addition, the importance of risk assessments and the IMO guidelines as well as the efficiency of the bidirectional A* algorithm were analyzed and discussed. The results show that the model effectively lowers the meteorological risk, is more efficient than the traditional route planning algorithm, and is 86.82% faster than the Dijkstra algorithm and 49.16% faster than the A* algorithm.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Maritime Navigation and Safety · Robotic Path Planning Algorithms · Maritime Ports and Logistics
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
Key Laboratory of High Impact Weather (Special), China Meteorological Administration, Changsha 410073, China
College of Meteorology and Oceanography, National University of Defense Technology, Changsha 410073, China
Funding
Humanities and Social Science Fund of Ministry of Education · the Open Project of Key Laboratory of High Impact Weather(special), China Meteorological Administration, the Open Research Fund of Key Laboratory of Water Safety for Beijing-Tianjin-Hebei Region of Ministry of Water Resources · Natural Science Foundation of Hunan Province · National Natural Science Foundation of China · Postgraduate Research & Practice Innovation Program of Jiangsu Province
References (44)
Show source-provided references
1. Wang, S., Yin, J., and Khan, R.U. (2020). The multi-state maritime transportation system risk assessment and safety analysis. Sustainability, 12.10.3390/su12145728 ↗
2. Overview of definitions of maritime safety, safety at sea, navigational safety and safety in general
3. Numerical simulation of ship navigation in rough seas based on ECMWF data10.21278/brod72102 ↗
4. Ship route and speed multi-objective optimization considering weather conditions and emission control area regulations10.1080/03088839.2020.1825853 ↗
5. Multi-criteria route planning with risk contour map for smart navigation10.1016/j.oceaneng.2018.11.050 ↗
6. Pennino, S., Gaglione, S., Innac, A., Piscopo, V., and Scamardella, A. (2020). Development of a new ship adaptive weather routing model based on seakeeping analysis and optimization. J. Mar. Sci. Eng., 8.10.3390/jmse8040270 ↗
7. A machine learning method for the evaluation of ship grounding risk in real operational conditions10.1016/j.ress.2022.108697 ↗
8. Mamenko, P., Zinchenko, S., Kobets, V., Nosov, P., and Popovych, I. (2022). Solution of the problem of optimizing route with using the risk criterion. Intellectual Systems of Decision-making and Problems of Computational Intelligence, Springer International Publishing.10.1007/978-3-030-82014-5_17 ↗
9. A comprehensive ship weather routing system using CMEMS products and A* algorithm10.1016/j.oceaneng.2022.111427 ↗
10. Voyage optimization combining genetic algorithm and dynamic programming for fuel/emissions reduction10.1016/j.trd.2020.102670 ↗
11. A novel, data-driven heuristic framework for vessel weather routing10.1016/j.oceaneng.2019.106887 ↗
12. A genetic algorithm for finding realistic sea routes considering the weather10.1007/s10732-020-09449-7 ↗
13. Application of real-coded genetic algorithm in ship weather routing10.1017/S0373463318000048 ↗
14. Algorithms for motion optimization on a given trajectory taking into account weather forecast and constraints10.1016/j.ifacol.2018.11.415 ↗
15. Zhu, Z., Li, L., Wu, W., and Jiao, Y. (2021, January 22–24). Application of improved Dijkstra algorithm in intelligent ship path planning. Proceedings of the 2021 33rd Chinese Control and Decision Conference (CCDC), Kunming, China.10.1109/CCDC52312.2021.9602021 ↗
16. AIS based shipping routes using the Dijkstra algorithm
17. Dynamic anti-collision A-star algorithm for multi-ship encounter situations10.1016/j.apor.2021.102995 ↗
18. Ship pipe route design using improved A* algorithm and genetic algorithm10.1109/ACCESS.2020.3018145 ↗
19. Shin, Y.W., Abebe, M., Noh, Y., Lee, S., Lee, I., Kim, D., Bae, J., and Kim, K.C. (2020). Near-Optimal Weather Routing by Using Improved A* Algorithm. Appl. Sci., 10.10.3390/app10176010 ↗
20. Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment10.1109/ACCESS.2021.3070054 ↗
21. Bi-directional adaptive A* algorithm toward optimal path planning for large-scale UAV under multi-constraints10.1109/ACCESS.2020.2990153 ↗
22. The value of meteorological data in marine risk assessment10.1016/j.ress.2021.107480 ↗
23. Causal links between Arctic sea ice and its potential drivers based on the rate of information transfer10.1029/2021GL095892 ↗
24. Bayesian network to predict environmental risk of a possible ship accident10.1504/IJRAM.2016.077381 ↗
25. The selection of class intervals10.2307/622195 ↗
26. Evaluation of green port factors and performance: A fuzzy AHP analysis10.1155/2014/802976 ↗
27. A survey: Fuzzify parameters and membership function in electrical applications10.1007/s40435-020-00622-1 ↗
28. MAritime RISk Assessment (MARISA), a fuzzy approach to define an individual ship risk factor10.1016/j.oceaneng.2009.07.003 ↗
29. Ship routing optimisation based on forecasted weather data and considering safety criteria10.1017/S0373463322000613 ↗
30. Energy-efficient Ship Route Optimization Considering Wind and Wave Impacts
31. Donnelly, D.J., and Neu, W.L. (2011, January 26–29). Numerical simulation of flow about a surface-effect ship. Proceedings of the 11th International Conference on Fast Sea Transportation FAST 2011, Honolulu, HI, USA.
32. ITTC (2021). Recommended Procedures and Guidelines, 7.5-04-01-01.1, Preparation, Conduct and Analysis of Speed/Power Trials, International Towing Tank Conference.
33. Regression analysis of experimental data for added resistance in waves of arbitrary heading and development of a semi-empirical formula10.1016/j.oceaneng.2020.107357 ↗
34. Performance prediction of full-scale ship and analysis by means of on-board monitoring (Part 1 ship performance prediction in actual seas)10.1007/s00773-017-0523-1 ↗
35. An Artificial Bee Colony Algorithm Based on Dynamic Penalty and Lévy Flight for Constrained Optimization Problems10.1007/s13369-017-3049-2 ↗
36. Chuang, Z., and Steen, S. (2011, January 15–17). Prediction of speed loss of a ship in waves. Proceedings of the Second International Symposium on Marine Propulsors, Hamburg, Germany.
37. Zhang, H., Tao, Y., and Zhu, W. (2023). Global Path Planning of Unmanned Surface Vehicle Based on Improved A-Star Algorithm. Sensors, 23.10.3390/s23146647 ↗
38. Discussion of goodness-of-fit index for curve regression
39. Li, H., Qian, L., Hong, M., Wang, X., and Guo, Z. (2023). An Efficient Maritime Route Planning Method Based on an Improved A* with an Adaptive Heuristic Function and Parallel Computing Structure. Appl. Sci., 13.10.3390/app131910873 ↗
40. Rough wave simulation and validation using onboard ship motion data in the Southern Hemisphere to enhance ship weather routing10.1016/j.oceaneng.2017.08.037 ↗
41. Research on ship meteorological route based on A-star algorithm
42. Meng, H., Zhi, P., Zhu, W., Qiu, H., Wang, H., and Wu, Y. (2021, January 10–12). Research on unmanned ship route planning based on the smoothed DGWW algorithm. Proceedings of the 2021 4th IEEE International Conference on Industrial Cyber-Physical Systems (ICPS), Victoria, BC, Canada.10.1109/ICPS49255.2021.9468166 ↗
43. Application of improved multi-objective ant colony optimization algorithm in ship weather routing10.1007/s11802-021-4436-6 ↗
44. Liu, C., Mao, Q., Chu, X., and Xie, S. (2019). An Improved A-Star Algorithm Considering Water Current, Traffic Separation and Berthing for Vessel Path Planning. Appl. Sci., 9.10.3390/app9061057 ↗