Finding the optimal vessel route using a modified A-Star algorithm

Abstract

This paper addresses the problem of determining a safe ship route considering the hydro-meteorological conditions along the route. The solution is proposed using graph theory. The shortest route for an ocean crossing is a Great Circle, so the graph is constructed around the Great Circle. The graph nodes are spaced at intervals corresponding to 12 hours of ship passage. For each node, current and forecasted hydro-meteorological data on wind, waves, and surface currents are assigned. A modified A* (A-Star) algorithm is proposed to solve this problem. Instead of distance, the heuristic function uses the shortest travel time, accounting for speed reductions or increases due to hydrometeorological influences on each segment between adjacent graph vertices. The proposed algorithm demonstrates high speed in finding the optimal path. Computer simulations illustrate the results of the modified algorithm. The results show significant time savings when navigating the optimal route compared to the Great Circle. This method can be used to develop systems for automated planning of optimal routes considering changing environmental conditions.