Quantum-inspired algorithm for vehicle sharing problem

• Main Authors: SUEN, Whei Yeap, LEE, Chun Yat, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/6232; https://ink.library.smu.edu.sg/context/sis_research/article/7235/viewcontent/IEEE_QCE_2021_Quantum_inspired_Algorithm_for_Vehicle_Sharing_Problem.pdf
• Institution: Singapore Management University

Recent hardware developments in quantum technologies have inspired a myriad of special-purpose hardware devices tasked to solve optimization problems. In this paper, we explore the application of Fujitsu’s quantum-inspired CMOS-based Digital Annealer (DA) in solving constrained routing problems arising in transportation and logistics. More precisely in this paper, we study the vehicle sharing problem and show that the DA as a QUBO solver can potentially fill the gap between two common methods: exact solvers like Cplex and heuristics. We benchmark the scalability and quality of solutions obtained by DA with Cplex and with a greedy heuristic. Our results show that the DA is a general QUBO solver that is more robust than heuristics, and more scalable than Cplex. Our methodology and framework which focus on QUBO problems is also applicable to other quantum-inspired and fully quantum devices that are undergoing development.