direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Ship Traffic Optimization for the Kiel Canal

Lupe

Project heads:
Rolf H. Möhring
Marco E. Lübbecke
Researcher:
Elisabeth Günther
Cooperation partner:
Waterways and Shipping Administrations of Kiel-Holtenau and Brunsbüttel
Part of:
Matheon Project B24

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.

Traffic on the Kiel Canal
The Kiel Canal
Lupe

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.

Ships waiting in a siding
Ships waiting in a siding until they can pass the next canal segment.
Lupe

Algorithm

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.

distance-time diagram
Example of a distance-time diagram showing one of our solutions.
Lupe

Lower Bounds

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.

Project Output.

Publications

Extended abstracts

Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal.
In Proceedings of the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011), 2011.  [pdf]


Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Ship Traffic Optimization for the Kiel Canal.
In Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN 2010), 2010.  [pdf]


Technical reports

Ship Traffic Optimization for the Kiel Canal
Citation key LuebbeckeLuebbeckeMoehring2014
Author Lübbecke, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Year 2014
Number 4681
Month 12
Institution Optimization Online
Abstract We introduce, discuss, and solve a hard practical optimization problem which we call the ship traffic control problem (STCP). Since we plan bi-directional traffic, STCP relates to, and in fact generalizes train timetabling on single-track networks. The objective of finding quickest routes motivates the integration of recent algorithmic ideas from dynamic collision-free routing of automated guided vehicles. We offer a unified view of routing and scheduling which blends simultaneous (global) and sequential (local) solution approaches to allot scarce network resources to a fleet of vehicles in a collision-free manner. This leads us to construct a fast online heuristic. The STCP originates from the Kiel Canal which is the basis for the trade between the countries of the baltic area and the rest of the world. As traffic is projected to significantly increase, the canal is planned to be enlarged in a billion Euro project. Our work forms the mathematical and algorithmic basis for a tool to evaluate the different enlargement options. In view of computational experiments on real traffic data expert planners approved that our combinatorial algorithm is well-suited for this decision support. With the help of instance-dependent lower bounds we assess the quality of our solutions which significantly improves upon manual plans. We are confident that our ideas can be extended to other application areas like train timetabling and collision-free routing, also in more general networks.
Link to original publication Download Bibtex entry

Diploma students

  • 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.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions