Always an Algorithm Ahead
R-OPT
Characteristics
R-OPT is an integrated algorithm for the optimization of train rotations for rail traffic. From the trips of a timetable, the algorithm simultaneously calculates efficient trip sequences and train compositions as well as necessary vehicle maintenance.
Description
Starting point for our optimization is a standard week consisting of different days of operations. For each day of operation there is a list of trips stemming from a timetable which has to be covered by vehicles. We call these timetabled trips.
Vehicles are the basis of the rotations which the optimizer will compute. However, in railway operations vehicles have to be combined to so called compositions.
A composition is a set of vehicles of probably different vehicle types which are coupled in a certain order to a driveable unit (sometimes also called a train).
The optimizer has to assign a composition to each of the timetabled trips. For every vehicle in a composition on a trip the optimizer also has to determine where it comes from and where it will go to. Thus, the vehicles on the timetabled trips are combined to a large rotation or to several small rotations. The rotations have to cover all the specified timetabled trips.
To determine which timetabled trips can be chained to be covered by the same vehicle, the optimizer needs information about driving time between important locations, minimum turning times on different stations and the layout of the tracks.
Railway companies typically have lots of technical constraints and regulations which have to be considered while creating the rotations, as there are:
Figure 1– cyclic solution of the planning problem (blue edges =
timetabled trips, red edges = standing times/deadhead trips)
Model
Our basic mathmatical integer programming model consists of a Multicommodity Flow Problem enriched by constraints that control the compositions. The planning graph contains (in each case several) edges for the planned trips and edges for the possible links of the passenger trips. The planning graph is cyclic, which means that the trips Sunday are again linked to the rides on Monday. Maintenances are considered in our model by layers in the planning graph.
This model differs from the one presented by Reuther et al., because it is adapted to be solved by a bundle method similar to the one developed to solve the integrated vehicle and duty scheduling problem. However, it captures the same base properties.
Algorithmical Approach
R-OPT works in two phases. In the first phase a near optimal solution of our mathematical model is computed by a rapid branching approach. This gives us an integer solution of a relaxed problem, that ignores some of the constraints and rules of the original problem. In the second phase we incorporate the missing features by an exchange heuristic, that does dynamic depth arc exchanges until no further improvement seems to be probable. This results in a local optimum, which is typically close to the lower bound we calculated in the first phase.
Application in practice
The rotation optimizer R-OPT is integrated in the planning system IVU.rail of IVU Traffic Technologies AG which is used by many railway companies around the world (see here). We are working hard to improve R-OPT on an ongoing basis and to incorporate new features. At the moment we are developing a rescheduling algorithm to widen the scope and improve the usability of our optimizer.