Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization

Introduction

The Western European railway network is among the densest in the world and is of major importance for passenger and freight transport in the European Union (Figure 1). It supports a broad mix of operations, including InterCity Express (ICE) high-speed connections between major cities in central Europe at up to 300 kilometers per hour (km/h), regional passenger transport such as commuter services, and cargo transport with heavy freight trains.

Deutsche Bahn (DB) is among the leading railway companies in the world, with revenue exceeding that of BNSF and Union Pacific combined. Each day, the company transports about 5.7 million people using approximately 24,000 timetabled trips (DB 2018). To do so, DB employs about 1,300 locomotives, 5,500 coaches (i.e., passenger wagons), and 4,200 train sets (i.e., permanently coupled sets of self-powered units), including 274 ICE high-speed units, which are the flagships of DB’s operations (Figure 2). DB also transports 700,000 tons of freight each day using 2,900 freight trains (in Germany), 2,700 locomotives, and 83,000 freight wagons. As the Federal Ministry of Transport and Digital Infrastructure (2020) reports, in 2018, these numbers corresponded to steadily increasing shares in the German market of 8.3% for passenger transport (p. 221) and 19.1% for freight transport (p. 247). Rail transport also has a positive impact on our environment (Federal Environment Agency 2012) because it saves up to two-thirds of energy (p. 14) and 75% of CO₂ (p. 16) in comparison with road transport.

A key asset of every railway company is its train sets, locomotives, and wagons. These units are referred to individually as vehicles, and together as rolling stock, to distinguish them from the network infrastructure of stations, tracks, switches, signals, and control centers that are fixed in place. Putting the rolling stock to efficient use is essential for every optimization strategy. Although it would seem logical for railway companies to use operations research methods, as airlines have used them to schedule their aircraft and public transit companies their buses since the 1980s, this was not the case at DB until recently. The main reason is mathematical. Unlike in air transportation or public transit, solving a railway vehicle routing problem to compute sequences of trips for individual vehicles (i.e., rotations) is not a satisfactory solution. Scheduling railway rolling stock also requires handling the composition of vehicles into trains. One option is to decompose the problem into train composition and train routing steps, which are solved in sequence. In rail freight transport, for example, cars are assembled into blocks in step 1, trains are routed in step 2, and locomotives are scheduled in step 3 (Ireland et al. 2004, Ahuja et al. 2005), often using network flow techniques. Approaches using partial integration include Ahuja et al. (2005), who consider penalizing the breakup of consists (i.e., locomotive compositions) by using consist busting, and Cacchiani et al. (2019), who use capacity constraints on train compositions. Kroon et al. (2009) present an integrated approach, but it is designed for daily settings with fixed turns on the spot (i.e., unique, immediate follow-on trips). This model is suboptimal for operations that rely on repositioning vehicles over long distances and over several days, such as in long-distance passenger transport or in European cargo transport. Therefore, no mathematical methods were available to simultaneously handle both aspects of vehicle scheduling and train composition for DB’s complex and large-scale rolling stock rotation scheduling problems.

DB launched a project to develop a new rolling stock rotation planning (RSRP) system in 2008. Its name FEO is an acronym for “Fahr- und Einsatz-Optimierung,” which can be translated as fleet employment optimization. It is based on new mathematical methods of a concept we call “algorithmic hypergraph theory.”

This paper describes the RSRP problem at DB and our operations research approach to modeling and solving it. We discuss how we implemented our approach and how FEO helped DB to improve its business processes. We then report on success stories for the three DB divisions (DB Fernverkehr AG, DB Regio AG, and DB Cargo) that are responsible for long-distance passenger transport, regional transport, and cargo transport, respectively, and conclude with a summary of the benefits accrued.

The Rolling Stock Rotation Planning Problem

The objective of rolling stock rotation planning is to determine how a railway uses its rolling stock to compose trains and to implement a given timetable subject to a number of objectives and constraints. In this section, we provide background information.

Train Composition

Rolling stock refers to a railway company’s set of vehicles. Traditionally, the vehicles have been (and to a large extent, still are) locomotives and wagons; however, today vehicles can also be train sets (i.e., self-powered, fixed concatenations of several units). Such train sets look like trains, but they cannot be easily disassembled or reassembled, at least not by a coupling operation. For our purposes, we treat them as indivisible vehicles (of a larger size). Figure 3 shows a typical train set.

Similar to locomotives and wagons, train sets can be coupled to form trains if they feature clutches. Rather than using the term train, we use the term train composition or composition to highlight the combinatorial choices that are made in forming a train (we use the term train in the title of the paper because it is a customary word in everyday speech). ICE2 and ICE3 high-speed train sets have special Scharfenberg clutches—clutches that allow them to be coupled to run in double traction (i.e., two self-powered units; in this case, train sets that are coupled together) (Figure 4); theoretically, they can also run in triple traction, but because platform length in Germany is limited to 400 meters, triple-traction ICEs are not allowed. Although the clutches of ICE2 and ICE3 train sets fit together mechanically, the electronic and pneumatic systems are not compatible; therefore, forming trains by coupling ICE train sets of different vehicle types (in this case, ICE generations) is not permitted. ICE vehicles also feature a variety of technical equipment that the neighboring European countries of Austria, Belgium, France, the Netherlands, and Switzerland require. The presence or absence of such equipment results in many vehicle subtypes and complex rules that address which vehicles can be coupled and how this coupling can be done. These rules can be expressed in terms of numbers of vehicles, types of vehicles, or positions of vehicles within a train composition.

A less obvious train composition rule refers to the orientation of a vehicle (i.e., whether it is positioned to drive forward or backward). For example, an ICE1 train set consists of five first-class wagons, followed by a restaurant and seven second-class wagons, and has an overall length of 390 meters. Positioning the train at the correct side of the platform is important to facilitate transfers of passengers between trains that are at the same platform; to ensure first-class wagons are closer to the station, thus minimizing the distance first-class passengers must walk; and to optimize crew relief. If an ICE train set goes forward with the first-class wagons in front, it is said to be in a “tick” orientation; if the second-class wagons are in front, it is called a “tock” orientation. The orientation must also be considered for train composition because of technical constraints. For example, consider two ICE2 train sets that are coupled in double traction as tock-tick, such that the two cockpits at the first-class side of the train sets are face to face in the middle of the train. Such a composition can only run at a maximum speed of 200 km/h. Because the timetable is designed for a train speed of 250 km/h, this is a severe restriction. For these reasons, technical, organizational, and marketing considerations give rise to many train composition rules that have significant combinatorial complexity. We provide an illustration in Figure 5.

All train compositions are rated to assess their desirability and to reflect, for example, the number of vehicles used. Multiplied by travel distances, these weighted factors provide the primary (number of vehicles used), secondary (monetary), and tertiary (operational convenience) objectives of a rolling stock rotation planning problem.

In one sense, the positions and orientations of vehicles within a train composition are less critical than the number of vehicles and their types. Positions and orientations will often end up correctly, or they can be adjusted in a subsequent scheduling step (but not in operation) at no extra cost. This observation can be exploited algorithmically. Therefore, introducing the term “configuration” to refer to the numbers and types of vehicles in a train composition is useful. The train configuration represents a “coarsening” of the composition; that is, the positions and orientations are ignored. The result is significantly fewer configurations than compositions. In the example in Figure 5, the 16 compositions are coarsened to three configurations: (1) two white framed, (2) one white framed and one gray framed, and (3) two gray framed.

Turns, Deadhead Trips, and Regularity

Determining the compositions of the timetabled trips is an important aspect of rolling stock rotation planning, but other factors must also be considered. The timetabled trips must be connected. This involves turns and deadhead trips. The simplest types of turns are direct through-station (i.e., a station at which a train can stop and then continue with its composition unchanged) turns and direct turns in a dead-end station (i.e., a station at which the track ends such that the train reverses its orientation). To avoid a reversal, a turn with a (hopefully short) turnaround trip can be used, provided the infrastructure allows the reversal. Sometimes, however, a train might have to be reoriented or repositioned using an unproductive empty trip without payload over a larger distance; such a trip is called a deadhead trip. A significant problem involving shunting operations, whose feasibility and duration depend on the track geometry, can arise in scheduling coupling and uncoupling processes on turns and deadhead trips. We will show later in the paper that such (un-)coupling rules can be handled by setting train composition rules for turns and deadhead trips, such that we do not have to delve into the (complicated) subject of railway station operations.

Fortunately, we can also set rules to address the requirement for regularity. Regularity refers to the similarity of operations on different days of the week to provide railways and other industries with the ability to set operational routines. In their package delivery optimization approach, Holland et al. (2017) emphasize the value of regular patterns for their UPS delivery routes, whereas Ahuja et al. (2005) stress the significance of consistent (i.e., regular) locomotive compositions in rail freight transport for trips that repeat in five or more of the seven days of the week. Scheduling similar activities each day is advantageous in every complex system. For this reason, railway timetables are regular (or periodic) and should also be operated using regular train compositions and vehicle rotations. We explain that the mathematical approach we use to address train compositions can also be used to address this requirement.

Summarizing the Rolling Stock Rotation Planning Problem

There are two degrees of freedom in rolling stock rotation planning: selecting the train compositions for the timetabled trips, the turns, and the deadhead trips and selecting the turns and deadhead trips. The number of potential turns and deadhead trips exceeds the number of timetabled trips by orders of magnitude. As both degrees of freedom multiply, the treatment of turns and deadheads becomes the main algorithmic difficulty. Turns, deadhead trips, and the compositions of timetabled trips, turns, and deadhead trips must be chosen in such a way that feasible routes (i.e., rotations) are generated for the vehicles involved. Rotations and train compositions must be synchronized to ensure a railroad can cover all timetabled trips at the minimum cost—this is the rolling stock rotation planning problem.

Rolling stock rotation planning has additional constraints: in particular, maintenance rules and station and parking requirements. The FEO system handles these constraints; however, although they are important, we do not discuss them in this paper.

Uses for Rolling Stock Rotation Planning

The rolling stock rotation planning problem is relevant to several DB business processes. Rolling stock rotations are first considered in developing the strategic plan, which is devised 10–20 years prior to its implementation. The strategic plan includes the creation of a prototypical timetable for a standard week (i.e., a week that repeats indefinitely in a cyclic fashion). In a cyclic timetable, the vehicle routes are cycles that extend over one or more weeks (hence, the term rotation); we illustrate this in Figure 6. The standard week is useful in evaluating the feasibility or cost of a timetable with respect to an existing fleet or fleet procurement. The tactical plan, which is developed approximately five years before its implementation, includes the development and differentiation of summer and winter timetables and establishes the transition between them. It also considers long-term construction sites in the railway track network.

In the operational plan, which is developed one year (or sometimes less than one year) prior to its implementation, holidays, important events such as major exhibitions, and most importantly, construction sites are considered on a fully dated basis (i.e., for specific days in a calendar period) and in increasing detail, as additional information becomes available. For this purpose, the standard week is rolled out over an acyclic (i.e., noncyclic) planning horizon with a start date and an end date (e.g., December 1, 2021, to December 31, 2021), adding information for specific days (e.g., extra trips during the Christmas season); see Figure 7 for an illustration. A fully dated scenario involves more timetable data. It also shifts attention from the consideration of exchangeable vehicles (or vehicle types) to the planning of individual vehicles with specific characteristics, such as start and end positions, maintenance states, and home depots. Using our approach, an individual vehicle can be modeled as a unique and distinct vehicle type; however, this may come with a drawback. For example, the resulting increase in the number of trips and the number of vehicle types initially makes the fully dated problem appear to be much harder to solve than its cyclic counterpart.

However, fully dated problems are not optimized from scratch. The purpose of strategic and tactical planning in FEO is to construct a set of base schedules that are modified only in the fully dated scenarios, thus allowing DB to provide operational stability. The purpose of planning one year ahead or less than one year ahead is to adapt the schedule to a previously generated base plan. Planners should follow the base plan whenever the planning department considers doing so to be feasible and cost effective; a planner who deviates from it should return to following it as soon as possible. This approach is similar to the use of base routes in the UPS package delivery approach (Holland et al. 2017).

Such a reoptimization setting requires, as an additional input, a base plan that is used as a scheduling template to penalize deviations. This base plan is usually infeasible for the current scenario; otherwise, we would not have to adapt it. Nevertheless, a base plan provides enough guidance to compensate for the increase in size, such that fully dated reoptimization scenarios are different but not substantially harder to solve than an optimization developed from scratch in the base case. In reality, the computationally hardest problems are found in strategic settings in which one has to determine the feasibility of a scenario in a fleet minimization run; we discuss such applications in section Tendering Regional Passenger Services and in the procurement cases we address in the section ICE Procurement and Construction Site Management.

The Hypergraph Model for Rolling Stock Rotations

At the heart of our operations research approach to rolling stock rotation planning is a novel model of the problem using hypergraphs. This model provides a mathematically elegant and unified treatment of all train composition and regularity requirements and for all optimization and reoptimization uses discussed in the previous section. It also provides the basis for a generalization of the theory of network flows and more generally, a generalization of algorithmic graph theory to “algorithmic hypergraph theory.”

Figure 8 illustrates this concept. Figure 8(a) shows two (standard) arcs that connect two pairs of nodes. Each node represents an arrival or departure event of a vehicle at a station and the state of the vehicle with respect to type, position, and orientation. The arcs that connect these state-event nodes represent the movement of a vehicle and the retention or change of its position and orientation (the type must stay the same). An arc from a departure to an arrival node represents the movement of a vehicle in a timetabled trip; an arc from an arrival to a departure event represents a movement (or just waiting) in a turn or a deadhead trip. Adding all possible state-event nodes and all possible transition arcs results in a vehicle scheduling graph. Flow on an arc reflects the transition from one node to another (e.g., a vehicle moving from one station to another). Two flows on two parallel arcs that represent the same timetabled trip indicate the use of two vehicles to service this trip; this can be used to model a double traction of two vehicles, as we show in Figure 8(a). Flow conservation results in vehicle rotations. The problem with this naïve flow model is that it provides no control of train compositions because each vehicle can move as if it was operated individually.

Figure 8(b) shows how to obtain this control by merging compatible standard arcs into hyperarcs. Such hyperarcs model feasible state-event transitions of train compositions. Adding (not adding) appropriate hyperarcs allows (rules out) train compositions on timetabled trips, turns, and deadhead trips. Figure 9 shows a more elaborate example with six trips, turns, and deadhead trips. As in a standard network flow model, flow conservation at every node results in a hyperflow that can be decomposed into rotations of the individual vehicles. The trips are covered because of flow constraints that enforce the use of exactly one standard arc or hyperarc for every timetabled trip. Rolling stock rotation planning thus amounts to solving a minimum cost hyperflow problem. This can in turn be translated into a binary integer program in which each hyperarc and standard arc becomes a binary decision variable. Because many train compositions are possible, many hyperarcs that reflect the underlying combinatorial complexity are also possible. In a full model, there are, for every trip, turn, and deadhead trip, as many hyperarcs as there are possible train compositions. However, this impairs neither the conceptual simplicity of the model nor its usefulness because hyperarcs can be generated dynamically using a column-generation approach.

The hypergraph approach can also handle regularity requirements. The ability to model simultaneous movements of several vehicles applies to both one trip and to multiple trips: that is, all repetitions of a generic timetabled trip on several days of a planning horizon. Running all such trips in the same way gives rise to regularity hyperarcs. Figure 10 shows an example of a regular turn from the everyday arrival of a set of regular timetabled trips on the left to the departures of another set of regular timetabled trips on the right. This regular turn can be modeled by using a hyperarc, as the example shows. Giving this hyperarc a reward in the objective function configures the model to prefer regularity. Other regularity requirements can be expressed similarly via suitable hyperarcs (which could become “hyperarcs of hyperarcs”).

Hypergraphs have thus far had limited popularity in the optimization community because they can result in large models that have little structure and are hard to solve. The hypergraphs present in rolling stock rotation planning, however, have a special structure; that is, all hyperarcs are unions of standard arcs, which we refer to as graph-based hypergraphs. The node-hyperarc incidence matrices of graph-based hypergraphs have only 0/ ± 1 coefficients, and all columns add up to zero, like standard network matrices (see the mixed integer programming (MIP) formulation in the appendix for details). Although hyperflow problems are provably hard (i.e., APX-hard) for even the simplest imaginable settings (Borndörfer and Heismann 2015), we found that instances arising from rolling stock rotation planning problems are computationally well behaved and provide strong lower bounds on the optimal objective value (Reuther 2017, chapter 7). Their structure can also be exploited to design a combinatorial hyperflow network simplex algorithm for the solution of the linear programming relaxation (Beckenbach 2018), which is currently in an early theoretical stage and not yet used for computations in FEO. These results indicate the potential to establish an algorithmic hypergraph theory based on suitable structures, such as those that are graph based. A number of theoretical results for related classes of hypergraphs, including a generalized Hall theorem for normal hypergraphs (Beckenbach and Borndörfer 2018) and a tight-cut decomposition algorithm for matching-covered uniformizable hypergraphs (Beckenbach 2019), corroborate this assumption. Hyperflow models are also potentially useful for other applications that involve a synchronization of paths, such as scheduling work for teams, truck-and-drone scheduling, or modelling chemical reaction networks.

Maintenance requirements, which are handled by using an additional model component of resource flows and consume resources along vehicle rotations (Giacco et al. 2014), cutting planes (Grimm et al. 2019), or path-based models (Lusby et al. 2017), have also been investigated. The mathematical details of the complete model are published in several articles, including Borndörfer et al. (2011, 2015, 2018, chapter 10) and extensively in Reuther (2017).

The Coarse-to-Fine Method for Rolling Stock Rotation Optimization

Hyperflow problems arising from actual business cases at DB cannot be solved by setting up an integer program and entering it into a standard solver. The major problem is the size of the hypergraph, which can have 10⁸ hyperarcs, each of which gives rise to a binary variable. Although direct hyperarc column-generation approaches provide better results, they are not sufficient in our situation. We found, however, that a hierarchical column-generation approach, which makes the major decisions on a coarse (and hence, computable) level and checks the position and orientation details on a fine level, is a workable approach. In the algorithm we implemented in FEO, we use three levels (i.e., layers), which we define in Figure 11. The resulting hierarchical pricing algorithm is called the coarse-to-fine (C2F) methods (Borndörfer et al. 2014, 2018, chapter 10). The C2F approach is not limited to rolling stock rotation optimization but is applicable to large-scale linear programming in general. Reuther (2017) includes an in-depth presentation.

The C2F method is inspired by the expertise of DB planners and can be seen as a mathematical formalization of a procedure that has been used successfully over a long period. DB planners knew that tackling a dedicated scenario often requires making a relatively small number of key decisions. For example, suppose we know the number of vehicles and have information about some essential deadhead trips with crucial repositioning. Then, the remaining direct turns are often obvious, and further details (e.g., orientations and positions of the vehicles in the train compositions) are tightly restricted by the timetable and by technical constraints such that they frequently fall easily into place. The C2F method mirrors this approach in a mathematically precise and algorithmically powerful way.

The concept is to represent coarse and fine decisions in terms of hierarchical layers, as we illustrate in Figure 11. The finest layer is called the composition layer; it contains all details of the full hypergraph model. This is the model that we want to solve; the other two layers are relaxations (i.e., approximate models that have more solutions). The configuration layer is derived from the composition layer by ignoring the positions and orientations of the vehicles in a train composition. This layer represents the key decisions on which types of vehicles are combined and whether coupling and uncoupling operations must be performed. The configuration layer is a coarse hyperflow model of its own. Going one final step higher in the hierarchy, we also ignore vehicle types (e.g., white-filled and gray-filled types) and coupling requirements and arrive at the vehicle layer. This layer simplifies the problem to the computation of a standard single-commodity minimum cost flow. It reflects essential decisions on the number of vehicles needed and which deadhead trips are used. The layered construction has the property that the nodes and hyperarcs of the detailed layers have canonical representatives in the coarser layers, and vice versa, coarse nodes and hyperarcs correspond to sets of nodes and hyperarcs arcs in the finer layers. In this way, compositions can be mapped to configurations, configurations to individual vehicle movements, and vice versa; see Borndörfer et al. (2011, 2015) for details. The particular mappings between compositions and configurations and between configurations and standard flow arcs are inspired by the problem structure and the planning expertise of DB experts.

The layers are used to implement a hierarchical column-generation algorithm that yields efficient pricing rules and strong, exact pruning. Briefly, the algorithm prices on the coarsest layer and checks the implementation of the resulting coarse solution on the induced part (and only on the induced part) of the next-finer layer and recursively on the finest layer (i.e., overall over two layers). Then, the induced part of the finest layer is used to compute shadow prices (i.e., a dual solution), and the method iterates. In this way, the algorithm can exploit the simplicity and reduced size of the coarse layers and yet check detailed and complex rules on the fine layers. To compute the shadow prices and to guarantee that the procedure finds the fine linear programming optimum, an algebraic linear programming (and finally, integer programming) implementation of the C2F method must be derived. Its mathematical core is a “coarsening lemma,” which ensures that the reduced costs in coarse layers always overestimate the attractivity of arcs or hyperarcs in the finer layers. That is, the coarsening lemma proves that coarsening produces relaxations. This ensures the theoretical convergence of the C2F method. In practice, the integer programming optimum is often reached to a persistent duality gap that is small enough that one can prove the optimality of the computed fleet size by means of reduced cost arguments. The FEO implementation of the C2F method is fully parallelized in various ways. Run times vary between a few minutes for easy reoptimization scenarios to several days for large-scale scenarios that may be infeasible.

The FEO System

The FEO decision support system allows planners to edit, manage, visualize, optimize, and analyze rolling stock rotations using advanced functionality. FEO is a multiple-tier application featuring a fat windows client, which interacts with a central server component in the enterprise cloud. The server is connected to a single database and can distribute computing tasks to multiple optimizer instances in a flexible and scalable way. The FEO graphical user interface (GUI) gives access to all relevant data through configurable lists and freely scalable Gantt charts, including tool tips that provide detailed information (Figure 12). The GUI is client specific; that is, different versions are available for the various DB divisions. The FEO versions are configured automatically based on the role of the software user.

Setting Up a Scenario

The availability of high-quality data, which is a conditio sine qua non for optimization, and fixing faulty data are major problems that can seriously impair user acceptance; indeed, planning experts consider them as dumb data-scrubbing activities that keep them from their creative planning work. The development of a working database is therefore a top priority. Despite all efforts, however, the data delivery systems may not be of sufficient quality, or necessary data may be missing. FEO mitigates this problem by detecting and reporting issues as lists of errors or warnings that describe the problem found (what) and provide a reference to the input (where) using railway terminology, such as train numbers and station names. FEO includes powerful editors that allow the postprocessing of complex data sets.

Some real-world requirements may not be covered fully or may be covered only by making a disproportionate effort. For example, including rarely applied exceptions, such as scheduling turns without the typical slack time, would require unnecessary effort. Such exceptions are not only allowed, they are sometimes necessary. When they are applied, they require only some small but well-specified adaptions to allow FEO to find a much better solution. For such cases, FEO offers interactive planning options that are implemented via a drag-and-drop user interface, including filtering, and embedded reporting functionality; examples include the number of kilometers since the last maintenance event and statistical data regarding historical delays (Figure 12).

Working with FEO

Business use cases typically require more than one call to FEO’s optimization algorithm. An optimizer will exploit errors (e.g., a driving or turning time of zero is attractive for the optimizer but is probably wrong) to construct solutions that cannot be implemented. When such flaws become apparent, they must be fixed in a subsequent optimization. In addition, a scenario may be infeasible, or computed turns may be incomprehensible (why did the optimizer do this?). In such cases, additional side constraints, objective function adjustments, and data fixes must be identified to clarify the situation. The FEO design includes several functions to support these optimization-evaluation issues. For example, in addition to consistency and plausibility checks, FEO categorizes the input data into hard data that cannot be changed and soft data that can be changed if the user confirms the changes. FEO also provides an editor for exceptions to overrule soft data. If the optimization results are not as expected, FEO can suggest adaptations (i.e., small changes to soft input data) to obtain better results. After an initial phase of data cleaning, parameterization, and the development of FEO profiles for typical use cases, this process is now smooth. Where a single solution was constructed formerly, FEO now usually offers four to five solutions, which a user can compare, analyze, and then choose the best one.

Reoptimization

One of FEO’s most important optimization functions is the reoptimization of rolling stock rotations. For this, an existing rotation (i.e., a reference rotation) can be passed to the algorithm. The reference rotation was typically created for a different scenario and might be suboptimal, infeasible, or even incomplete. The algorithm automatically configures its objective function to compute a feasible (optimal) solution that reproduces as many details of the reference rotation as possible. This is useful in a wide range of applications. One is to deal with operational disruptions (e.g., by fixing rotations that cannot be implemented because of construction sites or timetable changes). Another is to impound regularity by deriving fully dated rotations from a base plan. A third is scenario exploration. A particularly important aspect of reoptimization is that it can make optimization results transparent to the planner. In reoptimization, the algorithm tries to keep as much as possible of a reference rotation, which the planner can create manually. This simplifies the planner’s focus on the differences. Thus, many obscurities and doubts can be quickly resolved. Reoptimization is algorithmically supported by warm starting the optimizer, which guarantees short run times. The similarity of rotations can be controlled via configurable templates; see Borndörfer et al. (2017) for details. Such a reoptimization is usually much faster than a computation made from scratch.

Timetable Improvement

Another popular feature is FEO’s ability to identify advantageous shifts of timetabled trips. For this purpose, variables and constraints reflecting the timetable modifications are added to the basic model. For each timetabled trip, variants (shifted copies of the original trip) are added within some time interval, as are constraints stipulating that FEO must choose exactly one variant and penalties that represent the cost of the associated timetable change (the more extreme the shift, the higher the cost). Because the original trip has no change costs, FEO tries to keep as many trips as possible in their original time slots. If FEO finds a better overall solution (i.e., the benefits outweigh the change costs), it reports a suggested solution to the user.

Handout Optimization

FEO includes a feature that improves the look of rolling stock rotations to make them more readable for planners by enabling them to visualize the regularity of rotations, as Figure 13 illustrates. FEO optimizes the rotation handout using a clustering approach; see Borndörfer et al. (2019) for details.

Simulation

FEO can simulate future operations up to 52 weeks in advance; see Öztürk (2015) for details. The purpose is to detect several months in advance if and when additional vehicles will be required because of additional services or timetable changes resulting from construction work. The challenge here is not only to ensure that the trains will still run (additional vehicles can be rented to service additional trips) but to also satisfy crew planning and dispatching requirements. In particular, previously planned rotations should not be assigned to different types of vehicles because drivers are frequently qualified for only specific vehicle types. Early detection of such situations enables foresight in crew planning (e.g., vacation planning) to ensure the availability of drivers with the right qualifications.

Reporting and Scenario Management

An FEO solution can be inspected using various reporting options, and the user is encouraged to experiment with different settings. To analyze and compare different schedule variants, FEO supports sophisticated scenario management. A scenario combines specific data sets in various domains into a complete set of data as required by the optimizer. FEO allows temporarily inconsistent settings while the user works on the data, thus enabling that user to quickly make small changes. When the optimizer starts, it does a validity check to ensure that all data references can be resolved. With many users and use cases, the set of scenarios can become confusing. FEO allows users to see only data sets and scenarios that are relevant to them while enabling them to also work on the same consistent set of core data.

FEO Development

The FEO system was developed by DB Analytics, DB’s internal service provider for analytics, forecasts, optimization, and simulation. The project began in 2008 and followed the agile software development philosophy. Throughout the endeavor, users from the three transport divisions of DB worked closely with the software development team to ensure the project’s success. User integration was a key success factor for FEO in the early use cases. The mathematical component required research, which was carried out in cooperation with Zuse Institute Berlin (ZIB), a research institute in applied mathematics. The cooperative agreement was in place for almost 11 years and encompassed several phases. During these phases, the research was partially supported by the German Federal Ministry for Research and Education (BMBF), the Matheon Research Center, and the BMBF MODAL Research Campus. Since the successful implementation and integration of the optimizer, the ZIB spin-off company, LBW Optimization GmbH, has provided additional development, maintenance, and support.

FEO Success Stories

FEO was implemented in direct response to the 2007 liberalization of the regional and cargo railway markets in Europe. It immediately became clear that tendering for regional transport was a question of implementing a service using the minimum number of vehicles. Similarly, crossborder operations required different locomotives for each country and thus, resulted in high fixed costs for freight traffic. Optimization was therefore the key to winning or losing business. DB’s long-distance transport division was under pressure to implement the timetable subject to an increasing number of construction sites, as we explain. These presented, and still present, considerable challenges—but also, significant opportunities. Railroad transportation volumes have increased steadily in the past two decades (Federal Ministry of Transport and Digital Infrastructure 2020). Between 2001 and 2018, the numbers of long-distance and regional railway passengers in Germany rose by almost 10% and 46%, respectively (Federal Ministry of Transport and Digital Infrastructure 2020, pp. 216–217), and contrary to public perception, freight traffic tonnage rose by almost 35% (Federal Ministry of Transport and Digital Infrastructure 2020, pp. 240–241). The growth in passenger and ton kilometers is even more significant as people and goods are being transported over increasing distances. Long-distance and regional passenger kilometers have increased by 22% and 37%, respectively, (Federal Ministry of Transport and Digital Infrastructure 2020, pp. 218–219), and ton kilometers have increased by 64% (Federal Ministry of Transport and Digital Infrastructure 2020, pp. 244–245). To meet this rising demand, the German government and DB have established a long-term investment program valued at 156 billion euro (€) through 2030, with an objective of substantially expanding the capacity of the network. FEO was designed to seize these opportunities and to address the challenges through smarter planning of rolling stock rotations.

ICE Procurement and Construction Site Management

DB’s long-distance passenger transport division, DB Fernverkehr AG, uses FEO for both strategic and operational planning purposes. It achieved its first major benefit in 2009 when it used the optimizer in its strategic planning department to support the procurement of the new ICE4 fleet. Its planners performed extensive scenario analyses to determine the number of train sets to procure, their sizes (i.e., numbers of coaches), and whether the units should feature clutches to allow for double traction (like the ICE2) or should not (like the ICE1), and they made a decision to order 130 train sets of 7 cars and 90 train sets of 10 cars, all without clutches.

Since the rollout of FEO in 2013, its main use has been in construction site management. Construction sites force detours (which cost time and mileage) and sometimes result in service splits. For example, a line A-B-C-D might be split into two lines A-B and C-D if a construction site at segment B-C cannot be bypassed; as a result, passengers and vehicles cannot proceed from B to C. Detours and service splits can (theoretically) be addressed by employing additional vehicles, which are not part of the vehicle fleet available in practice, or by service cancellations, which result in loss of revenue and customer dissatisfaction—consequences that DB wishes to avoid. Because of the mentioned network capacity expansion program, DB Fernverkehr must contend with a record high number of construction sites—currently 850 per day. Thus, scheduling trains through bottlenecks and around temporarily closed track segments, while also maintaining a sufficient level of regularity, is increasingly difficult. Maintenance is a particular complication. To avoid expensive deadhead trips over long distances, the rolling stock rotations would ideally automatically pass by the proper maintenance facilities, further adding to the complexity of the scheduling task. In Figure 14, we illustrate how we used FEO to manage the disruption that construction sites can cause.

In addition to the example in Figure 14(b), we used four dedicated cases from the fourth quarter of 2019. In each, we analyzed FEO solutions in detail to compare its final optimized solutions with alternative manual ones and assess the impact. For the construction sites shown in Figure 14(a) (Gelnhausen (construction duration 3 days, start of October; marked as G), Offenbach (3 days, middle of October; marked as O), Dollbergen-Fallersleben (6 days, start of November; marked as D), and Ulm (38 days, November/December; marked as U)), FEO recommendations were used to prevent service cancellations of approximately 28,200, 21,300, 8,100, and 304,000 kilometers (km), respectively, (i.e., 360,600 total train km). Extrapolating this to an annual value, FEO allows DB Fernverkehr to drive roughly 1 million additional train km with the existing fleet. This equals the annual mileage of two ICE double-traction train sets and would generate additional fare revenue of approximately 24 million € per year or equate to the transport of 784,000 additional travelers. Each train journey saves around 44 kilograms of CO₂ in comparison with the amount that would have been expended had each passenger driven an automobile. Thus, FEO saves approximately 34,000 tons of CO₂ emissions per year.

The construction sites pose a serious problem because of the significant planning effort that must be made for each of them and for their combinations in the face of constant time shifts. Considering 850 construction sites per day, avoiding business losses related to managing around these sites is extremely important, and FEO has been of considerable help in preventing these losses.

Tendering Regional Passenger Services

All regional passenger traffic in Germany is tendered by the states of Germany. Train operating companies (TOCs) such as DB’s regional transport division, DB Regio AG, can apply in these tenders; the TOC that requires the lowest public subsidy in its offer usually wins the contract for a period of up to 15 years. The long length of the terms reflects the refinancing periods of the vehicle procurement costs. These costs are enormous and can range from 50,000,000 to 400,000,000 € for a single order. To win a tender, a TOC must determine the size and type of fleet that results in the most favorable operational plan. For this purpose, a TOC must study a large number of fleet variants (often 5–30 variants) in a short time (e.g., two to three weeks). Each variant requires studying different scenarios and operational procedures, performing sensitivity analyses, and forecasting delays.

We describe three documented cases in which FEO was instrumental in winning a tender for the state of Baden-Württemberg in the southwest of Germany. These are the tenders Netz 3b from Stuttgart to Crailsheim (2.1 million train km per year) (Ministry of Transport Baden-Württemberg 2015), Netz 4 (4.8 million km per year) (Ministry of Transport Baden-Württemberg 2017), and Netz 7b (4.5 million km per year) (Ministry of Transport Baden-Württemberg 2019), which together cover a mileage of roughly 11 million train km per year; see Figure 15.

DB Regio won the Netz 3b tender by implementing all timetable and vehicle reserve requirements using one vehicle fewer than the intrinsic minimum fleet size: that is, 16 BR 442 Bombardier Talent 2 one-story electric railcars. Undercutting the minimum fleet size enabled DB Regio to offer services at a price lower than its competitors. The tender was designed to permit small service tasks (e.g., cleaning) on reserve vehicles. The vehicles could be repositioned for this purpose, and such a repositioning would not interrupt the required reserve time window of 24 hours. However, the terms also permitted a deadhead trip of a reserve vehicle between two stations within the reserve time. One of DB Regio’s planning experts noticed this and realized that FEO could exploit it to construct a solution that saved one vehicle. Although this solution was considered to be unorthodox and the crucial deadhead option was disallowed for future tenders, it was instrumental in helping DB Regio to win the Netz 3b tender.

Extensive coupling/uncoupling was the key to winning the Netz 4 tender. The tender consisted of two lots. Lot 1 was for fast regional express trains between Karlsruhe, Offenburg, and Basel. Lot 2 was for the “Breisgau S-Bahn” commuter trains, which stop at every station and need strong acceleration. Demand was high around the three regional centers of Karlsruhe, Freiburg, and Basel but low in between these centers. The tender therefore stipulated capacities that varied between 800 and 400 seats on the respective segments. These requirements could be satisfied by always using large vehicles or by alternating between single, double, and triple tractions of small vehicles. The latter concept requires permanent coupling and uncoupling, which is much more complicated to operate and requires a second engineer; however, it reduces mileage and maintenance costs and is the most efficient solution. DB Regio won both lots. The key to this success was to use vehicles with excellent driving dynamics: in this case, 15 BR 462 Siemens Desiro HC electric railcars with 410 seats for Lot 1 and 24 BR 463 Siemens Mireo electric railcars with 215 seats per vehicle for Lot 2. These vehicles could be operated in such a way that specific arrival times could be advanced by one to two minutes. These timetable changes in turn enabled coupling and uncoupling operations at stations, at which (un-)coupling was not possible using the “traditional” timetable included in the tender. FEO provided the analytics to verify the feasibility of this complex operation and to evaluate the financial impact of this novel and superior concept.

DB Regio won the Netz 7b tender in essentially the opposite way. The tender consisted of two lots. The Complex Lot 1 was for the “Karlsruher Netz.” It seemed to require a mixed operation of single and double tractions to serve varying capacities between 140 and 280 seats similar to Netz 4. Likewise, Lot 2, the “Nordbaden Express,” stipulated capacities between 200 and 400 seats. Again, coupling is important, but the timetable in this case favored the use of large vehicles, although their use required significant and counterintuitive overcapacities on some segments. Over the tendering period of 13 years, the higher procurement costs of large vehicles are outweighed by smaller operational costs; that is, replacing couplings by overcapacities is cost effective. To win this tender, DB Regio acquired 19 BR 440 Alstom Coradia Continental electric railcars (6 large ones with five units and 13 small ones with three units) for Lot 1 and 7 BR 463 Siemens Mireo electric railcars with three units for Lot 1.

To distinguish between cases such as the Netz 4 and Netz 7b tenders, which initially seemed similar, precise operational costs had to be computed over a period of more than a decade. These calculations would have been impossible without FEO. However, the cases also testify to the importance of human creativity. The successful offers relied on innovative ideas. In all three cases, the same expert planner identified pivotal optimization opportunities and used the FEO decision support system with its powerful optimizer to explore, evaluate, and finally implement these concepts. This represents DB Regio’s best practice in tendering.

Crossborder Freight Rail Operations

DB’s freight transport division, DB Cargo AG, uses FEO for strategic and operational locomotive scheduling. In contrast to passenger transport, the rail freight business is highly demand driven. Transports are volatile, and operations often do not follow synchronized timetables on standardized train routes. The main challenge is crossborder operations, which constitute more than 60% of DB Cargo’s transports (Figure 16). Because the European railway infrastructure has not yet been harmonized (e.g., the electrical power systems, the signaling/train control systems, and the safety standards differ), engines must be changed if they are not interoperable; this incurs coupling work (Figure 17). Traffic from the large North Sea harbors of Rotterdam and Hamburg along the Rhine and across the Alps to the industrial centers of northern Italy crosses several countries and hence, can require several locomotive changes. Because the price of a locomotive ranges between 2 and 5 million €, efficiently employing these resources is critical.

DB Cargo started to use FEO in 2010 to optimize the locomotive operations in Belgium and France. At that time, more than 10 locomotive types were in use, many of them from the first generation of electric locomotives from the 1960s (locomotives can be used for several decades). The old locomotives were long depreciated and so, were inexpensive from that financial perspective. However, they used considerable energy, acquiring spare parts was a problem, and they required qualified drivers. A FEO analysis showed that putting 10–15 old locomotives out of service would be cost effective, necessarily increasing the mileage of the modern ones. Implementing this solution was a forerunner of later locomotive standardization at DB Cargo.

The Belgium Hinterland traffic was further optimized in 2011. It consists of oil, gas, automotive, and intermodal (i.e., container) transports, which are often time critical. Using FEO’s timetable improvement feature, 3 trains (of over 400) were identified, such that shifting them by as little as one hour would require two fewer locomotives. Implementing the shifts involved negotiations with the customer and the infrastructure provider. The timetable improvement was a huge success and has subsequently become a primary FEO application at DB Cargo.

Alpine transit operations were optimized in 2016 in connection with the opening of the Gotthard basis tunnel. These operations, which feature heavy trains loaded with containers, steel, scrap, minerals, and tiles, were operated using a diverse locomotive fleet. By an integrated optimization of these transports, including a timetable improvement, the number of locomotives required was reduced from 30 to 25.

All of these results testified to the significant benefits that could be derived by overcoming assignments of dedicated locomotives to individual services. However, this traditional concept is not devoid of advantages. Such transports are extremely reliable because they are not impacted by delays caused by other customers, which is a serious problem in rail freight transport. Using dedicated locomotives ensures a high quality of service and a high level of customer satisfaction. Would it be possible to establish a more integrated and more resource-efficient operation with a reasonable level of quality? This key question could, for the first time, be analyzed with FEO and was answered in the affirmative. One consequence was the introduction of a hub-and-spoke system in which the expensive intermodal locomotives circle between long-distance hubs and cheaper locomotives implement national distribution in the spokes. These concepts were successful and achieved an average increase in efficiency of between 3% and 5%. Extrapolated to the entire fleet of more than 2,700 locomotives, this amounts to annual cost savings of 27 million €.

DB Cargo is now moving toward integrated operations with standardized locomotives. This new strategy became palpable in DB Cargo’s biggest strategic investment during the past decades: that is, the procurement of a new fleet of 104 interoperable third-generation BR 193 “Vectron” locomotives for standardized crossborder operations. The support of this procurement was one of the biggest successes attributable to FEO. As compared with the ICE4 procurement at DB Fernverkehr, the problem involved not only determining the number of locomotives and their types (a locomotive can be equipped for only five to six European countries, not for all) but also, redesigning the crossborder operations per se. Using FEO, DB Cargo was able to address this problem. The first of the new engines has been in use since spring 2019 and has already improved on-the-job safety by eliminating 600 coupling operations per year.

The increasingly integrated and standardized production is revolutionary for DB Cargo’s operations. It requires a constant and careful balancing of resource integration and customer satisfaction subject to complex operational constraints in a volatile market. FEO showed that this strategy is viable and helped DB Cargo to implement it.

Summary of Benefits

The optimization of railway systems taps significant, but previously unused, potential to increase the efficiency and the quality of rail transport services. These stem from an optimization of existing production processes as well as from the ability to explore new concepts. Mastering the combinatorial complexity, the integrated use of resources, and improved scheduling processes are key components. We have shown how the use of advanced mathematical optimization methods in combination with human creativity resulted in the following benefits, which can be attributed directly to FEO: (1) annual savings/revenue increases of 74 million € (i.e., 24 million € at DB Fernverkehr, 23 million € at DB Regio, and 27 million € at DB Cargo); (2) savings in CO₂ emissions of 34,000 tons per year; (3) elimination of 600 coupling operations per year; (4) increased regularity of operations when managing construction site delays; (5) greatly increased flexibility, ease, and speed of planning processes; (6) new company-wide planning practices; (7) evaluation and implementation of new and superior production concepts; and (8) progress in railway optimization and the implementation of algorithmic hypergraph theory.

FEO’s hypergraph-based operations research approach addresses the key problem of rolling stock rotation optimization and provides DB’s planners with a powerful tool that helps them to reinvent the rail transport of the twenty-first century. Of all means of transportation, railways have the greatest potential to become the comfortable, fast, efficient, and environmentally friendly conveyance of the future. Operations research provides the methods to allow companies to make smarter planning and control decisions. Rail transport is on the right track—for the people, the economy, and the environment.