In an article recently published in the journal Scientific Reports, researchers investigated the potential of quantum computing technology for solving the automated guided vehicle (AGV) scheduling problem.
The AGV scheduling problem and a feasible solution. All AGVs start from a fixed start node, perform transportation tasks, and reach the end node after performing all tasks. ’S’ represents the starting point of a transportation task, and ’E’ represents the end point of a transportation task. Different colors represent different AGV’s mission routes. Image Credit: https://www.nature.com/articles/s41598-024-62821-6
Quantum Computing Potential
Currently, AGVs are used extensively in every aspect of production, transportation, and logistics, which significantly improved industrial intelligence and automation levels and enhanced efficiency. The amount of parallel work AGVs do is increasing to meet the requirements of application scenarios, which greatly increases the AGV scheduling challenges.
The AGV scheduling problem is a challenging combinatorial optimization problem. Although several studies have been performed on AGV scheduling problems covering multiple scenarios like terminals and workshops, finding high-quality scheduling solutions quickly/within a short timeframe remains a major challenge.
Significant progress has been achieved recently in both practical applications and theoretical understanding of quantum computing. Quantum computers' dependence on quantum mechanical principles is their fundamental difference from traditional computers.
Specifically, quantum bits are utilized as fundamental information storage units in quantum computers, which enable these computers to hold substantially more information than traditional computers. Additionally, quantum computers are advantageous for addressing problems like combinatorial optimization. Combinatorial optimization problems can be mapped to the Ising model's ground state search problem.
In this regard, the scheduling problem of AGVs could be considered as a type of routing problem.
Traditional solutions for routing problems often require significant computational resources. However, quantum computing techniques have displayed great potential in solving optimization and routing problems. Although several studies have utilized quantum computing to solve practical optimization problems, quantum computing research on AGV scheduling remains at the nascent stage, with several researchers using simulators to solve them.
The Study
In this study, researchers applied quantum computing technology to the AGV scheduling problem and proposed new quadratic unconstrained binary optimization (QUBO) models that adapt to solving the problem under two separate criteria: minimizing the overall AGV travel time and task completion time/makespan.
Specifically, two types of QUBO models suitable for various AGV scheduling objectives were constructed, and the scheduling scheme was coded into the Hamiltonian operator's ground state. The problem was solved using an optical coherent Ising machine (CIM).
The objective of the study was to effectively meet the requirements of large-scale scheduling.
In traditional AGV scheduling problem research, the computation time significantly increases with the rising number of tasks and AGVs. In practical scenarios, dispatchers set several scheduling objectives based on the nature of the work, with minimizing the total travel time and task completion time being the most common objectives. Thus, researchers constructed the QUBO models based on different objectives and presented the solutions and theoretical underpinnings for each.
The CIM and a traditional computer were used to perform the numerical experiments on the proposed QUBO model and the traditional model, respectively. Gurobi solver was utilized to solve the proposed mixed integer programming (MIP) model on a traditional computer, and its computing performance was demonstrated under various problem scales.
Additionally, an optical quantum computer was employed to solve the arc and node models' problem cases at different scales, and the computation performance was compared with the performance of traditional computers. The components of the CIM used in this study were primarily composed of electrical and optical parts.
The machine's optical part was composed of periodically poled lithium niobate crystals, fiber rings, erbium-doped fiber amplifiers, and pulsed lasers. The electrical part consisted of field-programmable gate arrays, analog-to-digital/digital-to-analog converters, and optical balanced homodyne detectors.
Significance of the Study
The comparison of the arc and node model performance on a quantum computer with the MIP model performance on traditional computers showed that the solutions obtained using CIM were all optimal. In small-scale examples, the CIM was significantly faster than the traditional computer.
Unlike traditional computers, CIM's computation time did not increase significantly with increasing problem scales. This indicates CIM's great application and development potential. Additionally, little difference was observed in the computing performance between the arc model and the node model on the quantum computer.
Specifically, the node model was slightly faster than the arc model and more universal than the node model. Overall, the experimental results showed that the optical quantum computer could save 92 % computation time on average compared to the traditional calculation method.
To summarize, the findings of this study demonstrated that CIM has significant application potential in solving the AGV scheduling problem and other similar combinatorial optimization problems. However, the benefits of quantum computing in large-scale situations/problems could not be demonstrated due to hardware constraints, which was the major limitation of this study.
Journal Reference
Tang, L., Yang, C., Wen, K., Wu, W., Guo, Y. (2024). Quantum computing for several AGV scheduling models. Scientific Reports, 14(1), 1-16. https://doi.org/10.1038/s41598-024-62821-6, https://www.nature.com/articles/s41598-024-62821-6
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.