Optimizing the Kiel Canal – Online Routing of Bidirectional Traffic
We introduce, discuss, and solve a hard practical optimization problem that deals with routing bidirectional traffic on the Kiel Canal, which is the world’s busiest artificial waterway with more passages than the Panama and Suez Canal together. The problem arises from scarce resources (locations) at which large ships can only pass each other in opposing directions.
This is a prototype problem for traffic management and routing in logistic systems. One wants to utilize the available street or logistic network in such a way that the network “load” is minimized or the “throughput” is maximized. The aspects of “time” and “congestion” play a crucial role in these problems and require new techniques that need to integrate dynamic network flows and scheduling.
The lecture will illustrate recent developments in this direction on the example of the Kiel Canal problem, which was a project with the German Federal Waterways and Shipping Administration. Here certain ships must wait in sidings to let opposing traffic pass. This requires decisions on who should wait for whom (scheduling), in which siding to wait (packing) and when and how far to steer a ship between sidings (routing), and all this for online arriving ships at both sides of the canal.
The combination of routing and scheduling (without the packing) leads to a new class of scheduling problems dealing with scheduling bidirected traffic on a path, and we will also address recent complexity and approximation results for this class.
For the application, we need a feasible assignment of parking slots within sidings over time that is consistent with the scheduling decisions between the sidings and the routing. We have developed a combinatorial algorithm that provides a unified view of routing and scheduling that combines simultaneous (global) and sequential (local) solution approaches to allocate scarce network resources to a stream of online arriving vehicles in a collision-free manner.
Computational experiments on real traffic data with results obtained by human expert planners show that our combinatorial algorithm improves upon manual planning by 25%. It was subsequently used to identify bottlenecks in the canal and to make suggestions for enlarging the capacity of critical sections of the canal to make it suitable for future traffic demands.
The lecture is based on joint work with Elisabeth Lübbecke and Marco Lübbecke.
Keynote: IFORS Distinguished Lecture, Rolf H. Mohring, Beijing Institute for Scientific and Engineering Computing
About the Awardee
Rolf H. Möhring obtained his M.S. (1973) and P.h.D (1975) in Mathematics at the RWTH Aachen and is since 1987 Professor for Applied Mathematics and Computer Science at Berlin University of Technology, where he heads the research group “Combinatorial Optimization and Graph Algorithms” (COGA). He has held earlier positions as associate and assistant professor at the University of Bonn, the University of Hildesheim, and the RWTH Aachen. His research interests center around graph algorithms, combinatorial optimization, scheduling, logistics, and industrial applications. Part of his research has been done in DFG Research Center Matheon, where he was Scientist in Charge of Application Area “Logistics, traffic, and telecommunication networks”. He has been chair of the German Operations Research Society and the Mathematical Programming Society and has been awarded the Scientific Award of the German Operations Research Society and the EURO Gold Medal of the European Association of Operational Research Societies. Since 2014 he is a honorary professor at the Beijing University of Technology and in the Board of the Beijing Institute for Scientific and Engineering Computing BISEC.