Parallelisation Of A Genetic Algorithm For The Computation Of Efficient Train Schedules

Publication
Abramson, D., Mills, G. and Perkins, S. "Parallelisation of a Genetic Algorithm for the Computation of Efficient Train Schedules", Proceedings of 1993 Parallel Computing and Transputers Conference, Brisbane, pp 139 - 149 Nov 1993, IOS Press
Abstract
This paper discusses the parallelisation of a genetic algorithm which computes train schedules. The program requires departure times for trains operating in two directions on a single-line track, and attempts to compute an optimal crossing plan which minimises lateness at the destination stations. Single-line track complicates the problem as trains are restricted to cross and overtake at fixed crossing locations.

Genetic algorithms require a problem to be coded as a string. The complexity of this train scheduling problem has resulted in a complex routine for decoding. This has resulted in longer calculation times which prompted the investigation of parallelisation techniques. The conversion of the code from single processor to multi processor calculations takes into account a number of different parallel computer architectures, including conventional sequential machines, shared memory machines, distributed memory multiprocessors and a network of workstations. The code was tested on a 16 processor Encore Multimax, a 128 processor Fujitsu APlOOO and a network of DEC Work Stations. Results are presented for the speedup attained. The best time was on the APlOOO, which achieved a 50 times speedup over its own urn-processor time.
Download
genalg_trainsched.pdf