Rescheduling rail networks with maintenance disruptions using Problem Space Search

The creation of train timetables for long-haul single track networks is a challenging process. This task is more difficult if track maintenance disruptions are to be taken into account. This paper describes how the Problem Space Search (PSS) meta-heuristic can be used for large scale problems to create quality timetables in which both train movements and scheduled track maintenance are simultaneously considered. We show that the PSS meta-heuristic can rapidly generate a large number of alternative train timetables and then describe how the technique is generalized to construct an integrated timetable which includes track maintenance. We show how the technique can also be used as an operational tool where a revised schedule can be quickly generated to take into account the new state of a disrupted system. A case study for a single track rail network in Queensland Australia, which spans a distance of 480 km, has 57 crossing loops and typically carries over 50 trains per day is discussed. Statement of scope and purpose: This paper details a fast and efficient heuristic for the simultaneous scheduling of trains and track maintenance in a large scale rail network. We also show how the heuristic can work in a dynamic environment in which disruptions occur. Crown Copyright (c) 2010 Published by Elsevier Ltd. All rights reserved.