Maintenance Scheduling in a Railway Corridor

Abstract

Australia has a large operational heavy railway network which is approximately 33,355 route-kilometres. This network accounted for approximately 55 percent of all freight transport activity in Australia in the financial year 2013–14, almost 367 billion tonne-kilometres which was up 50 percent from 2011–12 (BITRE (2016)). To provide a safe and reliable railway network to customers, an effective maintenance regime is a key requirement. Planned maintenance and asset renewal in capital intensive industries such as the railway industry, which has expensive infrastructure, is a common and effective maintenance practice. Infrastructure is of essential importance to maintain a reliable customer service. To prevent long unplanned interruptions in the service to customers, a proper maintenance and renewal program is required. The objective is to schedule planned maintenance and asset renewal jobs in such a way that their impact on the capacity that will be provided to customers is minimised while at the same time keeping the infrastructure in good working condition. A proper maintenance and renewal schedule limits the frequency with which disruptive emergency maintenance is needed. We investigate a planned maintenance and asset renewal scheduling problem on a railway corridor with train traffic in both directions. Potential train journeys are represented by train paths, where a train path is specified by a sequence of (location,time)-pairs, and we distinguish between up- and down paths, depending on the direction of travel. Necessary maintenance and renewal activities, or work, are specified by a release time, a deadline, a processing time and a location. Scheduling work at a particular time has the consequence that the train paths passing through the corresponding location while the work is carried out have to be cancelled. An instance of the problem is given by a set of train paths and a set of work activities, and the task is to schedule all the work such that the total number of cancelled paths is minimised. There is a vast literature on scheduling problems and on transportation network problems. However, the interaction of these problems in contexts such as the railway industry have not been studied thoroughly. Boland et al. (2014) study the problem of scheduling maintenance jobs in a network. Each maintenance job causes a loss in the capacity of network while it is being done. The objective is to minimize this loss or equivalently maximize the capacity over time horizon in such a way that all jobs are scheduled. They model the problem as a network flow problem over time. This problem and its variants are investigated in Boland et al. (2013), Boland et al. (2014), Boland et al. (2015), Boland et al. (2016) and Abed et al. (2017). Our work is different from the previous works. The main difference is that we model the capacity by train paths whereas in a network flow model over time the capacity is modelled approximately by flows over time. The primary purpose of this study is to provide further insight into this problem, to characterize the structural properties of optimal solutions, and to use these properties to develop efficient combinatorial and integer programming based solution algorithms. We present theoretical and computational results on the performance of the developed solution approaches.