We introduce, discuss, and solve a hard practical optimization problem that deals with routing bidirectional traffic on a line. This situation occurs in train traffic on a single track with sidings, in ship traffic in a canal, or in bidirectional data communication.
We illustrate our methods and algorithms on the Kiel Canal, which is the world’s busiest artificial waterway with more passages than the Panama and Suez Canal together. The scheduling problem arises from scarce resources (sidings) that are the only locations where large ships can pass each other in opposing directions. 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. This problem was proposed to us by the Wasserstraßen- und Schifffahrtsverwaltung des Bundes (WSV.de) and has led to a joint project with them.
In this project we have developed a combinatorial algorithm that provides a unified view of routing and scheduling. It combines concurrent (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 algorithm improves upon manual planning by 25%.
This combination of routing and scheduling (without the packing) leads to a new class of scheduling problems, and we will also address recent complexity and approximation results for this class.
The lecture is based on joint work with Elisabeth Lübbecke and Marco Lübbecke.
Venue: Z 536 (City Campus)
Date: Monday, June 25th, 2018, 14:00