Biased randomised iterated greedy with local 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 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 Biased Randomised Iterated Greedy with Local Search (BRIGLS) to solve the railway re-scheduling problem in the presence of delays caused by travelling/dwell time delay and late departure time. BRIGLS algorithm employs two phases in the search process for each iteration, namely destruction and construction. The destruction phase eliminates randomly some trains from the current solution, thus obtaining a partial solution. The construction phase inserts some trains into the partial solution until a complete one is obtained. The biased randomised concept is applied in the construction phase to select a train which is not sequenced before to be inserted it the partial solution. The local search is employed to intensify the search for better solutions around the complete solution generated by the construction procedure. 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 show that the BRIGLS algorithm has outperformed the solution used by the railway network in Thailand and it can improve the efficiency of Thailand railway management by decreasing the total train delays.