The Traveling Salesman Problem 2: 2-opt Removal of Intersections

strategy

number of points

4

5

6

7

8

9

10

11

12

13

14

15

other example

The traveling salesman problem (TSP) is the most famous combinatorial optimization problem. Its task is to find a tour through a set of vertices in the plane with the shortest possible total length. This Demonstration explores a method that helps in attaining the optimal minimum. It is based on the removal of intersections in a path to decrease its length, relying on the following fact: given

n

points on the plane, no three of which are collinear, there exists a closed path with no self-intersections having those points as vertices of minimal length. This method is called 2-opt and was proposed in 1958 as a way to solve the TSP. Although 2-opt does not give the optimum path, it often improves a given path. This Demonstration generates a random path and applies the method repeatedly to it, comparing the initial and final lengths obtained.