Travel time optimization on multi-AGV routing by reverse annealing

Abstract

Quantum annealing has been actively researched since D-Wave Systems produced the first commercial machine in 2011. Controlling a large fleet of automated guided vehicles is one of the real-world applications utilizing quantum annealing. In this study, we propose a formulation to control the traveling routes to minimize the travel time. We validate our formulation through simulation in a virtual plant and authenticate the effectiveness for faster distribution compared to a greedy algorithm that does not consider the overall detour distance. Furthermore, we utilize reverse annealing to maximize the advantage of the D-Wave's quantum annealer. Starting from relatively good solutions obtained by a fast greedy algorithm, reverse annealing searches for better solutions around them. Our reverse annealing method improves the performance compared to standard quantum annealing alone and performs up to 10 times faster than the strong classical solver, Gurobi. This study extends a use of optimization with general problem solvers in the application of multi-AGV systems and reveals the potential of reverse annealing as an optimizer.

11 pages, 5 figures, 1 table

References in corpus (7)

• Mathematical Foundation of Quantum Annealing
• Quantum Annealing for Combinatorial Clustering
• Item Listing Optimization for E-commerce Websites based on Diversity
• Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
• Fair Sampling by Simulated Annealing on Quantum Annealer
• Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
• Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian

Cited by in corpus (13)

• Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
• Exploration of new chemical materials using black-box optimization with the D-wave quantum annealer
• Hybrid quantum-classical computation for automatic guided vehicles scheduling
• Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
• Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
• Online calibration scheme for training restricted Boltzmann machines with quantum annealing
• Reverse quantum annealing assisted by forward annealing
• Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems
• Optimization of Connection Patterns between Mobile Phones and Base Stations using Quantum Annealing
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Enhancing Multiple Object Tracking Accuracy via Quantum Annealing
• Quantitative analysis of the effectiveness of mid-anneal measurement in quantum annealing
• Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing