Automated guided vehicles (AGVs) are portable robots that follow along marked lines or wires on the floor or use radio waves, vision cameras, magnets, or lasers for navigation to transport heavy materials or items within industrial facilities. They are commonly used in industrial settings to transport heavy materials within large buildings like factories or warehouses. The use of automatic guided vehicles expanded significantly in the late 20th century.

Scientists use quantum computing algorithms to reduce AGV scheduling computation time by 92%

They have been employed in industrial enterprises such as Amazon to move items across its huge logistics center. China’s e-commerce giant, Jingdong, has also set up an ‘Asia One’ warehouse, in which more than 100 AGVs are used for transportation operations at the same time. In ports such as the Amsterdam port, AGVs are being deployed for container transhipments.

This has shown the massive use of technology in the logistics industry and scheduling AGVs is an important component to their efficient operations. Imagine, over 1000 AGVs operating in a facility and think about the schedule that will enable all of them to work at the same time carrying out various transporting functions without colliding with one another.

The complexity in AGV scheduling

The complexity in AGV scheduling is increasing drastically as the technology is applied globally across industries. AGV scheduling problem is a difficult combinatorial optimisation problem and there have been many attempts to solve it using traditional computing. This has given some good results however, the challenge is that the computational time is extremely slow and will not be efficient for large-scale systems.

This is why some scientists led by Liang Tang have worked on this problem using quantum computing algorithms. Quantum computing by default does not rely on the sequential-bit (0s and 1s) computational process that traditional computing uses to solve computational problems rather works with entangled quantum states known as quantum bits (qubits) to solve computational problems at the same time by having superposed positions of both 0s and 1s.

In conventional research on the AGV scheduling problem, computation time significantly increases as the number of AGVs and tasks rises. To solve this, they constructed two types of quadratic unconstrained binary optimisation (QUBO) models suitable for different scheduling objectives, and the scheduling scheme is coded into the ground state of the Hamiltonian operator, and the problem is solved by using an optical coherent Ising machine (CIM).

Numerical experiments

Numerical experiments were carried out on a traditional model and QUBO model developed by the team on a traditional computer and a CIM respectively. The experimental results demonstrate that the computation speed of CIM is significantly faster than that of traditional computers, reducing the average calculation time by 92%. This proves that CIM has substantial potential for application in solving the AGV scheduling problem and similar combinatorial optimisation issues.

This research considered uniform start and end times for all AGVs and in reality, this may be different as they may all have different start and end times. This opens the research for further expansion and the use of actual quantum computers to achieve commercial utility for handling computational processes for AGV scheduling as it continues to gain adoption by e-commerce and logistics companies.