Solution to Exercise 3: Finding the Best Way to Travel

This exercise is a modified version of the famous traveling salesman problem. Let’s solve it.

Exercise 3

The matrix $G$ tells us the time required to go from one city to another. As the salesman has to visit all the cities, we need to figure out how to sort them in a way that minimizes the total time spent on travel. We need to keep in mind that the salesman wants to finish in the same city he starts in.

A solution is an arrangement of the $N$ cities. As the cities are numbered from $1$ to $N$, we say this arrangement is a permutation. Examples of permutation are:

• 1, 2, 3, 4, 5
• 5, 2, 4, 1, 3
• 4, 1, 3, 5, 2

In these examples, $N = 5$. In other words, a permutation of $N$ elements is any way of arranging them.

We’re looking for the permutation of the cities that minimizes the total travel time. In the computation of the total time, we need to keep in mind that the salesman will finish traveling from the last city in the permutation to the first one.

We’ll have the exact_solution again to compare our results.

We’ll use the following operations:

• mutation: We swap two elements in the permutation.
• crossover: We get the first cities from one permutation and the remaining from the other.
• score: We get the inverse of the total time.