Ship Traffic Optimization for the Kiel Canal

The Kiel Canal connects the North and Baltic seas and is ranked among the world’s three major canals. In fact, in terms of traffic, it is the busiest artificial waterway worldwide. In a billion Euro project, the German Federal Waterways and Shipping Administration plans to enlarge the canal during the coming years. This project is about contributing to a well-founded advise on how the enlargement can be optimally done. In order to evaluate the various construction possibilities it is indispensable to first provide an accurate model for the ship traffic and designing an algorithm which (ideally optimally) controls it. This paper is about such optimal traffic control. The problem very roughly is as follows. There is bi-directional ship traffic on the canal; there are several locks at both ends. Ships are classified in different size categories. Passing and overtaking is allowed only if the sizes of the two ships do not exceed a given threshold which depends on the meeting point. If otherwise a conflict occurs, ships have to wait at designated, capacitated places, the sidings. The objective is to minimize the total passage time, including lock and siding waiting times. The overall scheduling is currently done by two teams of experienced planners, one for the locks, one for the sidings. In this abstract we concentrate on the latter problem, but both will be treated in an integrated way during the project. Despite significant differences there are certain similarities to train scheduling on a single track line [1]