Near-Optimal Weather Routing by Using Improved A* Algorithm
Source abstract
Abstract
With soaring oil prices worldwide, determining the most optimal routes for economical ship operation has become an important issue. Optimizing ship routes is economically important for ship operation, but it is also essential to meet the standards of environmental regulations recently imposed by the International Maritime Organization. For this purpose, various algorithms for determining ship routes have been developed to ensure the economical operation of ships via utilization of marine climate data and Automatic Identification System (AIS) data. However, such algorithms require a large amount of computational time and do not provide optimal routes because they do not consider practical operating conditions, such as weather and ocean conditions. In this study, an improved A* algorithm using AIS and weather data is proposed to overcome the limitation of the original A* algorithm, one of the most widely used path-finding algorithms. The improved A* algorithm uses an adaptive grid system that efficiently explores nodes according to map grid deformation by latitude. It finds economical routes by minimizing the estimated time of arrival generated by machine learning through 16-way node exploration. For verification of the proposed method, the original A* algorithm and improved A* algorithm were compared through a case study.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Maritime Navigation and Safety · Maritime Transport Emissions and Efficiency · Ship Hydrodynamics and Maneuverability
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Research Institute of Mechanical Technology, Pusan National University, Busan 46241, Korea
School of Mechanical Engineering, Pusan Nat’l University, Busan 46241, Korea
LabO21, Busan 48508, Korea
Department of Naval Architecture & Ocean Engineering, Pusan National University, Busan 46241, Korea
Korea Marine Equipment Research Institute, Busan 49111, Korea
Funding
Ministry of Trade, Industry & Energy (MOTIE) · National Research Foundation of Korea(NRF)
References (30)
Show source-provided references
1. Ship weather routing optimization with dynamic constraints based on reliable synchronous roll prediction10.1016/j.oceaneng.2017.12.049 ↗
2. Big AIS data based spatial-temporal analyses of ship traffic in Singapore port waters10.1016/j.tre.2017.07.011 ↗
3. Fabbri, T., and Vicen-Bueno, R. (2019). Weather-Routing System Based on METOC Navigation Risk Assessment. J. Mar. Sci. Eng., 7.10.3390/jmse7050127 ↗
4. Fuel-saving ship route using the Navy’s ensemble meteorological and oceanic forecasts
5. Zhou, P., Wang, H., and Guan, Z. (2019, January 12–14). Ship weather routing based on grid system and modified genetic algorithm. Proceedings of the 2019 IEEE 28th International Symposium on Industrial Electronics, Vancouver, BC, Canada.10.1109/ISIE.2019.8781243 ↗
6. On the fuel saving operation for coastal merchant ships using weather routing
7. Machine learning models for predicting ship main engine Fuel Oil Consumption: A comparative study10.1016/j.oceaneng.2019.106282 ↗
8. A novel, data-driven heuristic framework for vessel weather routing10.1016/j.oceaneng.2019.106887 ↗
9. An Ant Colony Algorithm for efficient ship routing10.2478/pomr-2013-0032 ↗
10. Application of Real-Coded Genetic Algorithm in Ship Weather Routing10.1017/S0373463318000048 ↗
11. Veneti, A., Konstantopoulos, C., and Pantziou, G. (2018). Evolutionary Computation for the Ship Routing Problem. Modeling, Computing and Data Handling Methodologies for Maritime Transportation, Springer.10.1007/978-3-319-61801-2_4 ↗
12. On a routing problem10.1090/qam/102435 ↗
13. Ford, L.R. (1956). Network Flow Theory, RAND Corp.
14. Moore, E.F. (1959). The Shortest Path through a Maze. Proceedings of an International Symposium on the Theory of Switching, Harvard University Press.
15. A note on two problems in connexion with graphs10.1007/BF01386390 ↗
16. AIS Based Shipping Routes Using the Dijkstra Algorithm
17. A Three-Dimensional Dijkstra’s algorithm for multi-objective ship voyage optimization10.1016/j.oceaneng.2019.106131 ↗
18. A Formal Basis for the Heuristic Determination of Minimum Cost Paths10.1109/TSSC.1968.300136 ↗
19. Stentz, A. (1997). Optimal and efficient path planning for partially known environments. Intelligent Unmanned Ground Vehicles, Springer.10.1007/978-1-4615-6325-9_11 ↗
20. Theta: Any-Angle Path Planning on Grids10.1613/jair.2994 ↗
21. Generalized best-first search strategies and the optimality of A10.1145/3828.3830 ↗
22. Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations10.1179/sre.1975.23.176.88 ↗
23. Mahmoud, H., and Akkari, N. (2016, January 12–14). Shortest path calculation: A comparative study for location-based recommender system. Proceedings of the (WSCAR 2016): 2016 World Symposium on Computer Applications & Research, Cairo, Egypt.10.1109/WSCAR.2016.16 ↗
24. Ramsay, A., and Robert, R.D. (1995). Introduction to Hyperbolic Geometry, Springer. [1st ed.].10.1007/978-1-4757-5585-5 ↗
25. Oliver, B., Jeff, T., and Fabio, R. (2009). Simplex-Tree Based Kinematics of Foldable Objects as Multi-body Systems Involving Loops. Robotics: Science and Systems IV, MIT Press.
26. Pressley, A. (2010). Elementary Differential Geometry, Springer. [2nd ed.].10.1007/978-1-84882-891-9 ↗
27. (2020, April 03). IMO. Available online: http://www.imo.org/en/OurWork/Safety/Navigation/Documents/227.pdf.
28. (2020, August 09). NOAA, Available online: https://www.ndbc.noaa.gov/waveobs.shtml.
29. Abebe, M., Shin, Y.W., Noh, Y., Lee, S., and Lee, I. (2020). Machine Learning Approaches for Ship Speed Prediction towards Energy Efficient Shipping. Appl. Sci., 10.10.3390/app10072325 ↗
30. Chen, T., and Guestrin, C. (2016, January 13–17). XGBoost: A Scalable Tree Boosting System. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, San Francisco, CA, USA.10.1145/2939672.2939785 ↗