Railway Dispatching Improves Via Quantum-Inspired Optimisation Techniques

Researchers at East China Jiaotong University Nanchang have developed a new model to optimise departure sequencing and section-track allocation for railways during short-term concentrated departure scenarios. Xiaobin Li and colleagues formulated a quadratic unconstrained binary optimisation (QUBO) model to represent departure-position assignment and section-track selection within a unified binary framework. Because the quality of a dispatching scheme depends on time-dependent operational interactions that cannot be fully captured by a static combinatorial model, a simulation-based evaluation layer assesses section occupation, intermediate-station waiting, and platform-capacity pressure.

Quantum algorithms optimise railway scheduling and reduce operational costs

Scientists at East China Jiaotong University achieved a 26.26% reduction in railway scheduling cost, a level previously unattainable with conventional methods. This improvement addresses the vital challenge of coordinating train departures and track allocation during peak times, a problem of significant economic and logistical importance for railway operators globally. Existing static models, often relying on heuristics or simplified assumptions, struggle with the real-time complexities of fluctuating station capacity, potential delays, and the intricate interplay between multiple trains. The inherent combinatorial nature of railway scheduling, the vast number of possible departure sequences and track assignments, makes finding optimal solutions computationally challenging. A quadratic unconstrained binary optimisation (QUBO) model, a framework for representing complex decisions as simple yes/no choices, was combined with a detailed simulation layer that mimics real-world railway operations. The QUBO formulation allows the problem to be potentially tackled by emerging quantum computing technologies, although the current implementation utilises classical solvers.

The QPSO-QAOA algorithm performed optimally under normal conditions, exceeding the performance of conventional methods. This algorithm combines Quantum-inspired Particle Swarm Optimisation (QPSO) with the Quantum Approximate Optimisation Algorithm (QAOA), leveraging concepts from quantum mechanics to explore the solution space more efficiently. Key operational factors, section occupation (the status of each track section as occupied or free), waiting times at intermediate stations (a measure of potential delays propagating through the network), platform capacity (the ability of stations to handle arriving and departing trains), and the propagation of delays (how disruptions affect subsequent train movements), were assessed. The simulation layer validating the effectiveness of each algorithm. The simulation layer is crucial as it accounts for the dynamic nature of railway operations, including stochastic events like equipment failures or passenger demand fluctuations. These encouraging figures are based on simulated scenarios, and a key step remains to validate these results with data from live railway operations before widespread implementation can be considered. Further investigation will explore the algorithm’s durability to unexpected disruptions, such as track closures due to maintenance, and its adaptability to varying network topologies, including high-speed rail lines and freight networks.

The QUBO model represents each possible departure-position assignment and section-track selection as a binary variable, either ‘1’ (selected) or ‘0’ (not selected). The quadratic nature of the model allows for the representation of interactions between these variables, capturing the constraints and dependencies inherent in railway scheduling. For example, two trains cannot occupy the same track section simultaneously, and a train must be assigned a valid route through the network. The objective function of the QUBO model is designed to minimise the overall scheduling cost, which incorporates factors like travel time, waiting time, and track usage. The simulation layer then takes the solution generated by the QUBO model and simulates the operation of the railway network over a specified time horizon, providing a realistic assessment of its performance. This iterative process allows for the refinement of the QUBO model and the identification of optimal scheduling strategies.

Cost and delay reductions from optimised short-term departure scheduling

Precise coordination is demanded by optimising railway departures, a notoriously complex undertaking to avoid bottlenecks and delays. The increasing demand for rail transport, coupled with the need for efficient resource utilisation, necessitates advanced scheduling techniques. This work offers a promising new method for tackling these challenges, particularly during peak times when trains are departing in quick succession. The authors caution that their current work focuses on “short-term concentrated departure scenarios”, raising an important question of whether this approach can scale effectively to encompass longer planning horizons and more intricate, interconnected networks. Extending the model to incorporate rolling stock scheduling, crew allocation, and energy consumption would further enhance its practical applicability.

Up to a 24% delay reduction, even within these limited scenarios, establishes a valuable foundation. A new method utilising a mathematical technique was developed to optimise train departures and track allocation during busy periods. This modelling approach creates potential railway schedules which are then rigorously tested within a detailed simulation, replicating real-world conditions and accounting for factors like station congestion and potential delays. The simulation incorporates realistic train performance characteristics, such as acceleration and deceleration rates, and accounts for the impact of signalling systems on train movements. By combining this with the simulation layer, improvements over existing methods were achieved, suggesting a pathway towards more durable and efficient railway networks. The team intends to investigate the computational demands of this approach for larger, more complex railway systems, exploring the potential for parallel processing and distributed computing to accelerate the optimisation process. The computational complexity of solving QUBO problems, even with quantum algorithms, remains a significant challenge, particularly for large-scale railway networks. Future research will also focus on developing robust algorithms that can adapt to unforeseen events and maintain optimal performance in the face of uncertainty.

The 26.26% reduction in scheduling cost represents a substantial economic benefit for railway operators, potentially leading to lower operating costs and increased profitability. Furthermore, the reduction in delays improves the reliability of rail services, enhancing passenger satisfaction and attracting more ridership. The development of more efficient railway scheduling algorithms is crucial for supporting sustainable transportation systems and reducing carbon emissions. By optimising train movements and minimising energy consumption, this research contributes to a more environmentally friendly and economically viable railway industry.

This research demonstrated that combining a mathematical model with detailed simulations improves railway scheduling. The QUBO model generated viable train schedules, and subsequent simulation revealed performance differences between algorithms under normal and disrupted conditions. Quantum-enhanced methods reduced comprehensive cost by 4.28%, 26.26% and total delay by 4.37%, 24.25% compared to conventional methods. The authors plan to explore how this approach scales to larger railway networks and to develop algorithms that can respond to unexpected events.