Hybrid quantum-classical computation for automatic guided vehicles scheduling

TitleHybrid quantum-classical computation for automatic guided vehicles scheduling
Publication TypeJournal Article
Year of PublicationSubmitted
AuthorsŚmierzchalski T, Pawela Ł, Puchała Z, Koniorczyk M, Gardas B, Deffner S, Domino K
JournalarXiv preprint

Motivated by global efforts to develop quantum computing for practical,
industrial-scale challenges, we showcase the effectiveness of state-of-the-art
hybrid quantum-classical solvers in addressing the business-centric
optimization problem of scheduling Automatic Guided Vehicles (AGVs). These
solvers leverage a noisy intermediate-scale quantum (NISQ) device, specifically
a D-Wave quantum annealer. In our study, the hybrid solvers exhibit non-zero
quantum processing times, indicating a significant contribution of the quantum
component to solution efficiency. This hybrid methodology performs comparably
to existing classical solvers, thus indicating `quantum readiness' for
scheduling tasks. Our analysis focuses on a practical, business-oriented
scenario: scheduling AGVs within a factory constrained by limited space,
simulating a realistic production setting. Our new approach concerns mapping a
realistic AGV problem onto a problem reminiscient of railway scheduling and
demonstrating that the AGV problem more suits quantum computing than the
railway counterpart and is more dense in terms of an average number of
constraints per variable. We demonstrate that a scenario involving 15 AGVs,
which holds practical significance due to common bottlenecks like shared main
lanes leading to frequent deadlocks, can be efficiently addressed by a hybrid
quantum-classical solver within seconds. Consequently, our research paves the
way for the near-future business adoption of hybrid quantum-classical solutions
for AGV scheduling, anticipating that forthcoming improvements in manufacturing
efficiency will increase both the number of AGVs deployed and the premium on
factory space.



Historia zmian

Data aktualizacji: 09/05/2024 - 07:47; autor zmian: Krzysztof Domino (kdomino@iitis.pl)