2017-05-23
Prof. Rolf H. Möhring, gave a lecture titled “Online Scheduling of Bidirectional Traffic”at NCMIS on 11, May, 2017.
In this talk, they introduced, discussed, and solved 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.
They illustrated their 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.
They 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 they will also address recent complexity and approximation results for this class.
The lecture was based on joint work with Elisabeth Lübbecke and Marco Lübbecke.
Prof. Rolf H. Möhring received the M.Sc. and Ph.D. degrees in mathematics with the RWTH Aachen University, Aachen, Germany, in 1973 and 1975, respectively. His current research interests include graph algorithms, combinatorial optimization, scheduling, logistics, and industrial applications. He was a recipient of the Scientific Award of the German Operations Research Society and the EURO Gold Medal of the European Association of Operational Research Societies. He has been the Chair of the German Operations Research Society and the Mathematical Programming Society.
