Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines

• URL: http://arxiv.org/abs/2010.08227v3
• Date: Tue, 30 Mar 2021 13:01:37 GMT
• Title: Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines
• Authors: Krzysztof Domino, M\'aty\'as Koniorczyk, Krzysztof Krawiec, Konrad Ja{\l}owiecki, Bart{\l}omiej Gardas
• Abstract summary: We consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, compatible with the emerging quantum annealing technology. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers.
• Score: 0.4724825031148411
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• A Greedy Quantum Route-Generation Algorithm [0.0]
  We propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer. By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution.
  arXiv  Detail & Related papers  (2024-05-05T21:20:46Z)
• Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach [0.157286095422595]
  We build an integer linear model for the given problem and solve it with D-Wave's quantum-classical hybrid solver. The proposed approach is demonstrated on a real-life heterogeneous urban network in Poland.
  arXiv  Detail & Related papers  (2023-09-13T07:19:32Z)
• Hybrid quantum-classical computation for automatic guided vehicles scheduling [0.0]
  We demonstrate the effectiveness of state-of-the-art hybrid (not necessarily quantum) solvers in addressing the business-centric problem of scheduling Automatic Guided Vehicles. We utilize D-Wave hybrid solvers that implement classicals with potential assistance from a quantum processing unit. We show that a scenario involving up to 21 AGVs, significant due to possible deadlocks, can be efficiently addressed by a hybrid solver in seconds.
  arXiv  Detail & Related papers  (2023-09-01T09:11:53Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  We propose to expand the solution interval gradually to make the PINN converge to the correct solution. All ensemble members converge to the same solution in the vicinity of observed data. We show experimentally that the proposed method can improve the accuracy of the found solution.
  arXiv  Detail & Related papers  (2022-04-11T14:05:34Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Quantum annealing in the NISQ era: railway conflict management [0.44040106718326594]
  We consider a practical railway dispatching problem: delay and conflict management on single-track railway lines. We introduce a quadratic unconstrained binary optimization (QUBO) model of this problem, compatible with the emerging quantum annealing technology. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers.
  arXiv  Detail & Related papers  (2021-12-07T13:17:21Z)
• Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing [0.5161531917413706]
  This paper introduces QUBO and HOBO representations for rescheduling problems of railway traffic management. We consider the conditions of minimal headway between trains, minimal stay on stations, track occupation, and rolling stock circulation.
  arXiv  Detail & Related papers  (2021-07-07T14:07:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.