### Inhalt des Dokuments

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.

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.

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

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

### 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 Traﬃc Optimization for the Kiel Canal**.

In *Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN 2010)*, 2010.
[pdf]

### Technical reports

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

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