Travelling Salesman Problem¶
This section describes how to solve the traveling salesman problem using Amplify.
The Traveling Salesman
Problem is
a combinatorial optimization problem to find the shortest route that visits all cities exactly once,
given
a set of cities and the distances between each pair of cities.
In order to use the Ising machine, the combinations of paths need to be represented by polynomials
with
respect to binary or Ising variables.
Every combination of paths can be represented by a table of variables that shows which city is visited
in
which order.
For example, the following table for four cities will represent the route $A \rightarrow C \rightarrow
B
\rightarrow D \rightarrow A$.
| turn |
A |
B |
C |
D |
| 1st |
1 |
0 |
0 |
0 |
| 2nd |
0 |
0 |
1 |
0 |
| 3rd |
0 |
1 |
0 |
0 |
| 4th |
0 |
0 |
0 |
1 |
| 5th |
0 |
0 |
0 |
1 |
We assign binary variables $\left\{0, 1\right\}$ to each element of the table.
We interpret a path by following the cities where $1$ is assigned in the right order from 1st to 4th.
That is, for a traveling salesman problem in $N$ cities, it suffices to have $N^2$ variables.
Let $q_{n,i}$ be each variable in the above table, using the route order $n$ and the city index $i$.
Then
the total distance of travel routes are represented as follows;
$$
\sum_{n=0}^{N-1}{\sum_{i=0}^{N-1}{\sum_{j=0}^{N-1}{ d_{ij} q_{n, i} q_{n+1, j} }}}
$$
where $d_{ij}$ is the distance traveled between cities labeled by $i$ and $j$. Since $d_{ij} q_{n, i}
q_{n+1, j}$ adds $d_{ij}$ when the both variables equal $1$, the above expression is equal to the sum
of
total distance traveled. Note that the indices start at $0$ for convenience in later programmatic
coding.
However, this is not a sufficient formulation. This is because the above variable table does not take
into account the constraints of "visiting all cities" and "visiting only one city at a time". As an
extreme example, the combination of not moving from the first city is allowed. We thus need to impose
the
following constraints on all the rows and columns of the variables table.
$$
\begin{align*}
\sum_{i=0}^{N-1}{q_{n, i}} = 1 &, \; & n \in \left\{0, 1, \cdots, N - 1 \right\} \\
\sum_{n=0}^{N-1}{q_{n, i}} = 1 &, \; & i \in \left\{0, 1, \cdots, N - 1 \right\}
\end{align*}
$$
These imply the constraints that $1$ can appear only once in each row and each column of the variable
table.
Summarizing the above, it turns out that we need to find the minimum value of the following
polynomial:
-
Objective function
$$
\sum_{n=0}^{N-1}{\sum_{i=0}^{N-1}{\sum_{j=0}^{N-1}{ d_{ij} q_{n, i} q_{n+1, j} }}}
$$
-
Constraints
$$
\begin{align*}
\sum_{i=0}^{N-1}{q_{n, i}} = 1 &, \; & n \in \left\{0, 1, \cdots, N - 1 \right\} \\
\sum_{n=0}^{N-1}{q_{n, i}} = 1 &, \; & i \in \left\{0, 1, \cdots, N - 1 \right\}
\end{align*}
$$
Creating a problem¶
First, we create locations of the cities and the distances between each city, which will be the input
for
the Traveling Salesman Problem. Here we use numpy to place the cities at random locations
on
a two-dimensional plane and generating the distance matrix.
In this tutorial, the number of cities created will be 32.
