DEPARTMENT OF COMPUTER SCIENCE
MONASH UNIVERSITY

Clayton, Victoria 3168 Australia


TECHNICAL REPORT 96/250


Scheduling Trains with Genetic Algorithms

A Bud, A Nicholson and B Chandra

ABSTRACT

Scheduling trains is a complex problem that until recently has required the precise knowledge of experts to perform. Even with expert knowledge, it has traditionally been a slow and flexible process.

Although there are heuristics that solve this problem adequately for small simple rail networks, the general problem is much more difficult. In addition to the complexity of finding a solution, it is often necessary to recalculate the solution in "real time" in response to real world changes such as train delays, break downs, special trains and so forth.

This report details the application of a genetic algorithm to this problem. Using a two dimensional representation scheme, both mutation and crossover are used to guide the genetic algorithm to a valid solution.

Good results are presented for scheduling up to 16 trains on an 18 station railway, and there is no reason to believe that testing on larger more complex railways will take much greater time.

An analysis of the effects of varying a number of Genetic Algorithm parameters such as pool size, percentage of mutation, percentage of crossover and mutation sizes is presented to give some insight of how to optimise the performance of the algorithm and to give an idea of the geography of the solution space.

The approach to train scheduling demonstrated in this report offers new hope to an area of problem solving that has traditionally been both difficult and time consuming.