IEEE Access

Multi-FPGA Acceleration of Simulated Quantum Annealing for Route Optimization in Commercial AGV Operating Systems

Thinh NGUYEN QUANG, Kosuke Matsuyama, Keisuke Shimizu, Hiroki Sugano, Eiji Kurimoto, Jumpei Suzuki, Ziyi Chen, Hasitha Muthumala Waidyasooriya, Nishio Kosei, Masanori Hariyama, Masaru Hitomi, Kenta Sawamura, Tomohisa Okada, Masayuki Ohzeki

Published Jan 1, 2026• 0 citations

Publisher

Abstract

Improving the efficiency, safety, and speed of large-scale Automated Guided Vehicle (AGV) systems is crucial for enhancing the productivity of logistics warehouses. Recent advancements in quantum annealing devices have demonstrated the potential to optimize AGV routing effectively. However, applying quantum annealing to complex and large-scale AGV routing problems remains challenging due to insufficient consideration of operational constraints and the limited number of qubits available in current quantum annealers. To address these challenges, this study proposes a new formulation for large-scale AGV routing by introducing a priority constant to reduce delays caused by constraint violations. Additionally, we develop a system architecture that employs multiple FPGAs to accelerate Simulated Quantum Annealing (SQA), thereby overcoming the computational inefficiencies of classical SQA implementations. The proposed architecture is designed to solve large-scale optimization problems involving tens of thousands of variables. Each FPGA board can process problems with up to 50,176 variables, and a five-FPGA parallel configuration achieves significantly faster processing speeds. The performance of the proposed system is validated using a commercial AGV Operating System (AOS), including experiments with real AGVs in a small-scale environment and simulations involving up to 1,000 AGVs. Experimental results demonstrate that the proposed SQA accelerator achieves faster processing speeds and higher-quality solutions compared to existing SQA solvers, confirming its effectiveness for large-scale AGV route optimization.

DOI: 10.1109/access.2026.3717906

Related papers

Large-Scale AGV Routing Based on Multi-FPGA SQA Acceleration

Thinh NGUYEN QUANG, Kosuke Matsuyama, Keisuke Shimizu +5 more

Enhancing the efficiency, safety, and speed of large-scale Automated Guided Vehicle (AGV) systems is critical to increasing the productivity of logistics warehouses. Studies using the latest quantum annealers such as "D-Wave Advantage" with over 5000 qubits have shown the potential of quantum annealing (QA) to rapidly optimize AGV routing. However, applying QA to complex and large-scale AGV routing problems is a challenging task due to insufficient consideration of intricate operational conditions, and also due to the insufficient number of qubits in quantum annealers. This paper proposes a refined combinatorial optimization problem that minimizes the total travel time of thousands of AGVs while enhancing safety and efficiency by avoiding collisions. To solve such large-scale optimization problems with thousands of variables, we also propose a novel system architecture containing a Simulated Quantum Annealing (SQA) accelerator using multiple FPGAs. The proposed SQA accelerator is capable of processing problems with over 50,000 variables, which could be a few tens to several hundred times larger than the problems processed on the "D-Wave Advantage". It addresses multiple combinatorial optimization problems across multiple FPGAs concurrently while processing each problem in a high degree of parallelism. We demonstrate the accurate operation of the proposed SQA accelerator using a real-world large-scale AGV system with over 1000 AGVs. According to the experimental results, we observed faster processing speed and better quality results over existing SQA solvers.

Asia and South Pacific Design Automation Conference (ASP-DAC)Jan 20, 20252 citations

Quantum annealing-based route optimization for commercial AGV operating systems in large-scale logistics warehouses

Thinh Nguyen Quang, Kosuke Matsuyama, Keisuke Shimizu +10 more

This study proposes a new approach to optimizing the routing of Automated Guided Vehicles (AGVs) in large-scale logistics warehouses using Quantum Annealing. As logistics operations grow, efficient AGV routing becomes critical for ensuring safety, reliability, and throughput, particularly in high-density environments. To address the complexity of real-world systems, we introduce an enhanced cost function that incorporates a real-time priority factor to improve both routing performance and operation safety. In this paper, we present a secure and computationally efficient candidate route generation method, along with an Optimization Problem Clustering technique that decomposes the large problem into smaller, tractable subproblems to reduce computational complexity. The proposed methods are designed to incorporate real-time operational data to ensure collision avoidance, maintain safe operations, and enhance routing efficiency in realistic large-scale warehouse environments. We validate the proposed methods using a state-of-the-art Quantum Annealing machine, benchmarking against both classical and quantum-inspired solvers. Integration with a commercial AGV Operating System (AOS) is demonstrated, enabling seamless connectivity with classical solvers via a local network and with Quantum Annealing and Quantum-inspired solvers via cloud infrastructure. Simulations involving 1000 AGVs show that the proposed route generation method reduces the number of optimization variables by an average of 96% for small-scale to medium-scale systems and 78% for large-scale systems, while also improving route quality. The clustering method reduces the maximum problem size to under 10,000 variables, enabling scalable and safe control of large AGV fleets. Furthermore, a complexity-based problem formulation reduces sampling time by approximately 28.2% compared to conventional size-based approaches for problems ranging from 1000 to 10,000 variables. These results demonstrate the practical viability of Quantum Annealing for managing large-scale AGV Operating Systems and underscore the potential of the proposed methods for advancing logistics optimization in real-world warehouse environments.

Scientific ReportsDec 2, 20253 citations

Travel time optimization on multi-AGV routing by reverse annealing

Renichiro Haba, Masayuki Ohzeki, Kazuyuki Tanaka

Quantum annealing has been actively researched since D-Wave Systems produced the first commercial machine in 2011. Controlling a large fleet of automated guided vehicles is one of the real-world applications utilizing quantum annealing. In this study, we propose a formulation to control the traveling routes to minimize the travel time. We validate our formulation through simulation in a virtual plant and authenticate the effectiveness for faster distribution compared to a greedy algorithm that does not consider the overall detour distance. Furthermore, we utilize reverse annealing to maximize the advantage of the D-Wave's quantum annealer. Starting from relatively good solutions obtained by a fast greedy algorithm, reverse annealing searches for better solutions around them. Our reverse annealing method improves the performance compared to standard quantum annealing alone and performs up to 10 times faster than a commercial classical solver, Gurobi. This study extends a use of optimization with general problem solvers in the application of multi-AGV systems and reveals the potential of reverse annealing as an optimizer.

arXiv:2204.11789Scientific ReportsOct 22, 202244 citations

Highly-Parallel FPGA Accelerator for Simulated Quantum Annealing

Hasitha Muthumala Waidyasooriya, Masanori Hariyama

Quantum annealing (QA) is a method to find the global optimum of a combinatorial optimization problem by using quantum fluctuations. Quantum annealers such as D-wave are efficient to solve small problems with less than 2048 variables. Simulated quantum annealing on digital computers allows us to solve large real-world problems. However, the processing time increases exponentially with the number of variables. This article proposes a highly-parallel accelerator for simulated quantum annealing exploiting spatial and temporal parallelism. The accelerator is implemented using “open computing language (OpenCL)” on FPGA. For 8,192 spin models, we achieve 145 times speed using 32 Trotters in one FPGA and 290 times speed-up using 64 Trotters in two FPGAs, compared to single-core CPU implementation.

IEEE Transactions on Emerging Topics in ComputingDec 2, 201940 citations

A Parallel Hardware Architecture For Quantum Annealing Algorithm Acceleration

Evelina Forno, Andrea Acquaviva, Yuki Kobayashi +2 more

Quantum Annealing (QA) is an emerging technique, derived from Simulated Annealing, providing metaheuristics for multivariable optimisation problems. Studies have shown that it can be applied to solve NP-hard problems with faster convergence and better quality of result than other traditional heuristics, with potential applications in a variety of fields, from transport logistics to circuit synthesis and optimisation. In this paper, we present a hardware architecture implementing a QA-based solver for the Multidimensional Knapsack Problem, designed to improve the performance of the algorithm by exploiting parallelised computation. We synthesised the architecture using as a target an Altera FPGA board and simulated the execution for solving a set of benchmarks available in the literature. Simulation results show that the proposed implementation is about 100 times faster than a single-thread general-purpose CPU without impact on the accuracy of the solution.

IFIP/IEEE International Conference on Very Large Scale IntegrationOct 1, 20189 citations

Hybrid quantum-classical computation for automatic guided vehicles scheduling

Tomasz Śmierzchalski, Jakub Pawłowski, Artur Przybysz +6 more

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.

arXiv:2309.03088Scientific ReportsSep 18, 20249 citations