Heuristics ancient and modern: Transport scheduling through the ages

Heuristics which have been developed for transport scheduling over a lengthy period starting in 1960 are presented. They are generated in response to requirements to solve practical problems, and most are now in regular use by bus and train companies. Mathematical programming models have been formulated for some of the problems, but have been inappropriate on their own; in some cases, heuristics have led to a reduced problem which has then been solved by integer linear programming. The paper is designed to illustrate the development of heuristics for a range of related problem areas over nearly forty years. It explores the relationship between heuristics and other approaches and emphasises the need to convince users of the suitability of the overall system. Where appropriate, indications are given of difficulties in achieving practical implementation.