Decision Making for Improving Maritime Traffic Safety Using Constraint Programming

Saumya Bhatnagar, Akshat Kumar, Hoong Chuin Lau

Introduction

In high-traffic waterways like the Singapore Straits, maritime safety is a critical concern. Port controllers currently rely on reactive measures, intervening at the last second to prevent "near-miss" collisions. This paper proposes a proactive scheduling approach to mitigate traffic congestion and enhance safety margins before dangerous situations arise.

The Maritime Traffic Challenge

The Singapore Straits are among the busiest in the world, with thousands of unique vessels navigating complex routes daily. Managing this traffic is difficult because ships cannot simply stop in busy lanes; they must adhere to speed limits, maintain safety distances, and follow Traffic Separation Schemes (TSS).

Map of the Singapore Straits highlighting key navigational features and crossing areas.

Reactive management is not only stressful for controllers but also leaves a narrow margin for error. Accidents in these waters can lead to significant loss of life and environmental catastrophes, such as major oil spills.

Methodology: Constraint Programming for Vessel Scheduling

The researchers modeled the waterway as a grid of 216 hexagonal zones, treating each zone as a "resource" with a specific capacity. The problem was then formulated as a variant of the Resource Constrained Project Scheduling Problem (RCPSP) and solved using Constraint Programming (CP).

Key technical innovations include:

  • Variable Activity Durations: Ship transit times through zones are treated as variables based on speed, rather than fixed durations.
  • Bi-Objective Optimization: The solver balances two goals: minimizing total vessel delay and minimizing "resource violations" (instances where more than one ship occupies a zone).
  • Realistic Navigational Constraints: The model incorporates domain-specific rules such as speed limits, gradual acceleration, and "no-stop" zones in TSS.
  • Operational Limits: To ensure the plan is manageable for human controllers, the model limits the number of ships required to change their trajectory.

Experimental Results

The approach was tested using four months of historical data from the Singapore Straits, focusing on 64 high-traffic "hotspot" instances featuring between 27 and 53 vessels each.

Percentage decrease in resource violations across 30 test days, demonstrating the effectiveness of the proactive scheduling approach.

The results demonstrate significant improvements in traffic safety:

  • Congestion Reduction: Resource violations (congestion) were reduced by approximately 50% on average across the busiest test days.
  • Minimal Operational Impact: These safety gains were achieved with very low delays. The average delay per vessel was only 5–6 minutes, with maximum delays typically staying under 12 minutes.
  • Real-Time Performance: The CP solver consistently produced high-quality solutions in under 5 minutes, making it fast enough for live port operations.

Conclusion

By shifting from reactive to proactive traffic management, this Constraint Programming approach significantly increases safety margins in busy maritime corridors. The model's ability to reduce congestion with minimal shipping delays and its fast execution time make it a viable tool for modern port authorities seeking to prevent accidents and improve operational efficiency.

Summary updated

Abstract

Maritime navigational safety is of utmost importance to prevent vessel collisions in heavily trafficked ports, and avoid environmental costs. In case of a likely near miss among vessels, port traffic controllers provide assistance for safely navigating the waters, often at very short lead times. A better strategy is to avoid such situations from even happening. To achieve this, we a) formalize the decision model for traffic hotspot mitigation including realistic maritime navigational features and constraints through consultations with domain experts; and b) develop a constraint programming based scheduling approach to mitigate hotspots. We model the problem as a variant of the resource constrained project scheduling problem to adjust vessel movement schedules such that the average delay is minimized and navigational safety constraints are also satisfied. We conduct a thorough evaluation on key performance indicators using real world data, and demonstrate the effectiveness of our approach in mitigating high-risk situations.
BibTeX
@inproceedings{bhatnagar2019decision,
  author = {Saumya Bhatnagar and Akshat Kumar and Hoong Chuin Lau},
  title = {{Decision Making for Improving Maritime Traffic Safety Using Constraint Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/803},
}
Figure