Handbook of Optimization in the Railway Industry

From the long-term design of new infrastructure to the validation of timetables planners need accurate and reliable support tools that allow understanding the effect of their decisions. Microscopic simulation has gradually become widespread, since it allows considering not only the characteristics of infrastructure, signalling and rolling stock, but also human factors. In spite of this success and of the increasing quality of commercial simulation software, the setting up of a simulation requires time and accuracy to ensure that all elements are represented correctly.

Capacity assessment is essential for densely utilized railway networks. To guarantee stable operations, it is necessary to evaluate the capacity occupation and determine possible infrastructure bottlenecks. This requires accurate microscopic models that incorporate detailed infrastructure characteristics, signalling and interlocking logic, train characteristics, and driver behaviour. This chapter presents capacity assessment models based on a novel algebraic approach that builds on accurate running and blocking time computations. The capacity assessment should be undertaken on corridors, station areas, and networks, and as such, support a better understanding of the existing timetable constraints and possible infrastructure investments.

Rail freight traffic in Germany has experienced significant growth rates over the last decade, and recent forecasts expect this tendency to continue over the next 20 years due to the increases in national and international trade. Internal predictions of Deutsche Bahn AG, the most important German railway enterprise, assume a mean increase of 2% per year for rail freight traffic until 2030. At this pace, the German railway network in its current state would reach its capacity limit way before this date. As investments into the network infrastructure bear a very high price tag, it is crucial to use the available budget in the most efficient manner. Furthermore, the large size of the networks under consideration warrants the development of efficient algorithms to handle the complex network design problems arising for real-world data. This led us to the development of network aggregation procedures which allow for much shorter solution times by compressing the network information. More exactly, our framework works by clustering the nodes of the underlying graph to components and solving the network design problem over this aggregated graph. This kind of aggregation may either be used as a quick heuristic, or it can be extended to an exact method, e.g. by iterative refinement of the clustering, The latter results in a cutting plane algorithm, which also introduces new variables with each refinement. This idea developed in Bärmann et al. (Math Program Comput 7(2):189–217, 2015) is extended in this chapter such that it is able to incorporate the costs for routing flow through the network via lifted Benders optimality cuts. Altogether, our algorithm can be seen as a novel kind of Benders decomposition which allows to shift variables from the subproblem to the master problem in the process. Computations on several benchmark sets demonstrate the effectiveness of the approach.

This chapter is about strategic routing of freight trains in railway transportation networks with mixed traffic. A good utilization of a railway transportation network is important since in contrast to road and air traffic the routing through railway networks is more challenging and the extensions of capacity are expensive and long-term projects. Therefore, an optimized routing of freight trains have a great potential to exploit remaining capacity since the routing has fewer restrictions compared to passenger trains. In this chapter we describe the freight train routing problem in full detail and present a mixed-integer formulation. Wo focus on a strategic level that take into account the actual immutable passenger traffic. We conclude the chapter with a case study for the German railway network.

Timetabling is a central step in the planning of public transport and important for the quality of service. Thereby, it also faces requirements like punctuality, cost efficiency, flexibility and minimization of travel time. We show the state-of-the-art techniques and their extensions to new challenges, in particular, multi-period timetables and robustness. We conclude with a case study from the Italian Railways that shows the effectiveness of our robustness methods.

This chapter addresses the classical task to decide which train runs on which track in a railway network. In this context a track allocation defines the precise routing of trains through a railway network, which usually has only a limited capacity. Moreover, the departure and arrival times at the visited stations of each train must simultaneously meet several operational and safety requirements. The problem to find the “best possible” allocation for all trains is called the track allocation problem (TAP). Railway systems can be modeled on a very detailed scale covering the behavior of individual trains and the safety system to a large extent. However, those microscopic models are too big and not scalable to large networks, which make them inappropriate for mathematical optimization on a network wide level. Hence, most network optimization approaches consider simplified, so called macroscopic, models. In the first part we take a look at the challenge to construct a reliable and condensed macroscopic model for the associated microscopic model and to facilitate the transition between both models of different scale. In the main part we focus on the optimization problem for macroscopic models of the railway system. Based on classical graph-theoretical tools the track allocation problem is formulated to determine conflict-free paths in corresponding time-expanded graphs. We present standard integer programming model formulations for the track allocation problem that model resource or block conflicts in terms of packing constraints. In addition, we discuss the role of maximal clique inequalities and the concept of configuration networks. We will also present classical decomposition approaches like Lagrangian relaxation and bundle methods. Furthermore, we will discuss recently developed techniques, e. g., dynamic graph generation. Finally, we will discuss the status quo and show a vision of mathematical optimization to support real world track allocation, i. e. integrated train routing and scheduling, in a data-dominated and digitized railway future.

Deutsche Bahn, one of the largest European railway companies, offers mainly two products to commercial and industrial customers for freight transportation. Customers with high demand order unit trains, that are pulled by one or two locomotives from their respective origins to their destinations. In contrast, customers with less demand order a limited amount of single cars, that are first pulled to a classification yard. There they are grouped together with single cars from other customers into a train unit. On the way from their respective origins via intermediate yards to their destinations, the cars are reclassified several times, which is a time-consuming and personnel-intensive procedure. To support the strategic long-term planning process of the single car freight routing, a mathematical optimization tool based on mixed-integer nonlinear programming was developed and is in practice use since 2011. However, real-world constraints have changed over the last years. For example, unit trains and single cars are no longer strictly separated products, but they are more and more integrated: In some unit trains there are still residual capacities that can be used for single cars. For some of these additional new requirements, the existing optimization tool has to be extended slightly by formulating new additional mathematical constraints. For some other requirements, a substantial redevelopment will be necessary in the future. The purpose of this chapter is to review the existing single car routing model, to discuss how it is used in real-life, and to demonstrate how it can be extended to meet the new requirements in the present and future.

Railway freight shunting is the process of forming departing trains from arriving freight trains. The process is continuously performed at rail yards. The shunting procedure is complex and rail yards constitute bottlenecks in the rail freight network, often causing delays to individual shipments. One of the problems is that planning for the allocation of tracks at rail yards is difficult, given that the planner has limited resources (tracks, shunting engines, etc.) and needs to foresee the consequences of committed actions for the current inbound trains.

The required schedules highly depend on the particular infrastructure of the rail yard, on the configuration of inbound and outbound trains, and on the business objectives. Thus, new optimization tools as active decision support for the dispatchers are closely tailored to the actual processes. Due to its practical relevance, a broad range of variants has been discussed and solved by the scientific community in recent years. For selected relevant variants, we describe their fruitful relation to scientific research topics such as graph coloring, sequence partitioning, and scheduling, we discuss their computational complexity and approximability, and we outline efficient optimization procedures.

In particular, we consider a set of models and algorithms which are applicable in practice, and discuss their application to the shunting yards in Ludwigshafen, Germany and in Hallsberg, Sweden. We also discuss similarities and differences between the different approaches and outline the need for future research.

This chapter shows a successful approach how to model and optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical optimization problem is described in detail and solved by Rotation Optimizer for Railways (ROTOR), i.e., a complex optimization algorithm based on linear programming and combinatorial methods. ROTOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. We focus on main modeling and solving components, i.e. a hypergraph model and a coarse-to-fine column generation approach. Finally, the chapter concludes with a complex industrial re-optimization application showing the effectiveness of the approach for real world challenges.

This chapter deals with railway crew management, thereby focusing on the situation at Netherlands Railways (NS). NS is the main operator of passenger trains in the Netherlands. In this context, railway crew management is the process of guaranteeing in the most efficient way that the timetabled trains are supplied with a train driver and a sufficient number of conductors, thereby satisfying all the relevant practical constraints. Crew management has long term capacity planning aspects as well as short term scheduling, rostering, and dispatching aspects. In this chapter we describe these planning and dispatching processes, thereby focusing on practical issues. We also describe the planning support tools that are used by NS to support these processes.

Train rescheduling problems have received significant attention in the operations research community during the past 20–30 years. These are complex problems with many aspects and constraints to consider. This chapter defines the problem and summarizes the variety of model types and solution approaches developed over the years, in order to address and solve the train dispatching problem from the infrastructure manager perspective. Despite all the research efforts, it is, however, only very recently that the railway industry has made significant attempts to explore the large potential in using optimization-based decision-support to facilitate railway traffic disturbance management. This chapter reviews state-of-practice and provides a discussion about the observed slow progress in the application of optimization-based methods in practice. A few successful implementations have been identified, but their performance as well as the lessons learned from the development and implementation of those system are unfortunately only partly available to the research community, or potential industry users.

Should connecting trains wait for delayed feeder trains? Or is it better for the passengers if trains depart on time?

Questions of this type are the subject of delay management, which will be treated in this chapter from the point of view of the passengers. We start by discussing how delays are propagated through a public transportation network, and how such propagations can be modeled using event-activity networks.

We then focus on the question of finding an optimal solution to the delay management problem in case some (known) source delays have occurred. We discuss which decisions can be made and how these can be reflected by variables and constraints in integer programming models. In particular, we show how station capacities and the limited capacity of the tracks can be taken into account. Special emphasis will be given to the discussion of passenger-oriented objective functions. We introduce several ways on how to measure the effects that delays have on passengers and explain how to include the resulting objective functions in the models.

Next, we discuss solution approaches for delay management. In particular, we discuss heuristics that decompose the delay management problem and solve it within short computation times. Finally, we give some insights into delay management in practice. We review some simple delay management strategies used today and discuss recent developments that make it possible to implement more advanced methods in practice as well.