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 the local passenger community), and simple crew availability constraints. 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 input for quantum optimization, and evaluate its solutions using quantum annealing on D-Wave Advantage systems and 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. In contrast, current quantum and quantum-inspired solvers are restricted to substantially smaller subinstances (up to 51 and 78 train trips, respectively) due to the large number of terms in the QUBO and, in the case of quantum hardware, embedding limitations. These results quantify the current frontier of QUBO-based methods for rolling stock circulation and point toward hybrid decision-support architectures in which quantum or quantum-inspired optimizers address only local subproblems within a broader classical planning framework.
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 the local passenger community), and simple crew availability constraints. 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 input for quantum optimization, and evaluate its solutions using quantum annealing on D-Wave Advantage systems and 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. In contrast, current quantum and quantum-inspired solvers are restricted to substantially smaller subinstances (up to 51 and 78 train trips, respectively) due to the large number of terms in the QUBO and, in the case of quantum hardware, embedding limitations. These results quantify the current frontier of QUBO-based methods for rolling stock circulation and point toward hybrid decision-support architectures in which quantum or quantum-inspired optimizers address only local subproblems within a broader classical planning framework.
Abstract As consequences of disruptions in railway traffic affect passenger experience and satisfaction, appropriate rerouting and/or rescheduling is necessary. These problems are known to be NP-hard, given the numerous restrictions of traffic nature. With the recent advances in quantum technologies, quantum annealing has become an alternative method to solve such optimization problems. To use quantum annealing, the problem needs to be encoded in quadratic unconstrained binary optimization (QUBO) or higher-order binary optimization (HOBO) formulation that can be recast as a QUBO. This paper introduces QUBO and HOBO representations for rescheduling problems of railway traffic management; the latter is a new approach up to our knowledge. This new approach takes into account not only the single-track lines but also the double- and multi-track lines, as well as stations composed of tracks and switches. We consider the conditions of minimal headway between trains, minimal stay on stations, track occupation, and rolling stock circulation. Furthermore, a hybrid quantum-classical procedure is presented that includes rerouting. We demonstrate the proof of concept implementation on the D-Wave Quantum Processing Unit and D-Wave hybrid solver.
Rolling stock planning is a complex optimization problem in railway management that involves assigning physical trains to scheduled trips while minimizing operational costs. In this work, we address a specific instance of this problem featuring 190 trips over two days, subject to constraints such as mandatory maintenance stops. We reformulate the problem as a Maximum-Weight Independent Set (MWIS) problem on a graph where nodes represent feasible train cycles. To handle the computational complexity of the large search space, we propose a hybrid divide-and-conquer algorithm. This approach iteratively selects subgraphs and solves the MWIS problem using various solvers, including exact classical methods and the Quantum Approximate Optimization Algorithm (QAOA). We evaluate the algorithm's performance by comparing these methods and analyzing the scaling with respect to subgraph size, with QAOA assessed through both classical simulation and execution on a quantum device (IQM Emerald). Our results indicate that increasing the subgraph size generally improves solution quality, demonstrating that the hybrid framework can effectively bridge the gap between polynomial-time approximate solvers and exponential-time exact methods.
We are in the noisy intermediate-scale quantum (NISQ) devices' era, in which quantum hardware has become available for application in real-world problems. However, demonstrations of the usefulness of such NISQ devices are still rare. In this work, we consider a practical railway dispatching problem: delay and conflict management on single-track railway lines. We examine the train dispatching consequences of the arrival of an already delayed train to a given network segment. This problem is computationally hard and needs to be solved almost in real time. We introduce a quadratic unconstrained binary optimization (QUBO) model of this problem, which is compatible with the emerging quantum annealing technology. The model's instances can be executed on present-day quantum annealers. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers. As a reference, we also provide solutions calculated with classical methods, including the conventional solution of a linear integer version of the model as well as the solution of the QUBO model using a tensor network-based algorithm. Our preliminary results illustrate the degree of difficulty of real-life railway instances for the current quantum annealing technology. Moreover, our analysis shows that the new generation of quantum annealers (the advantage system) does not perform well on those instances, either.
The consequences of disruptions in railway traffic are the primary cause of passengers' dissatisfaction. Hence, appropriate dispatching decisions are necessary (e.g., by assigning the order of trains), given the numerous restrictions of traffic nature. The latter is perceived as an NP-hard problem. This paper outlines QUBO (quadratic unconstrained binary optimization) and HOBO (higher-order binary optimization) representations for dispatching problems of railway traffic management. Specifically, we consider minimal span between trains, minimal stay on stations, station/track occupation, and rolling stock circulation. The main result is the hybrid algorithm to deal with disturbances in rail traffic on single-, double- and multi-track lines; the demonstrative model illustrates the issue briefly. This algorithm can solve railway dispatching problems using the quantum annealer or any other QUBO-based optimization device.
2020 year has been a turning point for the entire humanity. The COVID-19 pandemic has not only revolutionized our way of thinking, but it has changed the way we live, leading to having limitations on any aspect of our daily life, from the smallest things to the biggest. This extraordinary situation has afflicted the railway world, too, since the movements have been limited drastically and new rules have been introduced. This thesis focuses on analyzing passenger transport's current situation on high-speed trains in this particular historical period we are experiencing, the COVID-19 Era. It aims to create hypothetical scenarios of passengers' distribution inside a train wagon with current health and hygiene rules. The main goal of what has been defined as the Seating Arrangement Optimization problem is to fill the train wagon as much as possible and therefore transport the largest number of people by maximizing the number of passengers belonging to the same family sitting in nearest seats. In this work, two different optimization models for formalizing the identified problem are presented and compared: a Mixed-Integer Linear Programming (MILP) model, one of the most common formulations in literature in the optimization field, and a Quadratic Unconstrained Binary Optimization (QUBO) model, a novel type of problem that can be solved on a quantum computer. In particular, for the resolution of the first type of model, the Gurobi commercial solver is used while, for the latter one, the QBSolv and a classical-quantum hybrid solver provided by D-Wave Systems Inc., a leader company in the quantum computing field, are considered. Quantum computing is an innovative research field currently still under development, on which time and money have begun to be invested only in recent years. What makes this research field attractive is the particular way with which quantum technology operates and the great potential it can offer to solve real-world problems. Due to the current physical capabilities, quantum computers' computational resources are not sufficient to execute too large optimization problems. Still, even with small instances like the ones considered in this work, it can be seen how much they can find highly optimized solutions in a short time.
Uncertainty is fundamental in modern power systems, where renewable generation and fluctuating demand make stochastic optimization indispensable. The chance constrained unit commitment problem (UCP) captures this uncertainty but rapidly becomes computationally challenging as the number of scenarios grows. Quantum computing has been proposed as a potential route to overcome such scaling barriers. In this work, we evaluate the applicability of quantum annealing platforms to the chance constrained UCP. Focusing on a scenario approximation, we reformulated the problem as a mixed integer linear program and solved it using DWave hybrid quantum classical solver alongside Gurobi. The hybrid solver proved competitive under strict runtime limits for large scenario sets (15,000 in our experiments), while Gurobi remained superior on smaller cases. QUBO reformulations were also tested, but current annealers cannot accommodate stochastic UCPs due to hardware limits, and deterministic cases suffered from embedding overhead. Our study delineates where chance constrained UCPs can already be addressed with hybrid quantum classical methods, and where current quantum annealers remain fundamentally limited.