Optimization of Practical Time-Dependent Vehicle Routing Problem by Ising Machines

Yui Tsuyumine*, Kenichi Masuda, Takeshi Hachikawa, Tsuyoshi Haga, Yuta Yachi, Tatsuhiko Shirai, Masashi Tawada, Nozomu Togawa

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Vehicle Routing Problem (VRP) is an extension of the Travelling Salesperson Problem (TSP). A VRP determines the delivery sequence where multiple vehicles are available, delivery should be made to multiple points, and each point should be visited once. However, road conditions change depending on the time of day, and the time required to travel between two points changes accordingly. Unless these changes are considered, a calculated minimum cost is not realized in actual logistics. Aiming to apply the Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW), which is a VRP extension that counts changes in the time required to travel between two points depending on the time of day, to Ising machines including quantum annealers, this paper proposes an effective formulation to realize TDVRPTW, composed of several objective functions and constraints. Further, this paper compares and evaluates the results obtained by a physical Ising machine and confirms the validity of the formulation, thus verifying the applicability of the TDVRPTW to quantum computing.

Original languageEnglish
Title of host publication2024 IEEE International Conference on Consumer Electronics, ICCE 2024
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350324136
DOIs
Publication statusPublished - 2024
Event2024 IEEE International Conference on Consumer Electronics, ICCE 2024 - Las Vegas, United States
Duration: 2024 Jan 62024 Jan 8

Publication series

NameDigest of Technical Papers - IEEE International Conference on Consumer Electronics
ISSN (Print)0747-668X
ISSN (Electronic)2159-1423

Conference

Conference2024 IEEE International Conference on Consumer Electronics, ICCE 2024
Country/TerritoryUnited States
CityLas Vegas
Period24/1/624/1/8

Keywords

  • Ising machine
  • QUBO
  • annealing machine
  • delivery planning
  • quantum annealer

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Optimization of Practical Time-Dependent Vehicle Routing Problem by Ising Machines'. Together they form a unique fingerprint.

Cite this