In multi-day cyclic vehicle scheduling trips given by a timetable are scheduled (e.g. passenger trips by train) to a single large rotation or several small rotations. The rotations should contain all of the specified trips. The main goal of the resulting optimization problem is to find rotations with as few vehicles and empty trips as possible. For days of operation with similar trips the drive chains should be similar too (uniformity).
In addition, treatments (refueling, cleaning, ...) and maintenances of the vehicles must be observed. These treatments must be regularly performed in vehicle depots (depending on mileage, driving time, ...) and must be scheduled in the rotations. For each vehicle depot there are capacity conditions that limit the simultaneous parking of vehicles at the depot.
Description
Vehicles and their operations cause a large share of the costs of railway companies. Therefore their efficient use in operations is crucial for the profitability of these companies. In this project, we are developing a railway vehicle rotation optimizer called R-OPT. With this optimizer we are able to compute near optimal strategic schedules for trains and their vehicles not only with respect to the costs of these schedules but also with respect to the stability of the operations.
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 formations. A formation 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 formation to each of the timetabled trips. For every vehicle in a formation 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:- Maintenances
Maintenances are treatments that need to be performed at regular intervals on the vehicles. The frequency of execution may be dependent on the distance driven, the driving time, or the transit time. Examples for maintenance in our sense are: fueling, cleaning and various inspections.
- Capacities
For parking and maintenance the vehicle depots and stations have only certain capacities. These capacities may be limited by the length of the tracks, the number of personnel that is able to perform a certain maintenance at a certain point in time, or by the machinery needed to do a certain maintenance.
- Uniformity
In order to facilitate the duty scheduling and the preparation of schedules, the trips should be scheduled as uniformly as possible. This means that the drive chains on different days of operation are as similar as possible.
- Coupling
Creating and changing formations (aka coupling of vehicles) needs in practices personnel and equipment and also sufficient infrastructure such as tracks and switch points to be performed. The feasibility of a certain coupling operation may also be dependent of the orientation and position of a certain vehicle in a formation.
Model
Our basic mathmatical integer programming model consists of a Multicommodity Flow Problem enriched by constraints that control the formations.
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.
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.
