Beijing Institute for Scientific and Engineering Computing
Optimizing the Kiel Canal - Integrating Dynamic Network Flows and Scheduling
Date: Wednesday, July 6, 2016 - 14:30-15:30
Bio: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.
Title:Optimizing the Kiel Canal - Integrating Dynamic Network Flows and Scheduling
Abstract: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 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 to 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 address recent complexity and approximation results for this class.
For the full problem, 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. To that end, we used a routing algorithm that we had developed earlier for routing automated guided vehicles in a container terminals (cooperation with HHLA). We will explain details of this algorithm and show how to combine it with a rolling horizon technique for the scheduling and packing decisions in the canal. This provides a unified view of routing and scheduling that blends 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.
Presented in a movie here: http://www.euro2016.poznan.pl/rolf-mohring/