TY - GEN
T1 - Optimization of Practical Time-Dependent Vehicle Routing Problem by Ising Machines
AU - Tsuyumine, Yui
AU - Masuda, Kenichi
AU - Hachikawa, Takeshi
AU - Haga, Tsuyoshi
AU - Yachi, Yuta
AU - Shirai, Tatsuhiko
AU - Tawada, Masashi
AU - Togawa, Nozomu
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
KW - Ising machine
KW - QUBO
KW - annealing machine
KW - delivery planning
KW - quantum annealer
UR - http://www.scopus.com/inward/record.url?scp=85187023646&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85187023646&partnerID=8YFLogxK
U2 - 10.1109/ICCE59016.2024.10444436
DO - 10.1109/ICCE59016.2024.10444436
M3 - Conference contribution
AN - SCOPUS:85187023646
T3 - Digest of Technical Papers - IEEE International Conference on Consumer Electronics
BT - 2024 IEEE International Conference on Consumer Electronics, ICCE 2024
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2024 IEEE International Conference on Consumer Electronics, ICCE 2024
Y2 - 6 January 2024 through 8 January 2024
ER -