Taxi Matching Problem¶
Let's solve the taxi matching problem as an example of a problem that uses both an objective function and constraints.
The taxi matching problem is the problem of minimizing the cost of dispatching a taxi given multiple customers and multiple taxi locations respectively.
The cost of dispatching a taxi can be defined in various ways, but for simplicity, we will assume that it is the total distance between the taxi and the customer. By matching taxis and customers, we can decide where to dispatch the taxi so as to minimize the total distance between each taxi and the destination customer.
Formulation of the Problem¶
First of all, the assumption of the problem here is that there are NN customers and the same number of NN taxis. Suppose that we are given the coordinates (ci,x,ci,y)(ci,x,ci,y) of the customers and (tj,x,tj,y)(tj,x,tj,y) of the taxis with indices i,j=0,1,⋯,N−1i,j=0,1,⋯,N−1. From these coordinates, let the distance between customer ii and taxi jj be the following:
dij=√(ci,x−tj,x)2+(ci,y−tj,y)2dij=√(ci,x−tj,x)2+(ci,y−tj,y)2
Decision Variable¶
The relation between customer ii and taxi jj can be divided into the following two patterns:
- Customer ii is assigned a taxi jj
- Taxi jj is not assigned to customer ii
We use the binary variable qijqij to represent these two states.
- When taxi jj is assigned to customer ii, qij=1qij=1
- When no taxi jj is assigned to customer ii, qij=0qij=0
| Customer \ Taxi | 00 | 11 | ... | N−1N−1 |
|---|---|---|---|---|
| 00 | q0,0q0,0 | q0,1q0,1 | ... | q0,N−1q0,N−1 |
| 11 | q1,0q1,0 | q1,1q1,1 | ... | q1,N−1q1,N−1 |
| ⋮⋮ | ⋮⋮ | ⋮⋮ | ... | ⋮⋮ |
| N−1N−1 | qN−1,0qN−1,0 | qN−1,1qN−1,1 | ... | qN−1,N−1qN−1,N−1 |
Objective Function¶
Using the above binary variables, the objective function, which is the total distance between the
matched
customer and the taxi, is given by following:
Since the variable qijqij means that customer ii and taxi jj are matched when 11, we only add up
the
distances that result in qij=1qij=1.
N−1∑i,j=0dijqijN−1∑i,j=0dijqij
Constraint¶
The next step is to define the constraints.
First, since we always assign one taxi to one customer, we need the following constraint for customer ii.
N−1∑j=0qij=1N−1∑j=0qij=1
In addition, since one taxi is always assigned to one customer, we also need the following constraint for taxi jj:
N−1∑i=0qij=1N−1∑i=0qij=1
Implementing the Problem¶
Since we need the coordinates of the customers and the taxies as input data, we will create a function that randomly generates the coordinates of the customers and the taxies and calculates the distances for all combinations of customers and taxies.
import numpy as np
# Randomly generate the coordinates of the customers and the taxies, and calculate the distances between the customers and the taxies
def gen_random_locations(num_customers: int, num_taxies: int):
rng = np.random.default_rng()
# Customer coordinates
loc_customers = rng.random(size=(num_customers, 2))
# Taxi coordinates
loc_taxies = rng.random(size=(num_taxies, 2))
# Construct a distance matrix between customer i and taxi j, distances[i, j]
distances = (
(loc_customers[:, np.newaxis, 0] - loc_taxies[np.newaxis, :, 0]) ** 2
+ (loc_customers[:, np.newaxis, 1] - loc_taxies[np.newaxis, :, 1]) ** 2
) ** 0.5
return loc_customers, loc_taxies, distances
For visualization purposes, we also create a function that, given the coordinates of a customer and a taxi, plot those coordinates.
%matplotlib inline
import matplotlib.pyplot as plt
# Visualize the location of customers and taxis
def show_plot(loc_customers: np.ndarray, loc_taxies: np.ndarray):
markersize = 100
fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(10, 10))
ax.set_xlabel("x")
ax.set_ylabel("y")
ax.scatter(
loc_customers[:, 0],
loc_customers[:, 1],
label="Customers",
marker="o",
color="red",
s=markersize,
)
ax.scatter(
loc_taxies[:, 0],
loc_taxies[:, 1],
label="Taxies",
marker="^",
color="blue",
s=markersize,
)
ax.legend(loc="upper right")
plt.show()
Determine N corresponding to the number of customers and the number of taxis, and
generate
their coordinates and distances with the gen_random_locations function we defined
earlier.
Plot the generated results to visualize the locations of customers and taxis.
N = 5
loc_customers, loc_taxies, distances = gen_random_locations(
num_customers=N, num_taxies=N
)
show_plot(loc_customers, loc_taxies)
Building a Binary Polynomial Model¶
Next, we define the QUBO variables that we will need. Since we want to have NN taxis for each NN customer, we define the QUBO variable as a two-dimensional array of N×NN×N as follows:
from amplify import VariableGenerator
# Generate a binary decision variable array
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, N))
Using these QUBO variables, the objective function is obtained as follows:
from amplify import sum
cost = (distances * q).sum()
The next step is to define the constraints.
The two constraints described at the beginning are represented as follows using the
one_hot
function, and they are added up to construct a constraint object.
from amplify import one_hot
customer_has_one_taxi = one_hot(q, axis=1)
taxi_has_one_customer = one_hot(q, axis=0)
constraints = customer_has_one_taxi + taxi_has_one_customer
By adding the objective function and constraints, the final binary polynomial model can be obtained as follows.
Here, the weight of the constraints relative to the objective function is important. Just to conclude, it is enough to set the maximum value of dijdij, and we will not go into the discussion of how strong it should be.
# Set the weight
constraints *= np.amax(distances) # type: ignore
# Combine objective function and constraints
model = cost + constraints
Running the Ising Machine¶
Set the client of the Ising machine to FixstarsClient, and also create a solver to solve
the
problem as follows:
from amplify import FixstarsClient, solve
from datetime import timedelta
# Set the client
client = FixstarsClient()
client.parameters.timeout = timedelta(milliseconds=1000) # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
# Solve the problem
result = solve(model, client)
The obtained solution can be checked as follows.
The final solution can be obtained by using the evaluate function and assigning the
solution
to the variable array defined in the beginning.
# If result is empty, the constraint condition was not satisfied and the solution cannot be found.
if len(result) == 0:
raise RuntimeError("Given constraint conditions are not satisfied")
# The value of objective function at the optimal solution (the sum of distances between the customers and taxies)
print(f"objective = {result.best.objective}")
# The values of decision variables at the optimal solution
solution = q.evaluate(result.best.values)
print(f"solution = {solution}")
The array of decision variables indicates that if there is 11 in the jjth column of the iith row, the taxi jj will be assigned to customer ii. Thus, we can get the information about which taxi to match to which customer as follows:
customers = np.arange(N, dtype=int)
taxies = (solution @ np.arange(N)).astype(int)
matches = list(zip(customers, taxies))
matches
Finally, we visualize the obtained data of matching customers and taxis.
def plot_matching(loc_customers, loc_taxies, matches):
markersize = 100
fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(10, 10))
ax.set_xlabel("x")
ax.set_ylabel("y")
ax.scatter(
loc_customers[:, 0],
loc_customers[:, 1],
label="Customers",
marker="o",
color="red",
s=markersize,
)
ax.scatter(
loc_taxies[:, 0],
loc_taxies[:, 1],
label="Taxies",
marker="^",
color="blue",
s=markersize,
)
for i, j in matches:
xc, yc = loc_customers[i]
xt, yt = loc_taxies[j]
plt.plot([xc, xt], [yc, yt], color="green", linestyle="--")
plt.legend(loc="upper right")
plt.show()
plot_matching(loc_customers=loc_customers, loc_taxies=loc_taxies, matches=matches)
The Case Where the Number of Customers is Less Than the Number of Taxis¶
In this section, we consider the taxi matching problem when the number of customers is smaller than the number of taxis. In this case, we need to formulate constraints that take into account both the case where the number of customers assigned to each taxi is zero and the case where the number of customers assigned to each taxi is one. Such constraints can be formulated using inequality constraints.
Given NcNc customers and NtNt taxis (Nc<NtNc<Nt) and their coordinates, let dijdij be the distance between customer ii and taxi jj as before.
Objective Function¶
The objective function is the same as before, but we consider that NcNc and NtNt are different values.
Nc−1∑i=0Nt−1∑j=0dijqijNc−1∑i=0Nt−1∑j=0dijqij
Constraint¶
Since there are more taxis than customers, every customer can be matched with one taxi. Therefore, for customer ii, the following holds. Nt−1∑j=0qij=1Nt−1∑j=0qij=1
On the other hand, for a taxi, there may be no customers at all. Therefore, we impose a constraint by inequality, taking into account both the cases where the number of customers is zero and the case where the number of customers is one. The following holds for taxi jj. Nc−1∑i=0qij≤1Nc−1∑i=0qij≤1
import numpy as np
from amplify import VariableGenerator, sum, less_equal, one_hot, FixstarsClient, solve
num_customers = 5 # Number of customers
num_taxies = 8 # Number of taxis
# Generate customers' coordinates, taxis' coordinates, and distance matrix between customers and taxis
loc_customers, loc_taxies, distances = gen_random_locations(num_customers, num_taxies)
# Create a QUBO variable array
gen = VariableGenerator()
q = gen.array("Binary", shape=(num_customers, num_taxies))
# Objective function
cost = (distances * q).sum()
############################################################################################
# Constraint
# Use equal_to for an equality constraint, less_equal for an inequality constraint
############################################################################################
customer_has_one_taxi = one_hot(q, axis=1)
taxi_has_one_or_less_customer = less_equal(q, 1, axis=0)
constraints = customer_has_one_taxi + taxi_has_one_or_less_customer
############################################################################################
# Construct a logical model by adding the objective function and constraint objects
constraints *= np.amax(distances) # type: ignore
model = cost + constraints
# Set up the client
client = FixstarsClient()
client.parameters.timeout = timedelta(milliseconds=1000) # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
# solve a problem
result = solve(model, client)
# If result is empty, the constraint condition is not satisfied.
if len(result) == 0:
raise RuntimeError("Given constraint conditions are not satisfied")
solution = q.evaluate(result.best.values)
customers = np.arange(num_customers, dtype=int)
taxies = (solution @ np.arange(num_taxies)).astype(int)
matches = list(zip(customers, taxies)) # Index of customers and taxis to be matched
# Plotting the matching of customers and taxis
plot_matching(loc_customers=loc_customers, loc_taxies=loc_taxies, matches=matches)