02064nas a2200229   4500000000100000000000100001008004100002260001200043100002600055700002100081700001900102700001900121700002200140700002400162700002300186700002200209700002100231245008200252856002600334490000700360520146700367       2024                            d  c09/20141 aTomasz Śmierzchalski1 aJakub Pawłowski1 aArtur Przybysz1 aŁukasz Pawela1 aZbigniew Puchała1 aMátyás Koniorczyk1 aBartłomiej Gardas1 aSebastian Deffner1 aKrzysztof Domino00aHybrid quantum-classical computation for automatic guided vehicles scheduling  uhttps://rdcu.be/dUkwi0 v143 a<p>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.</p>