A rapid globe-wide shortest route planning algorithm based on two-layer oceanic shortcut network considering great circle distance

In this paper, to realize the globe-wide route planning in a real-time by graph-search, we put forward an oceanic shortcut network (OSN) to discretize the large planning area involved, which consists of a base graph to resolve tiny features and a fast-forwarding graph to accelerate searching process. Then, A* graph-search is applied on the proposed OSN to derive a shortest path between given starting and end points, which is applicable in the dispatching system for vessels. Noticeably, since the shortcuts have arbitrary heading directions, our algorithm does not have angular bias problem as the conventional structured-grids and can follow optimal routes with proper headings. Moreover, when building the OSN, instead of Euclidean distance (ED), we apply the great circle distance (GCD) in the distance metric for both layers, which can approximate the distance on a spherical surface accurately. Additionally, during the construction of OSN, we propose a method to determine if a point is in the obstacle and judge if a line segment has intersections with the obstacle on a spherical surface. Lastly, we testify our algorithm in several cases to demonstrate the total-distance reduction and time-efficiency brought by it.

Automated summary

In this paper, a solution to realize globe-wide real-time route planning is proposed using an oceanic shortcut network (OSN). The proposed OSN consists of a base graph and a fast-forwarding graph, and the A* graph-search algorithm is applied to find the shortest path between given starting and end points. The algorithm eliminates the angular bias problem and follows optimal routes. The use of great circle distance accurately approximates distances on a spherical surface. The algorithm is validated through experiments, demonstrating reduced total distance and improved time efficiency.