イジングマシンを活用した配送計画最適化
理学専攻・情報科学コース
はじめに

1

2巡回セールスマン問題

2.1

一括で解く手法

4. グループ内の TSP を解く.
5. どの始点と終点を使うのかを決める.
「1. 訪問する都市をクラスタリング」では，イジングマシンを使用せずに，k-means 法 [3] を使用する．グルー
プ数を変えてクラスタリングを行い，一番平均シルエッ
ト係数 [4] の値がよかったグループ数を採用する．
「2. グループ間の TSP を解く」の目的関数は，式(1) の N が G に代わっただけである．G はグループ数を表す．
「3. グループ内の始点と終点の候補を決める．
」では，イジングマシンを使用しない．始点は前グループの重心から，終点は次グループの重心から，それぞれ近い順に R 箇所ずつ割り当てる．
「4. グループ内の TSP を解く」の目的関数は，式(1) と同様になる．ここで，N はグループ内の始点と終点を除いた都市数を表す．前段階で割り当てられた始点と終点を変えながら，全ての始点と終点の組合せで式 (1) を使用する．
「5. どの始点と終点を使うのかを決める．
」の目的関数は，次式で示される．

イジングマシンで TSP を解く場合，目的関数は次式のようになる．以下，この手法を「一括」と呼ぶ．

H=

大石 美賀

3. グループ内の始点と終点の候補を決める.

近年，ネットショップの普及により，宅配便の需要が高まり，その取扱数が増加している．一方で予算的な問題などの理由から，運送業は人手不足が深刻な問題である．この問題の解決策として，時間指定などの制約を守りながら，移動コストが最小になる配送計画の最適化が挙げられる．これは，組合せ最適化問題として解くことが可能である．先行研究では，この問題に特化した専用計算機のイジングマシンの一種である，アニーリングマシンを使用し，実際に渋滞軽減などの効果を確認できている [1, 2]．イジングマシンとは，2値変数の 2 次式で与えられた目的関数を扱い，それを最小化する変数の組合せを探索するマシンである．
そこで，本研究では，イジングマシンを用いて，巡回セールスマン問題 (以下，TSP) を組み合わせて解くことで，配送計画を最適化する手法を考案した．また，運送業者へのヒアリング調査を行い，調査結果に即した配送計画最適化を行う．

NN ∑∑2040636

H=dij xi,t xj,t+1 + Hp1 + Hp2(1)G ∑∑∑dpq xp xq +g=1 p∈Qg q∈Qg+1G ∑∑Cp xp + Hp5 (3)g=1 p∈Qgi,j=0 t=0

dpq は組合せ p, q 間の移動コスト，Cp は，始点と終点の組合せ p の時のグループ内の移動コスト，Qg はグループ g 内の組合せの集合を表す．変数 xp は始点と終点の組み合わせ p を選ぶかどうかを示し，選ぶ場合は 1，選ばない場合は 0 とする．P を始点と終点の組合せの総数とする．必要ビット数は P G となる．
Hp5 は，「各グループ内で組合せを 1 つだけ選ぶ」という制約項であり，次式のように示す．
2G∑∑
Hp5 = γxp − 1(4)dij は都市 i, j 間の移動コスト，N は都市数を表す．変数 xi,t は都市 i に t 番目に訪問するかどうかを表し，訪問する場合は 1，訪問しない場合は 0 とする. 必要ビット数は N 2 となる．
Hp1 は「各時刻で 1 箇所にいること」，Hp2 は「各都市には 1 度だけ訪問すること」を表す制約項であり，次式のように表せる．
Hp1 = α(NN∑∑t=0

Hp1 = βxi,t − 1i=0(NN∑∑i=0)2(2a))2xi,t − 1g=1(2b)

この時 γ は制約項の強さを表す．

t=0

2.3

ここで，α, β は制約項の強さを表す．

2.2

p∈Qg

比較結果

ベンチマーク問題 [5] を使用し，一括と 5 段階でそれぞれ 50 回ずつ実行し，比較指標を算出した．それを下記の図 1 に示す．それぞれの項目で，両者のうち，より良い結果のものを赤字としている．
主要部分の次元数については，一括は都市数が増えるにつれて，指数関数的に上昇するが，5 段階はクラスタリングされることにより，都市数が増えても緩やかに上昇した．
平均誤差率については，どちらもデータセットにより差があった．しかし両者を比較すると，ulysses16 とdj38 を除いては，5 段階の方が精度がよくなった．

段階的な解法

一括で解く手法は，使用できる変数の数の制限があり，また問題の大きさによっては，計算コストや解の精度にも問題が生じる．そこで，本研究では，問題規模の大きい TSP を解けるように，段階的な解法を考案した．以下，この手法を「5 段階」と呼ぶ．

1. 訪問する都市を適当な数のグループにクラスタリング
2. グループ間の TSP を解く.
1

ありを含んでいるため，それに対応できるようにする．
この目的関数は，式 (1) に，時間指定のペナルティ項Htime を加えたものになる．これは，その時間枠の中で，最も早い配達時間帯に時間指定されている配達先を含むグループを前半に，最も遅い配達時間帯に時間指定されている配達先を含むグループを後半に回るようにする．配達時間帯 m に時間指定された配達先を含むグループを最初に，配達時間帯 n に時間指定された配達先を含むグループを最後に回らなければ，ペナルティが追加される．これにより，複数の配達時間枠を含む状況における，時間指定ありへの対応ができる．

3.2
図 1: 一括と 5 段階の結果．主要部分の次元数，平均誤差率，平均実行時間の 3 項目で比較した．
平均実行時間については，最小の bruma14 を除いて，5 段階の方が良い結果となった．ここで，実行時間とは，実行開始から解が出力されるまで，としている．どちらも都市数が増えるにつれて，平均実行時間が増加する傾向にあったが，その増加のしかたに違いが見られた．一括は，指数関数的な増加であるが，5段階は線形的な増加であった．

3配送計画

3.1

アルゴリズム実行例

小規模のデータを作成し，提案するアルゴリズムを用いて配送計画を立てた．その実行例を図 2 に示す．
図 2 が，意図した配送計画であることが，確認できる．

5 段階の手法を元に，1，2 段階目を時間指定にも対応できるように変更した．
図 2: 赤が営業所，色はグループを表す．丸の大きさ

1. 配達先を時間指定を考慮してクラスタリング

は，時間指定された時間帯．一番小さいものは時間指2. 時間指定が含まれているグループを優先的に回る
ように，グループ間の TSP を解く．

定なし．丸付き数字はグループを回る順番である．

4

3,4,5 段階目は，2.2 節と同様である．
「1. 配達先を時間指定を考慮してクラスタリング」
では，k-means 法ではなく，イジングマシンを使用した．ここでは，その目的関数は次式を使用した．
H=N ∑G∑(dij + αkij )xi,g xj,g + Hp1

本研究では，イジングマシンを使用し，配達事業における配送計画の最適化を行なった．問題規模の小さ
い TSP を複数回解いて組み合わせる手法を取ることで，現行のイジングマシンでは解けないサイズに対応できるようにした．
また，この考案手法を，時間指定などを考慮できるように変更することで，配送計画を最適化した．

(5)i,j=1 g=1

dij は配達先 i, j 間の距離，N は入力された総配達先数，G は分けるグループ数を示す．変数 xi,g は，配達先 i がグループ G に属するかどうかを示し，属する場合は 1，属さない場合は 0 とする．必要ビット数は N Gとなる．時間指定を考慮する項は αkij で，kij は配達先 i, j が同じ時間帯に時間指定されていない場合 1, そうでないなら 0 とする．
Hp1 は，「各配達先の所属グループは 1 つ」を表す制約項であり，次式のように示す．
( G)2N∑∑Hp1 = β(6)xi,g − 1i=1

まとめ

参考文献
[1] H. Irie, G. Wongpaisarnsin, M. Terabe, A. Mikiand S. Taguchi, International Workshop on
Quantum Technology and Optimization Problems,Springer, pp. 145–156 (2019).
[2] F. Neukart et al., Frontiers in ICT 4, 29 (2017).
[3] J. MacQueen et al., Proceedings of the fifth Berkeley symposium on mathematical statistics andprobability, Vol. 1, No. 14, Oakland, CA, USA,pp. 281–297 (1967).

g=1[4] P. J. Rousseeuw, Journal of computational andapplied mathematics 20, 53 (1987).

β は制約項の強さを表す．またグループ数については，何度もクラスタリングを行うと，計算コストがかかるため，あらかじめ決めておく．
「2. 時間指定が含まれているグループを優先的に回るように，グループ間の TSP を解く．
」は，時間指定[5] G. Reinelt, ORSA journal on computing 3, 376(1991).

2