Hybrid quantum-classical computation for automatic guided vehicles scheduling

Abstract

Motivated by recent efforts to develop quantum computing for practical, industrial-scale challenges, we demonstrate the effectiveness of state-of-the-art hybrid (not necessarily quantum) solvers in addressing the business-centric optimization problem of scheduling Automatic Guided Vehicles (AGVs). Some solvers can already leverage noisy intermediate-scale quantum (NISQ) devices. In our study, we utilize D-Wave hybrid solvers that implement classical heuristics with potential assistance from a quantum processing unit. This hybrid methodology performs comparably to existing classical solvers. However, due to the proprietary nature of the software, the precise contribution of quantum computation remains unclear. Our analysis focuses on a practical, business-oriented scenario: scheduling AGVs within a factory constrained by limited space, simulating a realistic production setting. Our approach maps a realistic AGVs problem onto one reminiscent of railway scheduling and demonstrates that the AGVs problem is better suited to quantum computing than its railway counterpart, the latter being denser in terms of the average number of constraints per variable. The main idea here is to highlight the potential usefulness of a hybrid approach for handling AGVs scheduling problems of practical sizes. 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.

References in corpus (9)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A practical heuristic for finding graph minors
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Travel time optimization on multi-AGV routing by reverse annealing
• Practical Integer-to-Binary Mapping for Quantum Annealers

Cited by in corpus (4)

• On the Baltimore Light RailLink into the quantum future
• Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach
• Quantum-inspired dynamical models on quantum and classical annealers
• Information Processing in Quantum Thermodynamic Systems: an Autonomous Hamiltonian Approach