Sim-biased randomised variable neighbourhood search for railway scheduling in the presence of uncertainties

Railway scheduling and rescheduling play a central role in day-to-day railway operations. Trains on a railway network are scheduled and controlled according to a timetable. However, trains are not always run based on the proposed timetable because there might be some unpredictable disruptions due to excessive dwell times at stations, infrastructure and/or train faults, and the late arrival of crew. In this research study, we aim to minimise the total delay of trains while considering passenger safety and regulation principles including running times, headway and signalling system constraints. The problem is formulated as a Modified Blocking Job Shop Scheduling (MBJSS) model, which is adapted from the classical job shop scheduling model. We propose the Sim-Biased Randomised Variable Neighbourhood Search (SBRVNS) to solve the railway re-scheduling problem in the presence of delays caused by travelling/dwell time delay and late departure time. The SBRVNS algorithm starts with Monte Carlo Simulation (MCS) to generate stochastic random delays, then uses a biased randomised heuristic to generate an initial solution and VNS to improve the initial solution. To evaluate the performance of the proposed optimisation model and the solution method, we have conducted computational experiments using a real-world case study from the railway network in Thailand. The results have shown that the SBRVNS algorithm has promising results in decreasing the total train delays.