On the Right Track: Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization
Deutsche Bahn (DB) uses novel operations research methods to optimize the rotations of its rolling stock in its cargo, regional, and long-distance passenger transport divisions. Advanced optimization methods allow DB to manage timetable changes in order to offer more and better services to its customers, cut greenhouse emissions, and enhance regularity. DB transports about 5.6 million people each day on trains throughout Germany, as well as 700,000 tons of goods. These are carried by over 1,400 long-distance trains, 22,000 regional passenger trains, and 2,800 cargo trains, which are operated by a fleet of 3,800 locomotives, 4,500 passenger coaches, more than 80,000 freight wagons, and over 4,000 railcars, among them 274 ICE high-speed trains.
With a constantly increasing number of trains and a continuously fluctuating demand on a limited infrastructure in a deregulated, competitive railway market, it becomes harder and harder to schedule these services. It is difficult to direct the trains through bottlenecks and around construction sites to avoid cancellations, deadhead trips, and orientation mismatches. To address the challenges of using its rolling stock at full capacity, Deutsche Bahn drafted a vision of reinventing railways: “Strong rail” is DB’s overarching strategy to become more efficient in operations, develop a more powerful organization, and stimulate innovations. The cornerstone of this plan is the development and implementation of a new generation of advanced operations research methods, to first and foremost schedule DB’s core asset: its rolling stock of locomotives, wagons, and railcars.
To this purpose, DB launched the development of a new train/locomotive rotation optimization system called FEO/LEO in 2008. In order to provide a company-wide planning platform for three divisions, the solution was implemented as a modular system around adaptable optimization kernels. These kernels were flexibly customized to suit a large variety of planning tasks. FEO/LEO is directly linked to DB legacy planning IT, such that a seamless workflow is ensured. A particular strength in FEO/LEO is an integrated feedback algorithm that allows planners to approach an aspired solution by applying minimal changes with respect to the planning constraints. This had a profound impact on the scheduling methodology at DB, which changed from constructive to analytical planning.
The FEO optimizers are based on completely new and sophisticated mathematical methods of algorithmic network and hypergraph theory. This research is done together with Zuse Institute Berlin and LBW Optimization. The novel approach allows for an integrated treatment of the main operational requirements all within one generic model. A novel coarse-to-fine algorithm allows the solution of large-scale instances with up to 100 million variables. The approach also gives rise to deep theoretical developments in the mathematical foundations of operations research.
FEO has been operating since 2013 and has increased revenues in long-distance passenger transport by more than $26 million per year by reducing cancellations, and by $25 million per year in regional passenger transport by successful bids for tender contracts.
In the cargo division, LEO went online in 2018 with estimated savings of over $29 million per year. Moreover, dangerous and arduous labor is reduced with less couplings. Resource planners benefit in their day-to-day work from the powerful scheduling functionality of FEO/LEO, which reduces repetitive tasks and allows room for analyzing different options.
FEO/LEO is a first and key step toward the implementation of DB’s strong rail strategy. Driven by advances in operations research, strong rail will provide fast, comfortable, and efficient transport with minimal environmental footprint.