In a recent article published in the journal Scientific Reports, researchers demonstrated the effectiveness of hybrid solvers, including D-Wave's, for optimizing automatic guided vehicles (AGVs) scheduling. They showed that by combining classical heuristics with potential quantum processing, a hybrid approach could efficiently handle up to 21 AGVs in practical factory settings.
Study: Hybrid quantum-classical computation for automatic guided vehicle scheduling. Image Credit: Panchenko Vladimir/Shutterstock.com
The study highlighted that AGV scheduling is better suited to quantum computing than railway scheduling due to fewer constraints per variable. However, the precise role of quantum computation remained unclear due to the software's proprietary nature.
Background
Past work has shown that quantum computing can enhance the efficiency of solving certain optimization problems, particularly in industrial settings like AGV scheduling. Hybrid quantum-classical solvers, such as D-Wave’s, have been used to address AGV scheduling challenges in factories with limited space, showing potential over classical solvers.
The complexity of transforming linear problems into quadratic unconstrained binary optimization (QUBO) format and noise in quantum devices remain challenges. Larger AGV systems require advanced heuristics to handle deadlocks and timing issues efficiently.
Quantum Annealing for Optimization
Quantum annealing is a heuristic algorithm rooted in adiabatic quantum computing. It is designed to solve optimization problems by encoding them into a physical system with a problem Hamiltonian. D-Wave's quantum annealers utilize a 2-local ising model to represent the system's energy, transitioning from an initial Hamiltonian to the target one to find the ground-state solution.
Many optimization tasks, including scheduling, can be modeled as integer linear programs (ILPs) and transformed into QUBO problems. This allows hybrid classical-quantum solvers like binary quadratic model (BQM) and constrained QM(CQM) to tackle larger-scale challenges effectively. Despite being proprietary, D-Wave's solvers employ classical heuristics alongside quantum processing to enhance solution quality for complex problems.
AGV Scheduling in Industry 4.0
The concept of Industry 4.0 necessitates that the scheduling of AGVs aligns closely with the specific characteristics of individual factories. This research addresses a problem prevalent in a confidential production environment where AGVs operate on defined pathways. These pathways can be unidirectional or bidirectional, providing access to ports, loading stations, and charging points.
A centralized control system coordinates the AGVs and manages their scheduling. A significant challenge in such environments is the potential for deadlocks, where multiple AGVs converge at a point and immobilize each other.
The scheduling problem can be likened to job-shop scheduling theory, where zones function as machines and AGVs act as jobs that must be processed in a defined sequence. Each AGV must visit a series of infrastructure elements in a specified order. Areas between zones, where conflicts are unlikely, are treated as buffers.
The requirements for minimal headways between AGVs and deadlock constraints on bidirectional lanes introduce blocking constraints into the model. The ultimate objective is to minimize travel completion time while accommodating AGV priorities, effectively framing the problem within the scheduling theory framework.
The algorithm for AGV scheduling processes fixed inputs, including the set of AGVs, priority weights, network topology, and minimal headways. It also incorporates variable inputs such as AGV starting points, destinations, and nominal speeds.
The processing steps involve defining conflict zones, determining entry and exit times for AGVs, and encoding the problem into an ILP model. The output is a conflict-free timetable detailing AGVs’ entry and exit times at various zones. The formulation of the problem as an ILP model underscores its complexity, positioning it as a strong candidate for quantum computing solutions.
AGV Scheduling Optimization
For the numerical calculations, problem examples like those presented were utilized, varying the number of AGVs and zones, which is typical in industrial systems where AGVs operate dynamically. An illustrative case featuring seven zones was analyzed, with parameter values obtainable from the network topology, AGVs’ speeds, and zone locations.
From an optimization perspective, the aim was to evaluate how computational time, the number of variables, and constraints scaled with the problem size, focusing on instances ranging from two AGVs and four zones to twenty-one AGVs and seven zones.
The AGVs problem, with about two constraints per variable, is less dense than a related railway problem, making it more suited to quantum computing. However, a branched topology with loops could increase complexity, potentially limiting the problem's compatibility with quantum approaches.
The CQM hybrid solver consistently provided feasible solutions and outperformed the exact cplex optimizer (CPLEX) solver in computational time for larger problems, making it suitable for real-life factory applications. However, as problem size increases, additional heuristics may be needed due to decreased feasibility.
Conclusion
To sum up, this study demonstrated the potential of hybrid quantum-classical approaches for AGV scheduling in industrial environments. Although quantum advantage was not achieved, the CQM solver produced results close to the CPLEX benchmark.
As quantum technologies advance, these hybrid methods could handle larger problems beyond classical capabilities. Additionally, open-source tools like the simulated bifurcation machine (SBM) solver showed promise, but further development is needed to improve hybrid solvers for real-world applications.
Journal Reference
Śmierzchalski, T., et al. (2024). Hybrid quantum-classical computation for automatic guided vehicle scheduling. Scientific Reports, 14:1, 1-15. DOI:10.1038/s41598-024-72101-y, https://www.nature.com/articles/s41598-024-72101-y
Disclaimer: The views expressed here are those of the author expressed in their private capacity and do not necessarily represent the views of AZoM.com Limited T/A AZoNetwork the owner and operator of this website. This disclaimer forms part of the Terms and conditions of use of this website.