|
We introduce, discuss, and solve a hard practical optimization problem that deals with routing bidirectional traffic. This situation occurs in train traffic on a single track with sidings, ship traffic in a canal, or 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.
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 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.
|
