アニーリングマシンを用いた配送計画
大石美賀

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

はじめに

α は制約項の強さを表す．
「2. 駐車可能箇所の割り当て」では，「1. 配達先のクラスタリング」でクラスタリングされたグループごとに重心を取り，その重心から近い順に 2 箇所ずつ駐車可能箇所を割り当てる．
「3. 台車で回る部分の TSP」は次式で示される．

近年，ネットショップの普及により，宅配便の需要が高まっている．一方で，過酷な労働状況や予算的な問題から運送業の人手不足が問題になっている．この問
題の解決策として，配達における運送計画の最適化が挙げられる．最適な運送計画は巡回セールス問題 (以下TSP) を組み合わせて解くことで求めることができる．
そこで本研究ではアニーリングマシン「デジタルア
ニーラ [1]」を利用して，駐車箇所や配達物の位置情報を考慮した配送計画をするためにアルゴリズムを構築した．また実際に構築したアルゴリズムを，仮想データを用いてシミュレーションし，考察した．アニーリ
ングマシンとはイジングモデル [2] や QUBO 形式 [3]で表現された組合せ最適化問題を高速に処理できる専用計算機である．

2H=t=1

Hp3 = βH=GP ∑∑

Cp xp,t +p=0 t=0xi,t − 1(5)t=1GP ∑∑

Tpq xp,t xq,t+1(6)p,q=0 t=0+ Hp4 + Hp5
Cp は駐車箇所 p を選んだ時の台車での配達にかかる時間，Tpq は駐車箇所 p, q 間の車両での移動時間，Pは「2. 駐車可能箇所の割り当て」で選ばれた総駐車箇
所数，G はグループ数，p = 0 は営業所を示す．変数
xp,t は駐車箇所 p に t 番に駐車しない場合は 0，駐車する場合は 1 となる．営業所からスタートし，営業所に戻ってくるので x0,0 = x0,G+1 = 1 の固定値となる．
必要ビット数は P G となる．Hp4 は「各時刻で一箇所にいる」ことを，Hp5 は「各グループに一度だけ駐車する」ことを表す制約項であり，次式で表される．
( P)2G∑∑
Hp4 = α(7)xp,t − 1(1)i,j=1 g=1

dij は配達先 i, j 間の距離，N は配達先数，G はグループ数を示す．変数 xi,g は配達先 i がグループ g に属するかどうかを示し，属さない場合は 0，属する場合は1 となる．必要ビット数は N G である．Hp1 は「各配達先の所属グループは 1 つ」を表す制約項であり次式のように表せる．
( G)2N∑∑Hp1 = αxi,g − 1(2)i=1)2α, β は制約項の強さを表し，ここでは式 (3) の ti,j を正規化していることから α = 1, β = 1 とする．
「2. 駐車可能箇所の割り当て」で割り当てられたそれぞれの駐車箇所 p で行い，制約を満たしたものの移動時間をCp とする．
「4. 車両で回る部分の TSP」は次式で示される．

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

dij xi,g xj,g + Hp1

i=1

(DD∑
∑
i=1

アルゴリズムと定式化

N ∑G∑

(3)

tij は配達先 i, j 間の徒歩での移動時間，D は配達先数，i = 0 は駐車箇所を示す．変数 xi,t は配達先 i を t番目に配達しない場合は 0，配達する場合は 1 を示す．
駐車箇所からスタートし、駐車箇所に戻ってくるので，x0,0 = x0,D+1 = 1 の固定値となる．必要ビット数はD2 となる．Hp2 は「各時刻で一箇所にいる」ことを，Hp3 は「各配達先に一度だけ訪問する」ことを表す制約項であり次式のように表せる．
(D)2D∑∑
Hp2 = αxi,t − 1(4)

問題設定

H=tij xi,t xj,t+1 + Hp2 + Hp3

i,j=0 t=0

本研究では，1 台の車両で複数の配達先を巡回する際に移動時間が最小となるルートをデジタルアニーラを用いて求める．配達地域としては都市部での配達を想定する．都市部では駐車できる箇所が限られているため車両と台車を用いて配達する．手順としては，「駐車箇所まで車両で移動し，車両を降りて台車に荷物を積み，台車で今の駐車箇所から配達する荷物を配達し終えたら，車両に乗って次の駐車箇所まで移動する」という流れを繰り返す．車両は一度に一定数の荷物を積み、営業所を出発して積んだ荷物を全て配達し終えたら最終的に営業所に戻る．

3D ∑D
∑

t=1

Hp5 = βG
∑
g=1

g=113




p=1G ∑∑
t=1 p∈Qg

2
xp,t − 1(8)ここで Qg は，グループ g に割り当てられた駐車可能箇所の集合である．このモデルは最短となるルートと適切な駐車可能箇所を求める．

4

上記の結果から，G = 9 のときに配達にかかる時間が一番短くなることがわかった．G = 9 のときのルートを図 3 に示す．

データ

本研究では運送業者へのヒアリング調査の元，一台のトラックに 60 個の配達物が積まれることを想定し，配達範囲を文京区大塚 4,5,6 丁目として，営業所を 1箇所，配達先をランダムに 60 箇所プロットした．また駐車可能箇所は地図から駐車可能な場所を探して同じ範囲に 86 箇所設定した．図 1 は作成した配達先，駐車可能箇所，営業所の位置情報である．青が配達先を，赤が駐車可能箇所と営業所を表している．

図 3: G = 9 の時の配送ルート
赤色の営業所からスタートして，矢印が車両のルート，細線が台車でのルートを表している．G = 9 では，4 から 7 箇所の配達先が 1 グループになっていた．配達にかかる時間は 4 時間 2 分となった．使用ビット数については，「1. 配達先のクラスタリング」では 60 × 9 = 540ビット，「3. 台車で回る部分の TSP」では最大で 82 = 64ビット，最小で 42 = 16 ビット，
「4. 車両で回る部分のTSP」では 18 × 9 = 162 ビットである．

図 1: 配達先等のデータ

56

結果

まとめ

本研究では，一台のトラックの一度の配達における配送計画をアニーリングマシンを用いて行った．グループ数 G を 8 から 12 の範囲で変えて，その時の配達時間の変化を観察した．今回は台車に積む荷物の数に関わらず，一律で台車に荷物を積む時間を 3 分と設定し，台車や車両の積載量を考慮していない．今後はそれらを考慮することで，より現実的な配送計画のシミュレーションを行いたい．

富士通デジタルアニーラを用いて上記のデータを使用し，配送計画の最適化を実際に行った．より良い駐車可能箇所を決めるために，「2. 駐車可能箇所の割り当て」では 1 グループに 2 箇所ずつ割り当てをした．
「3.
台車で回る部分の TSP」で D = 6 前後で精度の高い解が得られることから，60 箇所の配達先を「1. 配達先のクラスタリング」で，約 6 箇所前後で 1 グループになるようにクラスタリングをした．グループ数を変えると配達にかかる時間が変化することから，グループ数を 8 から 12 の範囲で変えて配達時間の変化をみた．
その結果を図 2 に示す．なお台車に積む荷物の数に関わらず，台車に荷物を積む時間を 3 分，1 つの配達先にかかる時間を 1.5 分として計算する．

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

参考文献[1] 富士通, 「デジタルアニーラ」, https://www. fujitsu.com/jp/digitalannealer,（2020 年 1 月 26日アクセス）.
[2] M.W. Johnson, et al., Quantum annealing with
manufactured spins, Nature 473, 194 (2011).
[3] F. Glover, G. Kochenberger and Y. Du, A Tutorial on Formulating and Using QUBO Models,arXiv:1811.11538 (2019)[4] A. Lucas, Ising formulations of many NP problems, Front. Physics 2, 5 (2014).

図 2: グループ数と配達時間 (時間)14