第13回統計的機械学習セミナー / The 13th Statistical Machine Learning Seminar

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 of successful applications of this method include railway track allocation (the configurations are occupations of track segments over time), vehicle rotation planning (the configurations correspond to train compositions), and line planning ( configurations correspond to line bundles on an 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 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¨otschel, Olga Heismann, Torsten Klug, Markus Reuther, Thomas Schlechte, Elmar Swarat, and Steffen Weider.