Ride sharing¶
The problem we are dealing with in this tutorial is called collective ridesharing.
Collective ridesharing refers to a form of ridesharing in which multiple users gather at several
large
parking lots and ride in the same car to the same destination（there is another type of ridesharing
called
traveling ridesharing, but it will not be discussed here).
Here, given multiple people with the same destination and available cars, we will find the allocation
of
people and cars such that the travel distance to the parking lot for each person and the number of
cars to
be used are as small as possible.
We formulate the problem as a model that can be run on an Ising machine, and find the allocation as a
minimization problem.
First, we define the constants and variables necessary for the formulation.
Constant¶
- $N$：Number of rideshare users
- $M$：Number of available cars
- $C$：Number of available seats per car
- $D$：Matrix such that $ik$component$(d_{ik})$ is the distance between user $i$ and car $k$
Variables¶
- $q_{ik}\in\{0,1\}\quad(i\in\{1,\dots,N\}, k\in\{1,\dots,M\})$
Binary variables representing whether or not person $i$ rides in car $k$ ($q_{ik}=1\Leftrightarrow$
person $i$ rides in car $k$)
- $y_{lk}\in\{0,1\}\quad(l\in\{0,\dots,C\},k\in\{1,\dots,M\})$
Binary variables that satisfy $\sum_ly_{lk}=\sum_iq_{ik}$ (used to express constraints on the number
of
passengers)
Then, we consider the constraints where the variables must satisfy.
Constraints¶
-
Each person always rides in one car.
$\sum_{k=1}^Mq_{ik}=1(\forall i\in\{1,\dots,N\})$
-
The actual number of passengers does not exceed the number of available seats.
$\sum_{i=1}^Nq_{ik}\leq C(\forall k\in\{1,\dots,M\})$
Finally, we will consider an objective function that satisfies the followings:
- Users use a car that is as close as possible to their location.
- Users travel with as few cars as possible.
Objective function¶
- Users should avoid unnecessary travel as much as possible.
$\text{minimize}\quad\sum_{i,k}d_{ik}q_{ik}$
- We want to minimize the number of cars used as much as possible$\space\Rightarrow\space$Maximize
the
number of passengers per car.
$\text{maximize}\quad\sum_{k}\left(\sum_i\frac{q_{ik}}{C}\right)^2$
Considering these two items, the following objective function can be set.
$$\sum_{i,k}d_{ik}q_{ik}-\alpha\sum_{k}\left(\sum_i\frac{q_{ik}}{C}\right)^2$$
Note¶
Let $\alpha>0$ be the parameter that determines how much importance is placed on the number of
cars in
use.
The closer the value of $\alpha$ is to $0$, the more the optimization places emphasis on minimizing
the
distances traveled by users. The greater the value of $\alpha$ is, the more the optimization places
emphasis on minimizing the number of cars used.
If $\alpha$ is large, the term regarding the distance traveled will be less important. The
visualization
result thus will be cleaner if $\alpha$ is small.
Summary¶
From the above, the collective ridesharing problem can be formulated as the following Ising model.
$$
\begin{align}
H&=H_{\rm cost}+H_{\rm constraint}\\
H_{\rm cost}&= \sum_{i,k}d_{ik}q_{ik}-\alpha\sum_{k}\left(\sum_i\frac{q_{ik}}{C}\right)^2\\
H_{\rm constraint} &=
k_1\sum_{i=1}^N\left(\sum_{k=1}^Mq_{ik}-1\right)^2+k_2\sum_{k=1}^M\left(\sum_{i=1}^Nq_{ik}-\sum_{l=0}^Cy_{lk}\right)^2
\end{align}
$$
$k_1, k_2$ are constants that determine the strength of the constraints.
In order to ensure the feasibility of the solution, the size of the constant must be set so that the
objective function is not improved by violating the constraint.
In the present case, at least the following inequality should hold. The details of the derivation are
omitted.
$$
\begin{align}
k_1&>{\rm max}\left(− {\rm min\space}d_{ik}+
\frac{2c − 1}{c^2}\alpha,\space
{\rm max\space}d_{ik}−\frac{2c − 1}{c^2}\alpha
\right)\\
k_2&>\frac{2c − 1}{c^2}\alpha
\end{align}
$$
