Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity
From MaRDI portal
Publication:6315637
arXiv1903.06322MaRDI QIDQ6315637
Akira Miki, Goragot Wongpaisarnsin, Hirotaka Irie, Masayoshi Terabe, Shinichirou Taguchi
Publication date: 14 March 2019
Abstract: We propose a brand-new formulation of capacitated vehicle routing problem (CVRP) as quadratic unconstrained binary optimization (QUBO). The formulated CVRP is equipped with time-table which describes time-evolution of each vehicle. Therefore, various constraints associated with time are successfully realized. With a similar method, constraints of capacities are also introduced, where capacitated quantities are allowed to increase and decrease according to the cities which vehicles arrive. As a bonus of capacity-qubits, one also obtains a description of state, which allows us to set a variety of traveling rules, depending on each state of vehicles. As a consistency check, the proposed QUBO formulation is also evaluated by quantum annealing with D-Wave 2000Q.
Has companion code repository: https://github.com/June3141/TSP_denso_qubo
This page was built for publication: Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315637)
