Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines
arXiv:2010.08227
Abstract
In this work, we consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We examine the issue of train dispatching consequences caused by the arrival of an already delayed train to the segment being considered. This problem is computationally hard and often needs to be solved timely. Here, we introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, 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 those relevant to the community (linear integer programming) and a sophisticated algorithm based on tensor networks for solving QUBO problems.
arXiv comment36 pages, 17 figures, secondrevision based on reviewers' comments
References in corpus (19)
- The density-matrix renormalization group
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Adiabatic Quantum Computing
- Matrix product states represent ground states faithfully
- Dynamics of a Quantum Phase Transition and Relaxation to a Steady State
- Dynamics of quantum phase transition: exact solution in quantum Ising model
- Robustness of adiabatic quantum computation
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
- Quantum Annealing Implementation of Job-Shop Scheduling
- Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
- Scalable spin-glass optical simulator
- Pegasus: The second connectivity graph for large-scale quantum annealing hardware
- A quantum annealer with fully programmable all-to-all coupling via Floquet engineering
- Emulating the coherent Ising machine with a mean-field algorithm
- Mixing time and simulated annealing for the stochastic cellular automata
- The Chronological Operator Algebra and Formal Solutions of Differential Equations
Cited by in corpus (6)
- Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
- Error mitigation for variational quantum algorithms through mid-circuit measurements
- Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
- Quantum-inspired optimization for wavelength assignment
- Omnisolver: an extensible interface to Ising spin glass solvers
- Optimising Rolling Stock Planning including Maintenance with Constraint Programming and Quantum Annealing