Quantum and classical algorithms for daily railway rolling stock circulation plans
Ewa Kędziera, Wojciech Gamon, Mátyás Koniorczyk, Zakaria Mzaouali · 2025
Read Quantum and classical algorithms for daily railway rolling stock circulation plans by Ewa Kędziera, Wojciech Gamon, Mátyás Koniorczyk, Zakaria Mzaouali (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-19340.txt.
Introduction
Ewa Kędziera, Wojciech Gamon, Mátyás Koniorczyk, and Zakaria Mzaouali plan daily train fleet rotations for Silesian Railways in Poland. Electric multiple units must cover every trip, return to depots in balance, and meet seat and bicycle capacity needs. On some routes, two identical units couple and run as a pair.
The team writes the day as a mixed-integer program over a graph of train movements, with simple crew limits included. That solver produced high-quality plans for up to four hundred four trips within about forty minutes. A quantum-ready reformulation was then tried on a D-Wave annealer and a quantum-inspired classical solver, limited to much smaller pieces.
Catalog record
| CREATOR | Ewa Kędziera, Wojciech Gamon, Mátyás Koniorczyk, Zakaria Mzaouali |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-19340
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum and classical algorithms for daily railway rolling stock circulation plans Thanks: University of Žilina, Department of Mathematical Methods and Operations Research, Faculty of Management Science and Informatics, Žilina, Slovakia Thanks: [email protected], ORCID: 0000-0001-7386-5441, Institute of Theoretical and Applied Informatics, Polish Academy of Sciences Bałtycka 5, 44-100 Gliwice Ewa Kędziera, Wojciech Gamon, Mátyás Koniorczyk, Zakaria Mzaouali Abstract We study daily rolling stock circulation planning for electric multiple units (EMUs) on a regional passenger network, focusing on services where identical EMUs may be coupled in pairs on selected routes. Motivated by the operational needs of the regional operator Silesian Railways in Poland, we formulate an acyclic mixed - integer linear program on a one - day horizon that incorporates depot balance constraints, demand - driven seat and bicycle capacity limits (which is a new aspect requested by the regional operator and local society of passengers), and simple crew availability constraints. The model is designed to support both baseline planning and disruption management under increased passenger demand. Using a graph–hypergraph representation of trips and single or coupled EMU movements, we first solve the problem with a classical ILP solver. We then derive a Quadratic Unconstrained Binary Optimization (QUBO) reformulation - which is frequently used as the input for quantum optimization - and evaluate its solution by quantum annealing on D - Wave Advantage systems and by the classical quantum - inspired VeloxQ solver. Computational experiments on real - world instances from the Silesian network, with up to 404 train trips and 11 EMU types, show that the ILP approach can obtain high - quality daily circulation plans within at most about 40 minutes, whereas current quantum and quantum - inspired solvers are restricted to substantially smaller sub - instances (up to 51 and 78 train trips, respectively) due to embedding and QUBO size limitations. These results quantify the present frontier of QUBO - based methods for rolling stock circulation and point towards hybrid decision - support architectures in which quantum or quantum - inspired optimizers address only local subproblems within a broader classical planning framework. Keyword Rolling stock circulation planning; stakeholder-driven approach; passenger and bicycle capacity; quantum annealing; VeloxQ QUBO solver 1 Introduction Optimization of processes in railway transport is essential to ensure its efficient operation. The best way to develop such models is to work closely with stakeholders. Therefore, the research problem addressed in this work is based on the specific requirements of the local community of passengers as well as the regional passenger rail operator — Silesian Railways (pl. Koleje Śląskie). Our goal is to develop a flexible model, yielding a reactive rolling stock plan on an operational time horizon, subject to crew availability constraints, that can respond efficiently to unexpected events. Our model supports different optimization objectives, aiming to balance two primary goals: maximizing the rolling stock reserve and minimizing the operational costs associated with rolling stock usage. Due to the requirements of the local society of passengers and the railway operator, we introduce the bicycle capacity constraint, as the operator serves many tourist destinations. Rolling stock circulation models are essentially modifications of set-flow models, which do not scale well to large problem instances. In direct implementations of quantum and quantum-inspired approaches, the optimization problem (a variant of the set-flow problem) is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, which also incurs significant overhead for large instances. Recall that the QUBO formulation is the most recognisable input for quantum (quantum-inspired) optimisation; however, we recognise that there are also other approaches, for example, variational quantum algorithms with qubit-efficient encodings [ 1 ] . Based on these observations, we assess the current frontier of QUBO-based quantum and quantum-inspired approaches in comparison with classical approaches. Figure ( 1 ) describes the workflow of our work. Figure 1: The workflow of the paper 1.1 Problem Description We start the problem description from the practical point of view. The railway operator’s staff, equipped with knowledge of the timetable, the available railway vehicles and their technical and operational parameters, the pool of drivers based in depots, and expected passenger demand, prepare detailed planning tables. These tables assign individual EMU (or pairs of EMUs in some predefined cases) to specific trains (operating on designated routes at specified times) while adhering to all internal and external constraints. Additionally, given the baseline plan, the operator must respond to disruptions, such as increased passenger demand, rolling stock breakdowns, and other issues, in order to minimize the propagation of disturbances throughout the network. We focus on the acyclic rolling stock planning on the operational time horizon with the drivers’ ability aspect, yielding either the original vehicle circulation plan or its version given some disturbances (i.e. increased passenger or bicycle demand). Hereby, we recognise that we do not create an entire driver roster (including driving times, breaks, and many other aspects) but only introduce some constraints to check the drivers’ ability. A crucial aspect of rolling stock circulation planning is the need for coordination with infrastructure management. The operator values having multiple solutions to the problem, each with different objective values, available within the decision support system (DSS). This allows the dispatcher to make the final decision while maintaining communication with the infrastructure manager. 1.2 Literature review The optimization of the rolling stock circulation has been extensively studied in many detailed models using both exact and heuristic methods. Due to the strong interdependence between timetable structure, fleet availability, and operational constraints, a wide spectrum of mathematical programming approaches has emerged. Rolling stock circulation is most commonly formulated as a constrained network-flow problem [ 2 ] , either in arc-based or path-based form, and often solved through advanced decomposition or column generation techniques. More recent approaches incorporate additional operational realism, including capacity constraints, stochasticity, or multi-stage decision structures, see e.g. [ 3 ] . When passenger demand is taken into account, a major challenge in rolling stock circulation planning becomes the use of flexible train compositions, which allow vehicle capacities to match peak-hour flows while respecting operational constraints. In Central European operational practice, frequent modifications of EMU compositions are less common, particularly in winter conditions. Therefore, our model allows for joining and splitting EMUs, but rather occasionally (for predefined trains), reflecting realistic operational policies. To illustrate the sizes of the problems that are accessible on the available hardware, we refer to the following literature. A classical model that is conceptually closest to our formulation is the work of Fioole et al. [ 4 ] , who proposed one of the first mixed-integer models capable of handling rolling stock circulation together with operationally realistic combining and splitting of EMUs. Their formulation explicitly models train compositions and allows changes in the number of units assigned to each trip, enabling the representation of coupling/uncoupling operations subject to station-specific constraints. A trip is defined as a sequence of train movements during which the composition cannot change, which corresponds to the structure used in our model. An important contribution of their work is the introduction of seat-shortage kilometers as a service-quality metric. It measures, for each trip, the expected number of passengers without seats multiplied by the trip distance and summed over all services. This idea is closely related to the demand-driven capacity modelling used