Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity

被引：45

作者：

Irie, Hirotaka ^{[1
]}

Wongpaisarnsin, Goragot ^{[2
]}

Terabe, Masayoshi ^{[1
]}

Miki, Akira ^{[1
]}

Taguchi, Shinichirou ^{[1
]}

机构：

[1] DENSO Corp, Tokyo Off, Informat Elect R&I Dept, Elect R&I Div, Tokyo 1036015, Japan

[2] Toyota Tsusho Nexty Elect Thailand Co LTD, Contents Dev & Distribut Dept, Bangkok 10330, Thailand

来源：

QUANTUM TECHNOLOGY AND OPTIMIZATION PROBLEMS | 2019年 / 11413卷

关键词：

Vehicle routing problem; QUBO; Quantum annealing;

D O I：

10.1007/978-3-030-14082-3_13

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We propose a brand-new formulation for capacitated vehicle routing problem (CVRP) as a 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 can be successfully realized. Similarly, constraints of capacities are also introduced, where capacitated quantities are allowed to increase and decrease according to the cities in which vehicles arrive. As a bonus of capacity-qubits, one can also obtain a description of state, which allows us to set various traveling rules, depending on the state of each vehicle. As a consistency check, the proposed QUBO formulation is also evaluated using a quantum annealing machine, D-Wave 2000Q.

引用

页码：145 / 156

页数：12

共 9 条

[1] THE TRUCK DISPATCHING PROBLEM [J].

DANTZIG, GB ;

RAMSER, JH .

MANAGEMENT SCIENCE, 1959, 6 (01) :80-91

[2]

Feld S, 2018, QUB EUR 2018 D WAV U

[3]

HOPFIELD JJ, 1985, BIOL CYBERN, V52, P141

[4] COMPUTING WITH NEURAL CIRCUITS - A MODEL [J].

HOPFIELD, JJ ;

TANK, DW .

SCIENCE, 1986, 233 (4764) :625-633

[5]

Itoh T, 2017, AD QUANT COMP C AQC

[6] Quantum annealing with manufactured spins [J].

Johnson, M. W. ;

Amin, M. H. S. ;

Gildert, S. ;

Lanting, T. ;

Hamze, F. ;

Dickson, N. ;

Harris, R. ;

Berkley, A. J. ;

Johansson, J. ;

Bunyk, P. ;

Chapple, E. M. ;

Enderud, C. ;

Hilton, J. P. ;

Karimi, K. ;

Ladizinsky, E. ;

Ladizinsky, N. ;

Oh, T. ;

Perminov, I. ;

Rich, C. ;

Thom, M. C. ;

Tolkacheva, E. ;

Truncik, C. J. S. ;

Uchaikin, S. ;

Wang, J. ;

Wilson, B. ;

Rose, G. .

NATURE, 2011, 473 (7346) :194-198

[7] Quantum annealing in the transverse Ising model [J].

Kadowaki, T ;

Nishimori, H .

PHYSICAL REVIEW E, 1998, 58 (05) :5355-5363

[8] Ising formulations of many NP problems [J].

Lucas, Andrew .

FRONTIERS IN PHYSICS, 2014, 2 :1-14

[9]

MEZARD M, 1985, J PHYS LETT-PARIS, V46, pL771, DOI 10.1051/jphyslet:019850046017077100

← 1 →