Quantum Algorithms and Classical Methods Optimise Daily Railway Rolling Stock Circulation

Planning the daily circulation of railway rolling stock presents a significant logistical challenge, and researchers are now exploring the potential of quantum computing to improve these complex operations. Ewa Kędziera, Wojciech Gamon, and Mátyás Koniorczyk, alongside Zakaria Mzaouali, Andrea Galadíková, and Krzysztof Domino, investigate methods for optimising train schedules on a regional passenger network, incorporating practical demands such as passenger capacity and bicycle storage. Their work, motivated by the needs of Silesian Railways in Poland, formulates a new mathematical model and compares the performance of traditional computational approaches with those leveraging quantum algorithms on D-Wave systems and a classical-inspired solver. The results demonstrate that while conventional methods currently outperform quantum approaches for large-scale problems, this research identifies a pathway towards hybrid systems where quantum optimisation can address specific subproblems within a broader classical planning framework, ultimately enhancing the efficiency and responsiveness of railway networks.

The work addresses the complex task of optimising the allocation and movement of railway cars to minimise costs. Researchers investigated both quantum annealing, utilising D-Wave quantum annealers to directly solve the problem formulated as a Quadratic Unconstrained Binary Optimisation (QUBO) model, and quantum-inspired algorithms, employing classical algorithms inspired by quantum principles. The team rigorously compared the performance of these approaches against traditional optimisation solvers like SCIP on realistic railway network instances. The study highlights the potential of hybrid quantum-classical approaches and details the process of formulating the rolling stock rescheduling problem as a QUBO model. Recent advancements in quantum hardware, such as the D-Wave Advantage2 system, and software tools were also showcased.

Railway Circulation Planning with Integrated Capacity Limits

The study addresses daily rolling stock circulation planning for electric multiple units, focusing on the regional passenger network of Silesian Railways in Poland. Researchers developed an acyclic mixed-integer linear program designed for a one-day horizon, incorporating depot balance constraints and demand-driven capacity limits, including bicycle capacity, a novel addition requested by the operator and passengers. To represent the complex network, the team engineered a graph-hypergraph representation, enabling a detailed formulation of the optimisation problem. Initial solutions were obtained using a classical integer linear program implemented with the SCIP solver, providing a benchmark for performance. Subsequently, a Quadratic Unconstrained Binary Optimisation (QUBO) reformulation was evaluated using both D-Wave Advantage systems and the classical-inspired VeloxQ solver. Computational experiments using real-world data, encompassing up to 404 train trips and 11 EMU types, demonstrate that the classical ILP approach can obtain high-quality circulation plans within approximately 40 minutes, while quantum and quantum-inspired solvers were limited to substantially smaller instances due to embedding and QUBO size limitations.

Silesian EMU Circulation Planning with Integer Programming

Scientists achieved a breakthrough in daily rolling stock circulation planning for electric multiple units on regional passenger networks, developing a model tailored to the operational needs of Silesian Railways in Poland. The work addresses the complex task of scheduling trains, incorporating constraints such as the coupling of identical EMUs and demand-driven capacity for seats and bicycles. Researchers formulated an acyclic mixed-integer linear program designed for both baseline planning and responding to disruptions with increased passenger demand. Experiments using real-world data, encompassing up to 404 train trips and 11 EMU types, demonstrate the effectiveness of the classical ILP approach, successfully generating high-quality daily circulation plans within a maximum of 40 minutes.

However, current and quantum-inspired solvers faced limitations, successfully addressing substantially smaller sub-instances due to constraints related to embedding and QUBO size. Further investigation involved testing quantum annealing on D-Wave systems and the quantum-inspired VeloxQ solver. While the D-Wave Advantage2 system demonstrated improvements, it currently remains limited to smaller problems. Limiting the maximum transfer window significantly reduced solution time with only a minor impact on objective value, supporting a two-mode workflow for fast solves and optional refinement.

Silesian Railway Circulation Planning Optimised Successfully

This research presents a new approach to daily rolling stock circulation planning for electric multiple units, addressing a practical need identified in collaboration with Silesian Railways in Poland. Scientists developed a mixed-integer linear program, incorporating both depot balance and demand-driven capacity constraints, including bicycle capacity, to optimise train schedules. The model accounts for the possibility of coupling identical train units on specific routes, enhancing operational flexibility. Computational experiments using real-world data, involving up to 404 train trips and 11 train types, demonstrate that the model can generate high-quality daily circulation plans within a reasonable timeframe using conventional optimisation techniques.

The team also investigated the potential of quantum computing and quantum-inspired algorithms, formulating a Quadratic Unconstrained Binary Optimisation equivalent of the model. While these approaches showed promise, the study reveals current limitations in scaling these methods to instances comparable in size to those solved by the classical integer linear program. This work quantifies the current capabilities of quantum-based methods for rolling stock circulation and suggests that hybrid architectures, combining classical and quantum-inspired optimisation, may offer the most effective path forward.