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

Siya Bao, Masashi Tawada, Shu Tanaka, Nozomu Togawa

研究成果: Article査読

抄録

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.

本文言語English
ページ(範囲)445-459
ページ数15
ジャーナルIEEE Transactions on Consumer Electronics
70
1
DOI
出版ステータスPublished - 2024 2月 1

ASJC Scopus subject areas

  • 電子工学および電気工学
  • メディア記述

フィンガープリント

「An Ising-Machine-Based Solver of Vehicle Routing Problem With Balanced Pick-Up」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル