The encyclopedia · Engineering & Operations · Operational decision · 2018–2021
Deutsche Bahn matched trains to trips with hypergraph optimization, saving €74m a year.
DB turned the huge problem of deciding which train unit serves which service into hypergraph optimization, cutting cost, coupling work and CO2.
Deutsche Bahn (DB)
the move
Deutsche Bahn had to decide how thousands of train units should be assigned to planned services, a problem too large and rule-bound to solve sensibly by hand across cargo, regional and long-distance passenger divisions.
Working with ZIB and LBW Optimization, it built FEO, which models the rotation problem as graph and hypergraph optimization and solves it with clustering plus optimization, letting planners test many schedule scenarios quickly.
DB attributes the implementation to annual savings of €74 million, a cut of 34,000 tonnes of CO2 emissions, and the elimination of 600 coupling operations in cross-border operations.
why it works
- Rotation is a global allocation, not a set of local choices
- Hypergraph structure captures constraints a list cannot
- Fast solving lets planners test many futures before committing
- Measured: €74m/year, 34,000 tonnes CO2, 600 fewer couplings
what transfers
Many operational choices look like separate decisions but are really one global allocation; recast them as a single optimization model to unlock savings that local rules miss.
what came after
The FEO system became part of DB's planning toolkit and the work made Deutsche Bahn a finalist for the 2020 INFORMS Edelman Award, with the approach spreading to further divisions and timetable-change scenarios.
references
- Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization (abstract)
- Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization
spotted an error? The archive wants to know.