Hybrid Quantum Computing Boosts AGV Scheduling

By Dr Silpaja Chandrasekar, PhDReviewed by Susha Cheriyedath, M.Sc.Sep 25 2024

In a recent article published in the journal Scientific Reports, researchers demonstrated the effectiveness of hybrid solvers, including D-Wave's quantum technology, in optimizing the scheduling of automated guided vehicles (AGVs). The study revealed that by integrating classical heuristics with quantum processing, the hybrid approach efficiently managed the scheduling of up to 21 AGVs in practical factory settings.

The study highlighted that AGV scheduling is better suited to quantum computing than railway scheduling, primarily due to fewer constraints per variable. However, the precise role of quantum computation remains unclear, as the proprietary nature of the software limits full transparency.

Background

Previous research has demonstrated that quantum computing can improve the efficiency of solving certain optimization problems, particularly in industrial settings like AGV scheduling. Hybrid quantum-classical solvers, such as D-Wave’s, have shown potential advantages over classical solvers when addressing the challenges of AGV scheduling in space-constrained factory environments.

However, converting linear problems into the quadratic unconstrained binary optimization (QUBO) format, coupled with noise in quantum devices, presents significant hurdles. Larger AGV systems also require advanced heuristics to efficiently manage deadlocks and timing issues.

Quantum Annealing for Optimization

Quantum annealing is a heuristic algorithm based on adiabatic quantum computing, designed to solve optimization problems by encoding them into a physical system governed by a problem Hamiltonian. D-Wave's quantum annealers use a 2-local Ising model to represent the system's energy, gradually transitioning from an initial Hamiltonian to a target one to identify the ground-state solution.

Many optimization tasks, including scheduling, can be modeled as integer linear programs (ILPs) and converted into QUBO problems. This enables hybrid classical-quantum solvers, such as binary quadratic models (BQM) and constrained quantum models (CQM), to handle larger-scale challenges more effectively. Although proprietary, D-Wave’s solvers integrate classical heuristics with quantum processing to enhance solution quality for complex optimization problems.

AGV Scheduling in Industry 4.0

In the context of Industry 4.0, AGV scheduling must be tailored to the unique characteristics of each factory. This research addresses a specific challenge in a confidential production environment where AGVs navigate defined pathways. These pathways, which can be either unidirectional or bidirectional, provide access to critical areas such as ports, loading stations, and charging points.

A centralized control system oversees the AGVs and manages their scheduling. A significant challenge in these environments is the risk of deadlocks, where multiple AGVs converge and block each other’s paths.

This scheduling problem is analogous to job-shop scheduling theory, where zones function as machines and AGVs as jobs that must be processed in a predefined sequence. Each AGV must visit a series of infrastructure elements in a specific order. Areas between zones, where conflicts are less likely, serve as buffers.

The inclusion of minimal headway requirements between AGVs, along with deadlock constraints on bidirectional lanes, introduces blocking constraints into the model. The goal is to minimize travel completion time while prioritizing certain AGVs, aligning the problem with the principles of scheduling theory.

The algorithm for AGV scheduling processes fixed inputs, such as the set of AGVs, priority weights, network topology, and minimal headways. Variable inputs include AGV starting points, destinations, and nominal speeds.

The scheduling process involves defining conflict zones, determining AGV entry and exit times, and encoding the problem into an integer linear programming (ILP) model. The output is a conflict-free timetable detailing each AGV’s entry and exit times at various zones. The complexity of formulating the problem as an ILP model makes it a strong candidate for quantum computing solutions.

AGV Scheduling Optimization

For the numerical calculations, problem examples such as those presented were used, 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 derived from the network topology, AGVs’ speeds, and zone locations.

From an optimization perspective, the focus was on evaluating how computational time, the number of variables, and constraints scaled with problem size, with instances ranging from two AGVs and four zones to twenty-one AGVs and seven zones.

The AGV scheduling problem, with roughly two constraints per variable, is less dense than the related railway scheduling 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 CPLEX optimizer in computational time for larger problems, demonstrating its suitability for real-life factory applications. However, as problem size increases, additional heuristics may be needed due to reduced feasibility.

Conclusion

This study demonstrated the potential of hybrid quantum-classical approaches for AGV scheduling in industrial environments. Although quantum advantage was not fully achieved, the CQM solver delivered results comparable to the CPLEX benchmark.

As quantum technologies continue to advance, these hybrid methods could tackle larger problems beyond the capabilities of classical solvers. Open-source tools, such as the simulated bifurcation machine (SBM) solver, also show promise, but further development is required to enhance 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.