Scheduling two-way ship traffic for the Kiel Canal: Model, extensions and a matheuristic

Abstract

The Kiel Canal is an artificial waterway of about 100 km that connects the North Sea and the Baltic Sea. It allows ships to save several hundred kilometers of travel distance compared with going around the Jutland Peninsula (Denmark). Since the canal contains several narrow segments where large ships cannot pass each other, it needs to be decided on which ships have to wait in the wider siding segments to ensure a fast and safe passage of all ships. With this paper, several new optimization models are proposed for this traffic managing problem, which include variable ship speeds, capacities of siding segments, and limits for waiting times of ships. All model variants capture the relevant traffic rules and safety requirements with the goal to minimize the total transit time of ships. A matheuristic is proposed for solving the problem quickly. Experiments on real world data confirm the excellent performance of the heuristic and identify the potentials for providing high quality service to ships.