Im Rahmen des Berufungsverfahrens zur Besetzung der W2-Professur am FB Mathematik und Informatik für "Diskrete Mathematik  mit dem Schwerpunkt Diskrete Optimierung in  den Verkehrswissenschaften" laden wir ein zu dem unversitätsöffentlichen

Vortrag von

Dr. habil. Ralf Borndörfer (Zuse-Institut Berlin)

 

am 20.2.2012 um 10:30 Uhr im Raum 031, Arnimallee 6 (PI-Gebäude)

 

Abstract:

Railways are a classical and yet extremely active application area of combinatorial optimization and integer programming. Large networks, complex technical requirements, evolving demand patterns, and changes in the regulatory framework

give rise to challenging optimization problems, which call for the development of new mathematical models and algorithms.

There is, in particular, a need for a simultaneous treatment of multiple aspects, i.e., an integration of decisions about routing, scheduling, train composition, maintenance, parking, transfers, etc. This talk proposes ``configuration models'' as a novel approach to such problems. Configurations are local building blocks of primal solutions. The idea is to model involved requirements, that would be difficult to express in terms of constraints, using an exhaustive, but local, and hence manageable, enumeration of variables. This often gives rise to large, but combinatorially clean packing and covering type models, and it often produces strong LP bounds. Examples for applications of this method include railway track allocation (configurations are occupations of track segments over time), freight train routing (configurations correspond to capacity reservations of track segments in time slices), vehicle rotation planning (configurations correspond to train compositions), and line planning (configurations correspond to line bundles on infrastructure segments). Configuration models lend themselves to column generation approaches, which can be complemented by problem specific methods. The talk discusses the case of track allocation, in which the master problem is about path packing, and the case of vehicle rotation planning, in which the master problem is about flows in hypergraphs. Results for saturating the capacity of the Simplon tunnel through the Alps and for scheduling the ICE high-speed train fleet in Germany will be reported.

This talk is based on joint work with Martin Grötschel, Olga Heismann, Torsten Klug, Markus Reuther, Thomas Schlechte, Elmar Swarat, and Steffen Weider.