Scheduling trains on a network of busy complex stations

Many countries have busy rail networks with highly complex patterns of train services that require careful scheduling to fit these to the existing infrastructure, while avoiding conflicts between large numbers of trains moving at different speeds within and between multi-platform stations on conflicting lines, while satisfying other constraints and objectives. However, the construction and coordination of train schedules and plans for many rail networks is a rather slow process in which conflicts of proposed train times, lines and platforms are found and resolved ‘by hand’. Even for a medium size rail network, this requires a large numbers of train schedulers or planners many months to complete, and makes it difficult or impossible to explore alternative schedules, plans, operating rules, objectives, etc. As a contribution towards more automated methods, we have developed heuristic algorithms to assist in the task of finding and resolving the conflicts in draft train schedules. We start from algorithms that schedule trains at a single train station, and extend these to handle a series of complex stations linked by multiple one-way lines in each direction, traversed by trains of differing types and speeds. To test the algorithms we applied them to scheduling trains for a busy system of 25 interconnected stations, with each station having up to 30 sub-platforms and several hundred train movements per day. We here report on the results from many hundreds of test runs. To make the tests more challenging, the algorithms start from initial draft timetables that we constructed so as to contain very large numbers of conflicts to be resolved. The algorithms, implemented in C code and run on a Pentium PC, found and resolved all conflicts very quickly. A further purpose of the algorithms is that they can be used to simulate and explore the effects of alternative draft timetable, operating policies, station layouts, and random delays or failures.