# Near-Optimal Weather Routing by Using Improved A* Algorithm
## 1 Introduction  
International oil prices have been increasing, and environmental regulations pertaining to greenhouse gas emissions have been strengthened. The International Maritime Organization (IMO) 72 nd Marine Environment Protection Committee (MEPC) proposed a greenhouse gas reduction strategy aimed at reducing ship greenhouse gas emissions by more than 40% by 2030. The 74 th MEPC proposed an agenda for measures to improve the energy efficiency of ships using the Energy Efficiency Existing Ship Index. This increased international oil prices, and stricter international regulations for greenhouse emissions have caused shipping companies to look for ways to reduce the fuel consumption of ships, and the simplest method to reduce fuel consumption is to reduce the travel distance and time by optimizing shipping routes. There have been many studies on developing optimal algorithms for finding shipping routes. The main goals of route finding can be divided into two objectives: safe operation and economical operation. For safe operation, the dynamic stability of the vessel and the possibility of collision between vessels are commonly considered. For example, [PERSON] et al. [1] proposed a multiobjective evolutionary weather routing algorithm to find routes that can simultaneously meet various IMO safety standards while considering parametric roll risk. However, the various dangerous situations that ships can encounter during operation are not only the instability of the ship itself, but also the collisions between ships. Accordingly, [PERSON] et al. [2] focused only on safety and studied the methodology that considered collision between ships by utilizing vessel density based on ship operating route information as well as the stability of the ship itself. However, the route optimization, which considers various objective functions, has some limitations because the decision made by the user must be involved. To address these problems, [PERSON] et al. [3] constructed an intuitive indexing system to select the optimal solution from among the various candidates through the multicriterion weather routing framework based on hyper-radial visualization. However, if the goal of route finding is economical operation, vessel Fuel Oil Consumption (FOC) is set as an objective function to be minimized in general cases. However, it is not easy to present FOC as an analytical formula because it is affected by various environmental factors. In some cases, there may be significant errors in the predicted results. [PERSON] et al. [4] proposed an ensemble smart voyage planning model to reduce errors in the FOC prediction model based on the US Navy Meteorological and Oceanographic forecast system. However, the methodology is limited in that it is impossible to generate a direct FOC prediction model if the FOC factor is missing from the data used. It also has a high computational demand. [PERSON] et al. [5] and [PERSON] et al. [6] also performed Estimated Time of Arrival (ETA)-based route optimization by modeling the speed of the ship. Nevertheless, sufficient accuracy is not guaranteed because the speed of the ship is affected by numerous environmental factors. Thus, the empirical-based prediction model entails unavoidable errors. To solve these problems, some studies have attempted to improve accuracy by utilizing a learning-based predictive model. [PERSON] et al. [7] produced a variety of learning-model-based regression models and analyzed the predicted accuracy of the FOC, revealing that machine-learning models perform better than traditional regression models, such as conventional linear regression. Further studies suggested a framework for high-accuracy FOC optimal weather routing using an artificial neural network [8]. Once the predictive model for fuel consumption has been defined, i.e., the objective function for ship route optimization, the optimization algorithm should be employed to find the optimal route of the ship. Among the route optimization methods, a routing algorithm based on the evolutionary algorithm is widely used.