Always an Algorithm Ahead
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:
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.