Citation

Kwan RS, Kwan AS, Wren A. Evol. Comput. 2001; 9(4): 445-460.

Affiliation

School of Computing, University of Leeds, Leeds, LS2 9JT, UK. rsk@comp.leeds.ac.uk

Copyright

(Copyright © 2001, MIT Press)

DOI

10.1162/10636560152642869

PMID

11709104

Abstract

Public transport driver scheduling problems are well known to be NP-hard. Although some mathematically based methods are being used in the transport industry, there is room for improvement. A hybrid approach incorporating a genetic algorithm (GA) is presented. The role of the GA is to derive a small selection of good shifts to seed a greedy schedule construction heuristic. A group of shifts called a relief chain is identified and recorded. The relief chain is then inherited by the offspring and used by the GA for schedule construction. The new approach has been tested using real-life data sets, some of which represent very large problem instances. The results are generally better than those compiled by experienced schedulers and are comparable to solutions found by integer linear programming (ILP). In some cases, solutions were obtained when the ILP failed within practical computational limits.

Language: en