Posted in | News | Quantum Computing

Quantum Computing Revolutionizes AGV Scheduling

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.

Quantum Computing Revolutionizes AGV Scheduling
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.

Samudrapom Dam

Written by

Samudrapom Dam

Samudrapom Dam is a freelance scientific and business writer based in Kolkata, India. He has been writing articles related to business and scientific topics for more than one and a half years. He has extensive experience in writing about advanced technologies, information technology, machinery, metals and metal products, clean technologies, finance and banking, automotive, household products, and the aerospace industry. He is passionate about the latest developments in advanced technologies, the ways these developments can be implemented in a real-world situation, and how these developments can positively impact common people.

Citations

Please use one of the following formats to cite this article in your essay, paper or report:

  • APA

    Dam, Samudrapom. (2024, June 04). Quantum Computing Revolutionizes AGV Scheduling. AZoQuantum. Retrieved on June 13, 2024 from https://www.azoquantum.com/News.aspx?newsID=10294.

  • MLA

    Dam, Samudrapom. "Quantum Computing Revolutionizes AGV Scheduling". AZoQuantum. 13 June 2024. <https://www.azoquantum.com/News.aspx?newsID=10294>.

  • Chicago

    Dam, Samudrapom. "Quantum Computing Revolutionizes AGV Scheduling". AZoQuantum. https://www.azoquantum.com/News.aspx?newsID=10294. (accessed June 13, 2024).

  • Harvard

    Dam, Samudrapom. 2024. Quantum Computing Revolutionizes AGV Scheduling. AZoQuantum, viewed 13 June 2024, https://www.azoquantum.com/News.aspx?newsID=10294.

Tell Us What You Think

Do you have a review, update or anything you would like to add to this news story?

Leave your feedback
Your comment type
Submit

While we only use edited and approved content for Azthena answers, it may on occasions provide incorrect responses. Please confirm any data provided with the related suppliers or authors. We do not provide medical advice, if you search for medical information you must always consult a medical professional before acting on any information provided.

Your questions, but not your email details will be shared with OpenAI and retained for 30 days in accordance with their privacy principles.

Please do not ask questions that use sensitive or confidential information.

Read the full Terms & Conditions.