Modified Shifting Bottleneck Algorithms for Train Scheduling and Rescheduling in the UK

Performance of the railway system is important for both passengers and freight transport. It is very costly to modify or construct the infrastructure to accommodate more services. How to respond the ever-increasing demand for rail transportation is one of the main concerns of the train companies. Train scheduling defines the order and time of the trains efficiently so that the best usage of the current infrastructure is made. However, we need to monitor and control the plan in operational level and respond to disruption in real-time using train rescheduling. Job shop scheduling problem has attracted attention in the literature for modelling train scheduling problem. Similarly, we use a job shop scheduling approach in this study and we try to develop a generic model that can be also customized to special characteristics of the UK railway network.

An important feature of the schedule is to be conflict-free which means same trains are not allocated to the same track section at the same time. The schedule determines a plan including train orders and starting times on track sections for predetermined routes. In this microscopic study, we look at the detailed track topology of the network and the train movements on the track sections divided by signals called block. A block can be occupied by only one train at a time according to the line blocking principle which is similar to the job shop scheduling problem where only one job can be processed on a machine at a time. There are still certain gaps between the reality and the simplified research models though this similarity has been recognized in the literature for some time. The proposed model based on a modified disjunctive graph is flexible to present a broader range of operational and safety constraints for train scheduling. Moreover, the accuracy of the microscopic model is very helpful for reliable online decision making. If the solution method is fast enough, the same approach can be employed to handle disruptions for real-time traffic management by considering more restrictions for the current running trains.

This study suggests a Mixed Integer Linear Programming (MILP) model to minimize the delay propagation in the network subject to several operational and safety constraints including running time constraints, dwell time constraints, headway constraints and signalling constraints. Considering that the train scheduling problem is a very large and complex combinatorial problem which is known to be NP-complete, it is more appropriate to use heuristic methods to solve this problem. One of the inspiring solution methods for the job shop scheduling problem is Shifting Bottleneck (SB) procedure which provides the general framework of our solution approaches. SB is modified to be adapted to the train scheduling constraints and it differs from the conventional approach in finding the bottleneck and solving the single machine problems. SB is a decomposition approach which solves single machine scheduling problems. Obviously, the quality of the solution of the single machine problems can affect the total solution quality. Thus, different SB algorithms are developed to make use of the problem characteristics in order to solve the problem more efficiently.

The suggested SB algorithms are coded using MS Visual C++ 2010. A case study of a dense and complicated network in the UK is considered which has a mixed traffic of passengers and freight. This area is based on London and South East with various junctions and stations and it has usually reported performance and capacity issues. We offer computational experiments for comparing the employed methods and the FCFS dispatching rule in terms of solution quality and computation time.