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 $N$ customers and the same number of $N$ taxis. Suppose that we are given the coordinates $(c_{i,x}, c_{i,y})$ of the customers and $(t_{j,x}, t_{j,y})$ of the taxis with indices $i, j = 0, 1, \cdots, N -1$. From these coordinates, let the distance between customer $i$ and taxi $j$ be the following:

$$ d_{ij} = \sqrt{(c_{i,x} - t_{j,x})^2 + (c_{i,y} - t_{j,y})^2} $$

Decision Variable¶

The relation between customer $i$ and taxi $j$ can be divided into the following two patterns:

• Customer $i$ is assigned a taxi $j$
• Taxi $j$ is not assigned to customer $i$

We use the binary variable $q_{ij}$ to represent these two states.

• When taxi $j$ is assigned to customer $i$, $q_{ij} = 1$
• When no taxi $j$ is assigned to customer $i$, $q_{ij} = 0$

Customer \ Taxi	$0$	$1$	...	$N-1$
$0$	$q_{0,0}$	$q_{0,1}$	...	$q_{0,N-1}$
$1$	$q_{1,0}$	$q_{1,1}$	...	$q_{1,N-1}$
$\vdots$	$\vdots$	$\vdots$	...	$\vdots$
$N -1$	$q_{N-1,0}$	$q_{N-1,1}$	...	$q_{N-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 $q_{ij}$ means that customer $i$ and taxi $j$ are matched when $1$, we only add up the distances that result in $q_{ij} = 1$.

$$ \sum_{i, j=0}^{N-1}d_{ij}q_{ij} $$

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 $i$.

$$ \sum_{j=0}^{N -1}q_{ij} = 1 $$

In addition, since one taxi is always assigned to one customer, we also need the following constraint for taxi $j$:

$$ \sum_{i=0}^{N -1}q_{ij} = 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.

For visualization purposes, we also create a function that, given the coordinates of a customer and a taxi, plot those coordinates.

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.

Building a Binary Polynomial Model¶

Next, we define the QUBO variables that we will need. Since we want to have $N$ taxis for each $N$ customer, we define the QUBO variable as a two-dimensional array of $N\times N$ as follows:

Using these QUBO variables, the objective function is obtained as follows:

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.

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 $d_{ij}$, and we will not go into the discussion of how strong it should be.

Running the Ising Machine¶

Set the client of the Ising machine to FixstarsClient, and also create a solver to solve the problem as follows:

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.

The array of decision variables indicates that if there is $1$ in the $j$th column of the $i$th row, the taxi $j$ will be assigned to customer $i$. Thus, we can get the information about which taxi to match to which customer as follows:

Finally, we visualize the obtained data of matching customers and taxis.

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 $N_c$ customers and $N_t$ taxis ($N_c < N_t$) and their coordinates, let $d_{ij}$ be the distance between customer $i$ and taxi $j$ as before.

Objective Function¶

The objective function is the same as before, but we consider that $N_c$ and $N_t$ are different values.

$$ \sum_{i=0}^{N_c-1}\sum_{j=0}^{N_t - 1}d_{ij}q_{ij} $$

Constraint¶

Since there are more taxis than customers, every customer can be matched with one taxi. Therefore, for customer $i$, the following holds. $$ \sum_{j=0}^{N_{\rm t}-1}q_{ij} = 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 $j$. $$ \sum_{i=0}^{N_{\rm c} -1}q_{ij} \le 1 $$