Does this TSP solution work?

The traveling salesman problem

Find a round trip / "tour" of as short a length as possible, which visits each of n given cities exactly once and returns to the starting point. In the examples below (n points / "nodes" in the [0.1] x [0.1] square, new every day!) Only one point is added, but the best tour usually changes significantly. Try to find the best tour yourself by clicking the nodes one after the other!

Upload your own problem

"Click" rules:

  • Only nodes can be marked by clicking (highlighted in red), a second click removes the marking.
  • If a second node is marked for a marked node with no connection or a connection / "edge", this inserts an edge between the two; the second node remains selected.
  • If a marked node already has two edges, only one of the two "neighboring" nodes can be marked; that marks the edge.
  • A marked edge can be deleted using a button.
  • If an edge is marked and a further node is marked for this purpose, this is inserted / relocated between the two nodes of the edge.

To the math of the problem

The Traveling-Salesman Problem (TSP for short) is called the round trip problem or the traveling salesman problem and is one of the classic combinatorial optimization problems. It occurs both directly in this form and as a partial problem in many practical applications (everything that has to do with sequence-dependent transition times / lengths / costs: route planning for delivery services, sequence planning in production, coloring sequences in the automotive industry, processing sequences of spot welds in robotics, etc.). From the point of view of complexity theory, it belongs to the class of NP-complete problems, i.e. one can easily check solutions for their correctness, but presumably there is no algorithm that demonstrably always finds the best solution in a "short" time. On the basis of this problem, a large number of algorithmic approaches to handling combinatorial optimization tasks were developed and tested. The spectrum ranges from pure random searches through approximation algorithms to the exact solution of huge tasks. The latter are based on the formulation and solution of so-called linear relaxations. This can be imagined as high-dimensional polyhedra, through which the possible solutions are encompassed as closely as possible. Using these polyhedra, one can now efficiently determine the optimal solution with regard to a linear objective function (here the sum of the edge lengths) with linear optimization algorithms. In order to find the exact solution, you have to combine this with rounding methods and systematic search techniques (branch-and-bound). Please refer to the very nice website for the currently best solution algorithm Concorde.

The latest work at our professorship on this topic deals with square cost structures in which the effort no longer depends on two cities in direct succession, but now on three cities in a row. This also makes it possible to search for good tours in the event that acute angles are considered unfavorable. The latter is important in robotics applications, for example.