Siemens AG R&D cooperated with Deutsche Bahn AG on railway station scheduling with AI methods and implemented a prototype capable of performing the day-to-day scheduling of a typical large station in Germany. The station chosen for this prototype is a large through station with 14 tracks and 6 platforms and a traffic flow rate of 68 trains per hour.

Portion of Preplanned Timetable

A sample station schedule

The computer system reacts to real-time scheduling problems which occur when trains are delayed; it then reschedules the arrivals minimizing the overall disruptance to the pre-planned timetable. The prototype operates under real-time conditions based on actual data samples, describing the rail network and its predetermined timetable.

The interactive tool also allows controllers to adjust the schedule to meet other station activities. For example, track and platform maintenance may be specified which may close portions of the network for several hours. Alternatively, non-scheduled arrivals may be added to the schedule and their priorities defined.

The figure above shows a portion of the sheduled timetable for the station. Platform numbers corresponding to the lettered platforms are indicated on the x-axis. Two additional tracks are indicated (40 and 80) which allow trains to pass through the station without passing a platform edge. Time is indicated on the y-axis. The illustration here shows a smaller portion of the timetable than is actually interpretable on a large monitor screen.

Scheduled trains may arrive from either end of the station, as indicated by the tags from- or to- the -left or -right; each train is also given a code. Known delays to certain trains are indicated below the trains arrival time.

In reality, three station controllers are responsible for the real--time allocation of incoming trains to platforms at this station. Their task is to minimise the number of passenger movements (where passengers must cross from their planned platform to a new platform), give priority to certain trains and also comply with all safety criteria.

The computer system models all aspects of the station and aims to assist the station controllers with the whole task. By specifying constraints that must be met in determining a new schedule the system searches for a good solution.

Many established rules and safety regulations specify fixed constraints: governing, for example: the time a crossing must remain empty to ensure the train has passed. These fixed constraints may not be broken in the new computed schedule.

Other, more flexible constraints specify the minimum time a train should remain at a platform, which is less than the pre-planned time.

When a regional train is delayed, the actual time the train passes over crossings to its designated platform will also be delayed; this may cause a knock-on effect to other lower priority trains which must therefore wait outside the station. Should a local train be delayed significantly, this delay may also cause a knock-on affect to regional trains which should connect with it. The rail-timetable itself specifies dependencies between trains, which guarantee that connections can be made by passengers.

The application computes the new schedule based on the amendments from the station controllers and the delays to certain trains. These time and allocation constraints restrict the timetable; the schedule must compensate by reducing the time trains remain at platforms or by delaying other trains or in the worst case by allocating train and passengers to another less loaded platform. Passenger movements where passengers must simply cross to the other side of the same platform are less disruptive than those where passengers must use the subway.

Portion of Rescheduled Timetable

A screen picture of the system

Clearly, for such a problem there is not one optimal solution for a given set of delays; an interactive system which is able to react on more subjective optimization criteria has therefore been developed. It displays graphically the time trains remain at certain platforms for passengers to exit and board. Having rescheduled the timetable, (shown above) the reallocations are displayed to the right of the orginal schedule and coloured according to the severity of impact on the station schedule.

Station managers may then specify that certain trains should remain on their original platform (perhaps a school party or an old lady is waiting!) and the schedule can be rerun. This rerun takes less than 20 seconds on a small UNIX workstation or PC and is sufficient to meet the needs of the real-time pressures of a large, busy railway station.

In total, the application consists of 15 000 lines of code representing 2 person years development. Approx. 1/3 of this code is for the Motif based graphics, also written in Prolog. IF/Prolog's Constraint Technology can be used to effectively express such problems in a convenient, readable form. IF/Prolog allows the developer to work on expressing the problem as rules and constraints rather than being forced to concentrate on designing a solver which may not include all necessary criteria.

IF/Prolog brings together many forms of data, specifying rules and constraints in a readable, modifiable form. The standard constraint solving technology then confines the problem, into a managable number of alternatives which may then be selected or adjusted by the station controllers who are then able to work with the problem at a much higher level.

Hardware : UNIX Workstation.

Software : IF/Prolog 5.0 with: Constraint Technology Package & OSF/Motif Programming Interface