Railway scheduling in the presence of uncertainties

Abstract

Scheduling and rescheduling play a central role in day to day railway operations. Trains in a railway network are scheduled and controlled according to a timetable. However, the proposed timetable cannot be always followed because of unpredictable disruptions caused by many factors including excessive dwell times at stations, infrastructure and/or train faults and late arrival of crew. When trains do not operate according to the schedule, even by only a few seconds, there is an increased likelihood that they will cause conflict with other trains, resulting in further delays. This issue is even more critical in a congested network with high interconnection between trains because delays are easily propagated across the whole network, affecting all interconnected trains in the network.

The thesis focuses on railway scheduling problems (RSPs) by addressing the deterministic RSP and the stochastic RSP. Novel models and solution methods are proposed to solve these problems. We developed an optimisation model based on a set partitioning model with the main objective to minimise the total delay of trains while considering passenger safety and regulation principles including running times, headway and signalling system constraints. Moreover, we proposed heuristic and metaheuristic methods enhanced by biased randomisation and local search techniques to solve the deterministic RSP. These included Iterated Greedy with Biased Randomised (IG-BR), Biased Randomised Iterated Greedy with Local Search (BR-IG-LS) and Biased Randomised Variable Neighbourhood Search (BR-VNS).

Furthermore, we developed a stochastic optimisation model to handle delays and minimise the total delay of trains. The heuristics and metaheuristics methods which combined with Monte Carlo Simulation (MCS) to generate stochastic random delays including Sim-Iterated Greedy with Biased Randomised (S-IG-BR), Sim-Biased Randomised Iterated Greedy with Local Search (S-BR-IG-LS) and Sim-Biased Randomised Variable Neighbourhood Search (S- BR-VNS).

To the best of our knowledge, this is the first time that these proposed methods have been used to solve deterministic and stochastic RSPs.

To evaluate the performance of the proposed optimisation models and the solution methods, we conducted computational experiments using real-world case studies from the Southeastern train operating company, UK and State Railway of Thailand. Results indicated that the proposed methods outperformed the solutions adopted by the railway companies and/or existing mixed integer linear programming (MILP) obtained by CPLEX optimisation software package.

Date of Award	Sept 2019
Original language	English
Awarding Institution	University of Portsmouth
Supervisor	Banafsheh Khosravi (Supervisor) & Djamila Ouelhadj (Supervisor)