20.04.14

[Delivery Optimization] Clustering on Quantum Annealing

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.

Example Code

Importing tools

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))

40

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.



To COVID-19 Page