We are now basically staying at home and sometimes waiting for delivery. Here we optimize the delivery as to achieve delivery optimization to get much more efficiency using QUBO.
We now try optimize the delivery with a delivery startup https://207inc.jp in Japan to apply for actual applications.
Now we have a lot of baggages so first we just make group among the nearly address. Using clustering we first make 2 cluster on D-wave Leap2.
We consider 40 address to 2 clusters(groups). Node inside the cluster are close each other. We just prepared a simple example.
By using D-Wave Leap2, we could make 2 cluster easily.
If the number of address is large, even we use quantum computing we cannot calculate efficiently. We first need to decompose the list of address to smaller groups.
We just put the code on python, if you want to try on clustering please refer to it.
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
Set the size of the node.
halfnode = 20 #half of number of node node = halfnode*2 cluster = 2 N = node*cluster
We need 80qubits for 40nodes * 2clusters
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)) # scatter plot plt.scatter(x, y)
we set the distances between nodes.
#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]
And then set the constraint
#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
We connect these matrix
#set a QUBO M = 1 qubo = A+B*M
Let’s check the connection and nodes.
#show as network G = nx.from_numpy_matrix(qubo) nx.draw_networkx(G) plt.show()
And then first try work on simulator using blueqat. We set value of M as 100. It is not good too small or too large.
#solved on blueqat M = 100 qubo = A+B*M a = Opt() a.qubo = qubo res = a.run() #print(res) print(sum(res))
And then all of these calculation finished, now we got,
plt.scatter(x, y, c=res[::2])
This is a simulation on local machine, next we try send this problem to Leap2.
#to Leap2 bqm = dimod.BQM.from_numpy_matrix(qubo) token = "your token here" sampler = LeapHybridSampler(token=token) response = sampler.sample(bqm) #print(response.first.sample) resv = response.first.sample.values() print(sum(resv))
The token can be get from D-Wave’s website. And finally we get the result and correctly clustered.
plt.scatter(x, y, c=list(resv)[::2])
Next we try these data on actual map and solve much more detailed address.