Traveling Salesman Problem

What am I looking at?

You are looking at the visualization of an algorithm to solve the Traveling Salesman Problem (TSP).

What is the Traveling Salesman Problem (TSP)?

Given a collection of cities, the TSP is a problem where a salesman has to visit each city exactly once - and to return to its starting point - by traveling the shortest distance.

The TSP naturally arises as a subproblem in many transportation and logistics applications. You can even use it to catch all the pokemons in your area as quickly as possible.

In the image above, the black circles represent the cities and the empty circles linked by the red edges form an elastic. The elastic is the visualization of the Elastic Net algorithm.

What is the Elastic Net algorithm?

The Elastic Net algorithm is a heuristic to solve the TSP. It finds a tour that has a short distance, but not necessary the shortest tour.

The Elastic Net algorithm is an iterative method where an elastic is gradually stretched until it passes sufficiently near each city to define a tour. During that process two forces apply: one for minimizing the distance between the cities and the points on the elastic (alpha) and the other one for minimizing the length of the elastic (beta). These forces are gradually adjusted as the procedure evolves. (Potvin, 1992)

You can control these two forces (alpha and beta) by using the corresponding sliders above.

The algorithm is described in this paper.

Is the Elastic Net algorithm the best method to solve the TSP?

Absolutely not. I chose it because it is simple to code and easy to visualize. Concorde is the best solver.

Where is the source code?

https://github.com/larose/tsp