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

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.