量子アニーリングマシンを用いた時間制約付き配送ルート最適化
松本奈紗

1(指導教員：工藤和恵)

はじめに配達先 i, j 間の時間指定の有無が同じ場合は 0，異なる場合は 1 とする．式 (1) は一度の実行でクラスタリングを行うモデルである．しかしマシンの使用できるビット数によっては，N ，G が大きいと，式 (1) が使用できない場合がある．その場合は式 (1) が使用できるようになるまで次式を使って配達先を 2 分割する．

近年、E コマース市場の成長による宅配便取扱数の増加に伴い、運送業の人手不足が問題となっている．
また、輸送交通量が増加し、交通渋滞や排気ガスによる環境汚染も社会的問題となっている．これらの問題の解決策の一つとして、配送ルートを最適化することが挙げられる．配送ルートの最適化では時間指定などの様々な制約の中で最適なルートを求める必要がある．
そこで、組合せ最適化問題に特化したマシンである量子アニーリングマシンを用いて、時間指定を考慮した配送ルートの最適化を行った．
量子アニーリングマシンとはイジングモデル [1] やQUBO 形式 [2] で表現された組合せ最適化問題を解くための専用計算機である．

2

H=

tij xi,t xj,t+1 + Hp2 + Hp3(3)

tij は配達先 i, j 間の徒歩での移動時間，D は配達先数，i = 0 は駐車可能箇所を示す．変数 xi,t は配達先 i
を t 番目に配達しない場合は 0，配達する場合は 1 とする．Hp2 は「各時刻で一箇所にいる」ことを，Hp3
は「各配達先に一度だけ訪問する」ことを表す制約項である．
「2. 駐車可能箇所の割り当て」で割り当てられたそれぞれの駐車可能箇所 p で行い，制約を満たしたものの移動時間を Cp とする．
「4. 車両で回る部分の TSP」では，問題設定に応じて 2 種類のモデルを使い分ける．モデル 1 は時間指定ありの配達先を含むグループを優先的に回るモデルであり、次式を使用する．

以下のように順を追ってルートを求める．
1. 配達先のクラスタリング
2. 駐車可能箇所の割り当て
3. 台車で回る部分の巡回セールスマン問題 (TSP)
4. 車両で回る部分の TSP
量子アニーリングマシンを利用して問題を解くためには，イジングモデルや QUBO 形式の定式化 [3] が必要となる．目的関数 H が最小となる変数の組合せが解となるように定式化する．
「1. 配達先のクラスタリング」は「3. 車両で回る部分の TSP」のグループ分けのために行うもので，次式で示される．

(dij + αkij )xi,g xj,g + Hp1

D ∑D∑
i,j=0 t=0

定式化N ∑G∑(2)

変数 σi は配達先 i がグループ 1 に属する場合は 1，グループ 2 に属する場合は −1 とする．式 (2) は一度の実行で配達先を 2 分割するモデルである．問題の大きさやマシンの使えるビット数に応じて式 (1) が使えるようになるまで式 (2) を繰り返す．
次に「2. 駐車可能箇所の割り当て」では，「1. 配達先のクラスタリング」でクラスタリングされたグループごとに重心を取り，その重心から近い順に 2 箇所ずつ駐車可能箇所を割り当てる．
「3. 台車で回る部分の TSP」は次式で示される．

問題設定

H=(dij + αkij )σi σji,j=1

本研究では，1 台の車両で複数の配達先を巡回する際に移動時間が最小となるルートを量子アニーリングマシンを使って求める．配達では，「駐車可能箇所まで車両で移動し，車両を降りて台車に荷物を積み，台車で今の駐車可能箇所から配達する荷物を配達し終えたら，車両に乗って次の駐車可能箇所まで移動する」という流れを繰り返すものとする．また配達先の中には配達時間指定がされているものがあるとする．ここで，配達時間指定とは 1 日の配達可能時間のうち，2–3 時間ごとに区切られた配達時間枠のいずれかに配達が希望されていることを表す．車両は配達時間枠ごとに各地域の営業所を出発地し，最終的に営業所に戻ることとする．各配達時間枠において，配達時間指定がされている配達先を優先的に回るようなルートを求める．

3N∑

H=H=GG ∑∑γbg txg,t +g=0 t=0G ∑G∑g,h=0 t=0

Tgh xg,t xh,t+1(4)+ Hp4 + Hp5
変数 bg は配達先のグループ g に時間指定ありの配達先が含まれていない場合は 0，含まれている場合は 1とする．変数 xg,t はグループ g に t 番に駐車しない場合は 0，駐車する場合は 1 とする．Tgh は駐車可能箇
所 g, h 間の車両での移動時間，G は配達先のグループ数，γ は正のパラメータである．g = 0 は営業所を示す．第 1 項は時間指定に関する項で，時間指定された配達先を含むグループを先に回れば小さい値を取るようにする．Hp4 は「各グループに一度だけ駐車する」
ことを表す制約項，Hp5 は「選ばれた各駐車可能箇所に一回だけ駐車する」ことを表す制約項である．
モデル 2 は時間指定ありの配達先を含むグループを必ず先に回るモデルであり，次式を使用する．

(1)

i,j=1 g=1

dij は配達先 i, j 間の距離，N は配達先数，G はグループ数，α は正のパラメータである．変数 xi,g は配達先
i がグループ g に属するかどうかを示し，属さない場
合は 0，属する場合は 1 とする．Hp1 は「各配達先の所属グループは 1 つ」という制約を満たすための項で，満たさない場合は値が大きくなる．パラメータ kij は15

H=G ∑G∑γbg Θ(t − Nb )xg,t

g=0 t=0+なし→なし」の順で回り，時間指定ありの配達先を含むグループを必ず先に回ることが確認できた．それぞれの駐車可能箇所で台車に荷物を載せる時間を 3 分，1つの配達先に荷物を届ける時間を 1.5 分とすると，移動時間を含めた総配達時間は，モデル 1 では 1 時間 35分，モデル 2 では 1 時間 44 分となった．図 2,3 にそれぞれのモデルでの実行結果を示す．太線は車両のルー
ト，細線は台車のルートを直線で表している．

G ∑G
∑

(5)
Tgh xg,t xh,t+1 + Hp4 + Hp5g,h=0 t=0

第 1 項はモデル 1 と同様に時間指定に関する項であるが，時間指定ありの配達先を含むグループを先に回ればモデル 1 よりも小さい値を取るようにする．Nb は時間指定ありの配達先を含むグループの個数である．
Θ(t − Nb ) は t − Nb ≤ 0 の場合は 0，t − Nb > 0 の場
合は 1 とする．
モデル 1・モデル 2 の両方とも，駐車可能箇所をランダムに選び，それぞれの式 (4)，式 (5) を実行することを複数回行い，車両での移動時間を求める．そして各駐車箇所ごとに台車での移動時間である Cp を加算した総移動時間が最も短くなるものを採用する．

4実行結果

都内中心部にある営業所からの配達を想定し，配達先 24 箇所 (時間指定されているものが 6 箇所)，駐車可能箇所 20 箇所をデータとして設定し，量子アニーリングマシンである「D-Wave2000Q」で実行した．24箇所の配達先を 6 グループにクラスタリングし，それぞれに 2 箇所ずつ駐車可能箇所を割り当てて，台車と車両のルートと移動時間を求めた．式 (2) を 1 回，式(1) を 2 回実行することでクラスタリングをした．ク
ラスタリングの結果を図 1 に示す．グループごとに色分けされており，大きな丸が時間指定されている配達先，小さな丸が時間指定されていない配達先を表している．

図 2: モデル 1 の最終的なルート

図 3: モデル 2 の最終的なルート

5

まとめ

本研究では，量子アニーリングマシンを用いて，時間指定を考慮した配達ルートの最適化を行った．今後，様々な問題設定に対応するために，配達先のクラスタリングの新たなモデルを追加するなど，より現実的なシミュレーションが行えるように改良する余地がある．

図 1: 配達先のクラスタリングの実行結果

Google Maps API を利用して，一方通行や渋滞などの交通情報を考慮した上で最短となる二点間のルートと移動時間を算出し，それを tij と Tij として用いた．
また駐車可能箇所に関する TSP では，駐車可能箇所をランダムに選び式 (4)，(5) を実行することを 5 回繰り返した中で総移動時間が最小の結果を採用した．ク
ラスタリングされた配達先の 6 グループのうち時間指定ありの配達先を含むものは 4 つとなった．以下，時間指定ありの配達先を含むグループを「あり」，時間指定ありの配達先を 1 つも含まないグループを「なし」とする．モデル 1 ではグループを「あり→なし→あり→あり→あり→なし」の順で回り，時間指定ありの配達先を含むグループを優先的に回ることが確認できた．
モデル 2 ではグループを「あり→あり→あり→あり→

謝辞 本研究は未踏ターゲット事業の支援を受けています．

参考文献[1] M.W. Johnson, et al., Quantum annealing withmanufactured spins, Nature 473, 194 (2011).
[2] F. Glover, G. Kochenberger and Y. Du, A Tutorial on Formulating and Using QUBO Models,arXiv:1811.11538 (2019).
[3] A. Lucas, Ising formulations of many NP problems, Front. Physics 2, 5 (2014).

16