2019/03/14 by Hirotaka Irie, Goragot Wongpaisarnsin, Irie, Hirotaka +7 · 5 citations
Computer Science · Mathematics · Physics and Astronomy · #Discrete Mathematics (cs.DM) #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Optimization and Control (math.OC) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #cs.DM #cs.ET #math.OC #quant-ph
paper · pdf · doi:10.48550/arxiv.1903.06322
14 pages, 2 figures, to be published in Lecture Notes in Computer Science (QTOP 2019)
openalex publication_date 2019/03/14 · arxiv created 2019/03/15 · arxiv updated 2019/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.