Tactical and Real-Time Integrated Railway Scheduling and Routing with a Variable Neighbourhood Search Algorithm

Railway scheduling and routing problems are significant for railway operating companies who face increasing demand and high expense of construction or modification of infrastructure. In operational level, dispatchers need to respond to disruptions in daily railway operations. In this study, we address integrated railway scheduling and routing problem which can be implemented in tactical and operational level planning. Integrated railway scheduling and routing problem is formulated as a Modified Parallel Machine Job Shop Scheduling (MPM-JSS) model to minimise delay propagation due to the interconnectivity of trains in the railway network. A Variable Neighbourhood Search (VNS) algorithm is developed to solve the mentioned problem by using four neighbourhood structures. We conduct computational experiments to evaluate the performance of the suggested optimisation model and VNS algorithm. The computational experiments investigate different disruption scenarios including blocked tracks on a single-track section, blocked tracks on multiple-track section, and longer running/dwell time in a real-world case study of London Bridge area in the UK railway network. The results show the effectiveness of VNS algorithm in terms of solution quality compared to the optimisation model implemented using CPLEX.