An Ising-Machine-Based Solver of Vehicle Routing Problem With Balanced Pick-Up

Vehicle routing applications are ubiquitous in the field of pick-up and delivery service. We focus on the vehicle routing problem with balanced pick-up called VRPBP which originates from the package pick-up service. The aim of the problem is not only to efficiently explore the shortest travel route but also to balance loads between depots and vehicles. These problems can be regarded as optimization problems, and recent developments in Ising machines, including quantum annealing machines, bring us a new opportunity to solve complex real-world optimization problems. In this paper, a two-phase method and a three-phase method using Ising machines are proposed for solving the VRPBP. As the applicability of current Ising machines is limited due to the small size of Ising spins and connectivities, we partition the complex problem into two or three sub-problems, and the key elements of each sub-problem are mapped onto quadratic unconstrained binary optimization (QUBO) models to fit in the structure of the Ising machines. We first compared the performances of the Ising machine on the standard TSP and CVRP datasets with a conventional state-of-the-art solver and three conventional methods. Then, we evaluated the performances of the proposed methods compared with five conventional method for solving the VRPBP. The results confirm the effectiveness of the two proposed methods in solving vehicle-routing-related optimization problems.