ERCIM News No.20 - January 1995 - CWI
by Henk Nieland
The Dutch railroad-system is one of the busiest in the world. Designing for this system a timetable for the 21st century, in which both future customer requirements and efficient use of infrastructure are taken into account, is an extremely difficult task. CWI has succeeded in developing a practically usable software package, CADANS, which generates such timetables and indicates bottlenecks. This ongoing research is commissioned by RailNed, the company running the infrastructure of the Dutch railways.
A software package generating timetables for the Dutch railroad-system, one of the busiest in the world, has been developed at CWI (Photo: Nederlandse Spoorwegen)
Some specific problems in the Dutch railroad-system are the short lengths of trajectories, the large number of connections, to be realized simultaneously, and the short change times. There are thousands of interrelated constraints to be satisfied, such as desirable frequencies, connections, arrival and departure times, railroad section load, availability of rolling stock and distances between trains. In addition, customer requirements have to be weighed against infrastructural development.
Until now railroad timetables were mainly hand-made. Bottlenecks were redressed without having an insight into the consequences elsewhere in the network. Recently CWI's Combinatorial Optimization and Algorithmics group, led by Lex Schrijver, has developed the software package CADANS (Combinatorial Algebraic Timetable Algorithm for Dutch Railways), which produces on the basis of a set of initial constraints a timetable in a reasonably short time (a matter of minutes on an average computer). Conflicting situations are conveniently laid out, thus enabling the planner to take adequate measures. The CWI solution is flexible in the sense that constraints can easily be changed or added.
An important feature of the system is its hourly cadence. This constraint turns the problem into an integer programming problem, in which some five thousand inequalities have to be satisfied and a number of variables take only integer values. This type of problem is far more difficult to solve than linear programming problems. The problem can be described as one of finding a potential in a directed graph, with values in the cyclic group C60 with 60 elements, when on each arc the tension belongs to a prescribed interval on C60. If the graph has a cycle on which the intervalsare `too short', we obtain a bottleneck, which is returned by CADANS. Also larger subgraphs can form a bottleneck, which CADANS can return as well. If CADANS yields a feasible timetable, it can be optimized with the help of linear programming.
cwi.nl