2019/03/14 by Hirotaka Irie, Goragot Wongpaisarnsin, Irie, Hirotaka +7 · 4 citations
Computer Science · #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)
paper · pdf · doi:10.48550/arxiv.1903.06322
openalex publication_date 2019/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a brand-new formulation of capacitated vehicle routing problem\n(CVRP) as quadratic unconstrained binary optimization (QUBO). The formulated\nCVRP is equipped with time-table which describes time-evolution of each\nvehicle. Therefore, various constraints associated with time are successfully\nrealized. With a similar method, constraints of capacities are also introduced,\nwhere capacitated quantities are allowed to increase and decrease according to\nthe cities which vehicles arrive. As a bonus of capacity-qubits, one also\nobtains a description of state, which allows us to set a variety of traveling\nrules, depending on each state of vehicles. As a consistency check, the\nproposed QUBO formulation is also evaluated by quantum annealing with D-Wave\n2000Q.\n