Inhalt des Dokuments
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.
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. During the project both aspects will be treated in an integrated way. Some first results exist for the latter problem and are shortly scetched here.
To decide the waiting time of each ship in each siding, such that no conflict occurs and no capacity is exeeded, one needs some sort of time and space discretization. In particular the latter one causes some difficulties due to lots of different ship sizes and arbitrary start and end points. Instead of respecting such a discretization in the model directly we chose to let the algorithm take care of that. We designed a successive shortest path algorithm respecting blocked time windows which constructs conflict-free dynamic routes for the ships one after another. In addition to the basic version used for Online AGV Routing our algorithm allows more than one ship to be on an edge, handles arbitrary start and end positions in the canal, and tries different valid waiting positions in a siding. Thus, an initial solution is constructed which is feasible with respect to all constraints. The running time is a few seconds.
A local search based on a loss-benefit calculation improves that first solution in a rolling horizon manner, mildly imitating a manual planner's procedure. Since this local search uses the dynamic routing algorithm as a subroutine also the final schedule respects all the constraints. Our solutions are visualized in exactly the same way the planners are used to see them, in a distance-time diagram of the canal.
Not only for theoretical reasons we want to assess the quality of the heuristic solutions we obtain. Therefor, we formulate a mixed integer program (MIP), which, ignoring siding capacities and constraints, is a relaxation of the original problem. However, for practical problem instances it takes much too long to solve this formulation to integer optimality, mainly because of the poor LP relaxation. Instead, we developed a much more involved model which is solved by a full-fledged branch-and-price algorithm. The idea is to base an integer program on schedules for all ships on a given segment. Via a sort of flow conservation constraints these schedules for segments are linked together to form a valid schedule for the entire canal. The pricing subproblem is a scheduling problem which is interesting in its own right. In principle, this model is suited to seamlessly integrate the lock scheduling problem as well. To price the corresponding variables, a particular two-dimensional packing problem needs to be solved.
- Martin Luy, Algorithmen zum Scheduling von Schleusenvorgängen am Beispiel des Nord-Ostsee-Kanals, 2010.
- Robert Pankrath, Algorithmen für die Verkehrsflussoptimierung auf dem Nord-Ostsee-Kanal, 2010.