Travelling salesman problem¶
2022 Problem solving
Definition¶
Either a seller must visit N cities with the minium trip distance.
\[
\sum_{i=1}^{n} \sum_{j \neq i, j=1}^{n} c_{ij}x_{ij}
\]
Instances¶
Instances are available TSPLIB95 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
Example¶
We interest of the instance eil76. The number of node is 76 in euclidean plane. This is case, we use a stockastic algorithm of local search: the first-improvement with a swap operator of two items.
The figure 1 represented the optimisation progression.
