Greedy heuristics for rapid scheduling of trains on a single track

Abstract

This paper describes the core algorithm used in an implementation of a scheduler currently being installed in a major Asian railway. It extends previous work on a greedy heuristic for scheduling trains, to provide a powerful and practically useful method that is fast enough for real-time use in many cases. Real-world railway systems have constraints that do not fit easily into a simple mathematical formulation. The algorithm described here makes it straightforward to incorporate many such realistic features.