Algorithms for Wind-Powered Cargo Ship Routing

Abstract

This thesis explores a novel approach to long-distance ship weather routing by employing a quadtree data structure to represent the ocean surface, combined with an approach to interpolating graph weights used by a modified Dijkstra’s Algorithm. This approach allows access to a wider range of relative wind angles compared to using a uniform grid.

This study evaluates the performance of the interpolation technique, specifically examining how quadtree subdivision levels (or bounding box size) relate to interpolation accuracy. The findings indicate that the interpolation method performs similarly over a varying range of bounding box sizes if one assumes a relatively high engine-driven calm water speed. The auxillary electric engine is used when wind speeds can’t propel the vessel above the calm water speed. In some cases, larger bounding boxes yield better results, however it is possible this was due to the weather forecast deviating from the actual historical data, or approximation errors in the graph weight interpolation. The study highlights the importance of selecting an appropriate default calm-water speed, as it influences the accuracy of the interpolation method.

The interpolation algorithm introduces runtime overhead to the path planning algorithm, especially when the size of the bounding box is large. Memory savings are significant, even though the quadtree was only subdivided in the local area around the path. The best trade-off between memory and runtime savings is achieved with a bounding box size of 222-111 km.

Future work should focus on refining default speed selection, incorporating additional weather data, and further optimizing the quadtree framework to improve efficiency and robustness in real-world maritime applications.