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

Siya Bao, Masashi Tawada, Shu Tanaka, Nozomu Togawa

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)445-459
Number of pages15
JournalIEEE Transactions on Consumer Electronics
Volume70
Issue number1
DOIs
Publication statusPublished - 2024 Feb 1

Keywords

  • Ising machine
  • QUBO model
  • load balancing
  • pick-up service
  • vehicle routing

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Media Technology

Fingerprint

Dive into the research topics of 'An Ising-Machine-Based Solver of Vehicle Routing Problem With Balanced Pick-Up'. Together they form a unique fingerprint.

Cite this