Resource-constrained scheduling for maritime traffic management

• Main Authors: AGUSSURJA, Lucas, KUMAR, Akshat, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Constraint programming; Electronic navigation charts; Maritime traffic management; Navigational safeties; Resource constrained scheduling; Resource-constrained project scheduling problem; Singapore straits; Symmetry breaking constraints; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/4052; https://ink.library.smu.edu.sg/context/sis_research/article/5055/viewcontent/Resource_constrained_scheduling_for_maritime_traffic_management_2018_pv.pdf
• Institution: Singapore Management University

We address the problem of mitigating congestion and preventing hotspots in busy water areas such as Singapore Straits and port waters. Increasing maritime traffic coupled with narrow waterways makes vessel schedule coordination for just-in-time arrival critical for navigational safety. Our contributions are: 1) We formulate the maritime traffic management problem based on the real case study of Singapore waters; 2) We model the problem as a variant of the resource-constrained project scheduling problem (RCPSP), and formulate mixed-integer and constraint programming (MIP/CP) formulations; 3) To improve the scalability, we develop a combinatorial Benders (CB) approach that is significantly more effective than standard MIP and CP formulations. We also develop symmetry breaking constraints and optimality cuts that further enhance the CB approach's effectiveness; 4) We develop a realistic maritime traffic simulator using electronic navigation charts of Singapore Straits. Our scheduling approach on synthetic problems and a real 55-day AIS dataset results in significant reduction of the traffic density while incurring minimal delays.