Optimising ship routes with capability plots and Dijkstra's algorithm

Determining a vessel’s route from its starting location to the intended destination is a fundamental aspect of voyage planning. Historically, seafarers manually charted routes using nautical charts, but contemporary practices increasingly rely on computational algorithms to navigate to any port worldwide. Most scholarly works on this subject present algorithms that generate global routes based on historical data concerning weather and maritime traffic along major sea lanes. However, such methods often neglect the prevailing local hydrometeorological conditions, which can amplify the impact of environmental forces and consequently increase energy consumption. A viable alternative is localised route planning that incorporates current environmental conditions, enabling adaptive navigation to dynamically changing sea states. This approach allows for routes that minimise the impact of environmental forces on the vessel’s hull, thereby reducing both fuel and energy consumption. This study introduces an algorithm tailored for determining local passage routes for offshore vessels, demonstrated by a ship navigating to an anchorage point. The algorithm creates a grid of points between the ship’s current position and the anchorage, assigning transition weights to these points based on the vessel’s capability plots. A modified version of Dijkstra’s algorithm is then employed to calculate the route with the lowest cumulative transition weight. Testing revealed that the computational time required to generate a route is influenced by the density of the waypoint grid, ranging from 0.05 seconds for a 6 × 6 grid to 0.85 seconds for a 21 × 21 grid. Additionally, the optimised route reduced the impact of environmental forces on the vessel by 3%, resulting in a 5% decrease in energy consumption compared to a direct course. The algorithm’s operation was validated using an anchor planning tool developed in the Unity3D environment.