Minimizing the Number of Trains
Railway companies face the very important problem of minimizing the number of trains needed to fulfill a given schedule of train routes. This problem, known as the fleet size, rolling stock rostering, or vehicle routing problem, is very hard to solve efficiently in a realistic setting. Minimizing the number of locomotives and cars needed to fulfill a periodic schedule can drastically reduce costs of a railway company.
TrainRouting solves this problem. It concerns a large set of constraints and requirements and computes in a small number of seconds an almost optimal number of trains needed and the routes of locomotives and cars. Some of these requirements are: several different train unit types, different station turn around times, and a lot of different maintenance requirements.
The main objective of TrainRouting is minimizing the total costs of a rolling stock rostering. In order to work properly TrainRouting needs as input a schedule, information about train units, and a set of three different cost functions: fixed costs, costs per ride, and maintenance costs.
All input and output is read from and written into a standard database. An additional stand-alone viewer reads this database and visualizes the rolling stock rostering in a user-friendly and intuitive way.
Facts and Numbers
TrainRouting is based on a three phase optimization approach: first, the train length phase is solved, in which the lengths of the trains on each route (including empty and piggy-back rides) are determined. In this phase rides are only assigned to train unit types, but not to specific train units. In the second phase, the train assignment problem is solved: specific train units are assigned to the scheduled rides. For each train unit a rotation is determined. These two phases are solved optimally by building a directed graph of events and rides with costs and finding a minimum cost flow on it and then extracting rotations from the minimum cost flow. In the third phase, the maintenance insertion problem is solved by various heuristics.
TrainRouting is able to handle a wide variety of requirements and expense factors:
- Requirements: different train unit types, minimum station turn around times, maintenance (different types, different intervals, special stations).
- Costs: fixed costs per train unit, costs for each ride (energy and time), maintenance costs.
TrainRouting finds in railway networks with more than fifty concurrently running train units a saving potential of approximately ten percent. The computation time depends mainly on the number of train units needed for a given schedule. On a standard PC it takes a few seconds only for realistic problem instances with up to 120 train units.
Examples
The images show screenshots of our visualizing tool for rolling stock rosters. The provided examples are rosters computed by our software with realistic data. In the images a horizontal line represents a roster of an individual train unit during a whole week, beginning on Sunday midnight. The sloped end of a bar represents the position of the locomotive of a push-pull train.
Each colored bar on such a line marks either a ride between two end-stations or a maintenance stop (red). The color of the bar shows the type of the ride (productive, empty movement, etc.). A rotation is a periodic route of one or more train units. Rotations are separated by dashed lines.