自宅待機が増えるため、物資を宅配に頼ることも多くなりました。ここでは、宅配を最適化し、より効率的に同じ時間内で宅配ができるようにQUBOを利用して、宅配を最適化していきたいと思います。
今回の試みは207株式会社様と行っております。
今回は宅配の荷物が多いため、最初に宅配先をエリア分けします。ここではクラスタリングと呼ばれる手法を使い、D-Wave Leap2で実装をして見ます。
今回は40の配達先を2つのグループに分けます。グループは距離的に近いものが採用されます。距離の分布は下記を想定します。
D-WaveのLeap2にはこれらの距離情報とグループ分けする数（今回は2）を入力して計算します。結果は、
このように二つのグループに分かれました。配達が多い場合、量子コンピューティングを使っても同時にたくさんの宅配先を効率的に回るルートを算出することは難しいです。そのため、最初にある程度現在のマシンで対応できるサイズに落とし込む必要があり、今回はクラスタリングを利用しました。興味がある方は、下記に参考に実機のLeap2に投げるコードを添付しますので、試して見てください。
ツールの読み込み
import dimod
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from dwave.system import LeapHybridSampler
from blueqat.opt import *
%matplotlib inline
次にノードのサイズを指定します。
halfnode = 20 #half of number of node
node = halfnode*2
cluster = 2
N = node*cluster
今回利用するのは40ノードを2つのクラスタに分けるためには40*2=80量子ビット必要です。データを作って散布図を確認します。
x = np.random.normal(0, 1.5, halfnode)
y = np.random.normal(0, 1.5, halfnode)
x = np.append(x, np.random.normal(5, 1.5, halfnode))
y = np.append(y, np.random.normal(5, 1.5, halfnode))
散布図を描画
plt.scatter(x, y)
まずは距離を行列に格納します。
#initialize distance
d = np.zeros((node,node))
for i in range(0, node-1):
for j in range(i+1, node):
a = np.array([x[i],y[i]])
b = np.array([x[j],y[j]])
d[i][j] = np.linalg.norm(a-b)
#map distance to qubo
A = np.zeros((N,N))
for i in range(0, node-1):
for j in range(i+1, node):
A[i*2][j*2] = A[i*2+1][j*2+1] = d[i][j]
次に制約条件を決める行列を設定します。
#initialize constraint
B = np.zeros((N,N))
for i in range(N):
B[i][i] = -1
for i in range(node):
B[i*2][i*2+1] = 2
これはネットワーク問題と呼ばれている問題で、この二つの行列を接続します。
#set a QUBO
M = 1
qubo = A+B*M
図示して見ると、
#show as network
G = nx.from_numpy_matrix(qubo)
nx.draw_networkx(G)
plt.show()
見てるだけでは面白くないので、シミュレータで解いて見ます。Mの値は二つの行列の最大値などを見てバランスで決めます。ここでは100にします。大きくしすぎると精度に影響します。
#solved on blueqat
M = 100
qubo = A+B*M
a = Opt()
a.qubo = qubo
res = a.run()
#print(res)
print(sum(res))
40
チェックとして、上記はクラスタがきちんとできているかノードの数とチェックをしました。大丈夫そうです。最後に分かれているかまずは、量子ビット単位で見て見ます。
plt.scatter(x, y, c=res[::2])
上記のようにきれいに分かれています。今回はわかりやすい例題で助かりました。次にD-WaveのLeap2に投げます。
#to Leap2
bqm = dimod.BQM.from_numpy_matrix(qubo)
token = "ここにトークン"
sampler = LeapHybridSampler(token=token)
response = sampler.sample(bqm)
#print(response.first.sample)
resv = response.first.sample.values()
print(sum(resv))
TokenはD-Waveのサイトから入手できますので、各自試して見てください。
plt.scatter(x, y, c=list(resv)[::2])
きれいにできました。次回は実際の地図に導入し、さらに細かい配達をサポートします。