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.
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.
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.
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.
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.
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.
With the rapid advancement of smart agriculture, Unmanned Aerial Vehicles (UAVs) have become indispensable for efficient coverage and path planning in grid-mapped agricultural fields. However, optimizing UAV flight paths in large-scale environments remains a complex Nondeterministic Polynomial-time (NP)-hard problem. Traditional path planning methods are often constrained by local optima, limited scalability, and slow convergence, which significantly restrict their effectiveness in solving large-scale problems. To address these limitations, this paper proposes a novel optimization framework utilizing a Graphics Processing Unit (GPU)-parallelized Ising solver. Our method mimics the operational principles of quantum annealing on GPU hardware, enabling rapid search for the minimum-energy state of Ising models. Unlike physical quantum devices, which are often constrained by the number of qubits, our approach leverages the Fixstars Amplify (FA) platform to perform parallel annealing on highly parallelized GPUs. This enables the simultaneous evaluation of thousands of potential path candidates and vast state transitions. By leveraging large-scale parallel processing, this framework's core strength lies in minimizing computation time even as the problem scale increases. Simulation results demonstrate that our proposed method consistently identifies superior flight paths while maintaining stable computational performance compared with the genetic algorithm and simulated annealing method.
In the current competitive industrial environment, the study of NP-hard issues is becoming more and more significant. In logistics, the Vehicle Routing Problem (VRP) is one of the popular challenges, especially in cold chain logistics, which requires the management of perishable goods. This problem involves identifying the optimal paths for vehicles responsible for transporting goods to different locations. Due to its combinatorial nature and the complexity of finding optimal solutions, it is identified as an NP-hard problem that requires an unreasonable time frame to solve. Recently, quantum computing has proven to be a promising approach for addressing some of the complex challenges. Among quantum methodologies, quantum annealing (QA) has demonstrated the potential to accelerate computation times in solving optimization problems. By leveraging the principles of quantum tunneling and superposition, QA can explore solution spaces more efficiently. Therefore, this study explores the application of QA to address VRP in cold chain logistics, aiming to develop solutions that minimize travel distances during deliveries. The case study demonstrates that QA can achieve, on average, at least 85% of optimal performance while providing approximately 95% faster run times compared to classical genetic algorithms (GA). This contributes to greater efficiency in cold chain logistics operations.