Scheduling ships with uncertain arrival times through the Kiel Canal

The Kiel Canal is a two-way waterway that connects the Baltic Sea and the North Sea. The canal consists of an alternating sequence of narrow transit segments and wider siding segments. This calls for solving a ship scheduling problem to decide which ships have to wait in sidings to let opposing traffic pass through such that the total traversing time of all ships is minimized. This paper extends previous studies on scheduling ships through the Kiel Canal by considering that the arrival times of the ships at the entrance to the canal are subject to uncertainty. This is a major challenge in the planning as it gives frequent need of replanning to make the schedules feasible. We propose a mathematical formulation for the problem to mitigate the negative effects of the uncertainty. This formulation incorporates time-corridors, so that the schedule will still be valid as long as the ships arrive within their given time-corridors. To solve real-sized instances of the problem, we adapt a matheuristic that adds violated constraints iteratively to the problem. The matheuristic was tested within a rolling horizon simulation framework to study the effect of arrival time uncertainty. We show by experiment that solutions of the matheuristic for different time-corridor widths can be used to identify a suitable corridor width that trades off the average traversing time of ships and the number of reschedules required in the planning. A simple myopic heuristic, reflecting the current scheduling practice, was used to generate benchmark results, and tests on real data showed that the matheuristic provides solutions with significantly less need of replanning, while at the same time keeping the total traversing times for the ships short. We also provide simulations to gain insight about the effect on the ships' average traversing time from upgrading the narrow transit segments.