Autonomous and Optimized Ship Routing

Ioannis Z. Emiris2021 · DOI

TL;DR

This paper presents a comprehensive overview of advanced computational methods for autonomous ship routing, focusing on both collision avoidance and optimized route planning. By leveraging geometric computing and operations research techniques, the authors aim to enable more intelligent, efficient, and safer maritime operations, paving the way for semi-autonomous and fully autonomous navigation.

What Problem Does This Paper Address?

The maritime industry is increasingly seeking to integrate intelligence and automation into its operations to improve safety, efficiency, and reduce costs. This paper addresses the challenges of achieving autonomous ship routing by tackling two critical aspects:

  1. Collision Avoidance in Complex Environments: Traditional navigation relies heavily on human judgment, which can be prone to errors, especially in busy or complex maritime settings. The paper aims to develop computational methods that can provide robust, real-time collision detection and avoidance capabilities, supporting both semi-autonomous and fully autonomous navigation.
  2. Optimized Routing and Scheduling: Beyond just avoiding collisions, efficient ship operations require optimizing routes based on various constraints. These include fuel consumption, environmental regulations, time windows for port availability, and the cargo capacity of the vessel. The paper seeks to develop methods that can handle these complex optimization problems to minimize voyage costs and environmental impact.

Methods

The authors present a two-pronged approach, drawing on their work at the Lab of Geometric & Algebraic Algorithms:

  • Geometric Computing for Collision Avoidance:
    • Voronoi Diagrams of Ellipses: A key contribution is the extension of Voronoi diagrams to handle ellipses, which can model non-convex obstacles like ships more accurately than simple points or circles. This allows for the computation of regions where a ship is closest to a particular obstacle, guiding navigation to maximize distance from potential hazards.
  • Kinetic Voronoi Diagrams (kVD): To account for the dynamic nature of maritime traffic, the paper discusses the use of kinetic Voronoi diagrams. These diagrams adapt in real-time as obstacles (ships) move, providing continuous collision avoidance information.
  • CGAL Integration: The developed algorithms are implemented within the Computational Geometry Algorithms Library (CGAL), a powerful C++ platform for geometric computing, making them accessible for integration into existing software.
  • Operations Research for Optimized Routing:
    • Google OR-Tools: The paper leverages Google's OR-Tools, an open-source suite for optimization problems. This platform is used to address complex routing scenarios involving:
  • Fleet Routing: Managing multiple vehicles with capacity and time window constraints.
  • Scheduling: Handling tasks with dependencies and resource limitations.
  • Packing Problems: Optimizing cargo loading into vessel holds.
  • Customization for Maritime: The authors highlight their contributions to OR-Tools, adapting it to specific maritime needs, such as handling vessels with multiple compartments, incorporating safety regulations, and managing time delays at ports.
  • Geometric Clustering: An initial approach involves geometric clustering of destinations to accelerate the search for optimal routes.

Datasets

Not explicitly discussed in the paper. The methods are presented as general computational approaches that can be applied to real-world maritime data. Figure 3 shows a heatmap of global cargo travel in 2015, illustrating the context for optimized routing, but it is not presented as a dataset for evaluation.

Key Insights and Ideas

  • Ellipses as a Superior Obstacle Model: Using ellipses for collision avoidance is a significant improvement over simpler geometric shapes, allowing for more realistic modeling of ship geometries and complex environments.
  • Kinetic Voronoi Diagrams for Dynamic Environments: The ability of kVD to adapt to moving obstacles is crucial for real-time maritime navigation, where the positions of other vessels are constantly changing.
  • OR-Tools as a Versatile Optimization Backbone: Leveraging a powerful, open-source optimization library like OR-Tools provides a robust foundation for tackling the multifaceted challenges of ship routing and scheduling.
  • Integration of Geometric and Optimization Techniques: The paper effectively demonstrates how geometric computing (for collision avoidance) and operations research (for route optimization) can be combined to create a more holistic autonomous navigation system.
  • Focus on Practical Implementation: The emphasis on using established libraries like CGAL and OR-Tools suggests a strong focus on practical implementation and technology transfer to the industry.

Key Results

The paper focuses on presenting the methodologies and their potential impact rather than specific quantitative results from extensive evaluations. However, it highlights:

  • "Success Story" for Voronoi Diagrams of Ellipses: The authors claim a run-time of 1 second for each new ellipse added to the diagram, indicating efficient computation.
  • Speedup in Geometric Clustering: Their algorithm for geometric clustering, based on k-means, is reported to be the fastest since its publication and maintained that status for a couple of years.
  • Enhanced OR-Tools Functionality: The paper details how their contributions have enhanced OR-Tools for specific maritime applications, enabling more accurate and comprehensive optimization.

Limitations and Future Work

  • Real-World Data Testing: The authors acknowledge that the C++ tool based on kinetic Voronoi diagrams needs to be tested on real data to validate its performance and provide e-Navigation assistance.
  • Risk Assessment: A key interest is in the risk assessment of autonomous or semi-autonomous navigation decisions, and minimizing such risks, which implies further research in this area.
  • Supervised Machine Learning for Vessel Profiling: The paper suggests that supervised machine learning could be used to learn vessel profiles for better cargo assignment and loading factor maximization, indicating a direction for future work.
  • Predictive Maintenance and Autonomous Robots: The authors mention ongoing research in areas like predictive maintenance and autonomous robots for heavy-duty operations, suggesting a broader vision for automation in shipping beyond just routing.

Summary updated

Abstract

We present state-of-the-art computational methods which are instrumental in autonomous maritime operations, and optimization of routing, scheduling as well as loading. Our aim is to survey mature algorithmic approaches developed within the Lab of Geometric and Algebraic Algorithms, towards exploiting intelligence and automation in modern shipping and, in particular, in various aspects of routing. We showcase our advances in two main axes: (a) geometric computing for collision avoidance in complex environments, thus allowing for semi-autonomous and fully autonomous navigation, and (b) optimization for routing under time constraints of the carrier ship, time windows of availability at the ports of call, and capacity constraints of various compartments within a vessel.
BibTeX
@misc{emiris2021autonomous,
  author = {Ioannis Z. Emiris},
  title = {{Autonomous and Optimized Ship Routing}},
  year = {2021},
  doi = {10.5957/some-2021-017},
}
Figure