Facts and Numbers

Train-Routing 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.

Train-Routing 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.

Train-Routing 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 less than three minutes for realistic problem instances with up to 120 train units.