Ship Traffic Optimization for the Kiel Canal

• 成果类型: Article
• 署名作者: Luebbecke, Elisabeth; Luebbecke, Marco E.; Moehring, Rolf H.
• 署名单位: RWTH Aachen University; Technical University of Berlin; Beijing University of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1814
• 发表日期: 2019
• 页码: 791-812
• 关键词: simulation; MODEL

摘要

We introduce a hard practical optimization problem, the ship traffic control problem (STCP). We study it at the Kiel Canal, which is the most frequented artificial waterway in the world. The canal is operated bidirectionally, but large ships can pass each other only in sidings. Decisions must be made about who is waiting for whom, where, and for how long, subject to a multitude of operational constraints. The objective is to minimize the total waiting times of all ships. This problem generalizes train scheduling on a single-track network. We integrate algorithmic ideas from collision-free routing of automated guided vehicles. This leads to a unified view of scheduling and dynamic routing that may serve as a prototype for scheduling bidirectional traffic with passing conflicts. We implement a traffic control tool that uses our combinatorial algorithms and perform a computational study on traffic data from the Kiel Canal. Our tool produces schedules that significantly improve over manual planning and were approved by expert planners. As traffic volume and vessel sizes are projected to significantly increase, the canal is planned to be enlarged in a huge project. Our tool was used to select from a variety of enlargement options. The enormous level of detail in our model ensured that the chosen construction scenario actually constitutes a remedy to the impending inoperability of the canal.