TSP Software 1: Unterschied zwischen den Versionen

Aktuelle Version vom 30. Juni 2013, 15:25 Uhr

Theory

The 'Traveling Salesman Problem' (or 'travelling salesperson problem') is an NP-hard problem in combinatorial optimization. Its exercise is to find the optimal route for the visit of nodes. The criterion, which is to minimize, can be different; e.g. the time it takes, the costs, the distance or a mix of these.

Furthermore there are diffrent kind of restrictions for the TSP: To make the example as simple as possible we minimize the distance and use coordinate system, so every point can be related to every other point.

Example:

To plan a road trip with 4 different cities (A, B, C, D) there are Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (n - 1)!

possible routes: In this case Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (4 - 1)! = 6

.

Following this formula the possible solutions raise like this:

nodes (cities):          possible routes:        runtime (3GHz Single Core):
      3                         2                   0,063 sec
      4                         6                   0,073 sec
      5                        24                   0,078 sec
      6                       120                   0,109 sec
      7                       720                   0,125 sec
      8                     5.040                   0,156 sec
      9                    4.0320                   0,187 sec
     10                   262.880                   0,265 sec
     11                 3.628.800                   1,279 sec 
     12                39.916.800                  12,293 sec (ca. runtime of n=11 x 12)
     13               479.001.600                 143,474 sec (ca. runtime of n=12 x 13)
     14             6.227.020.800                  29,987 min (ca. runtime of n=13 x 14)
     15            87.178.291.200                ~  7,400  h  (ca. runtime of n=14 x 15)
     16         1.307.674.368.000                ~  5,000  d  (ca. runtime of n=15 x 16)
     17        20.922.789.888.000                ~ 85,000  d  (ca. runtime of n=16 x 17)
     18       355.687.428.096.000                ~  4,200  y  (ca. runtime of n=17 x 18)
     19     6.402.373.705.728.000                ~ 80,000  y  (ca. runtime of n=18 x 19)
     20   121.645.100.408.832.000                ~  1,600 ty  (ca. runtime of n=19 x 20)

Calculation of a route

How does the computer calculate the distance?

First of all u have to know how to measure the distance of 2 points in a coordinate system. Therefor we use the Pythagoras' theorem:

Take 2 points A(ax|ay), B (bx|by). The distance of those points is: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sqrt{(ax - bx)^2 + (ay - by)^2}

How does the computer calculate a route?

The computer measures the distance of every point to his successor and adds the results to get the distance of the whole route:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{n-1} \sqrt{(a_{i}x - b_{i}x)^2 + (a_{i}y - b_{i}y)^2}

How does the computer calculate the fastest route (permutations)?

He calculates the route for every possible permutation and saves the actual shortest distance. If a new route is shorter than the old one, he saves the new one. As soon as all possible permutations are computated, there is only the shortest route saved - this will be printed.

Solution methods

To solve the TSP there a plenty of algorithms and heuristic known, which some of are done in OR:

Exact algorithms

- Branch and Bound (Branch and Cut)

Heuristic and approximation algorithms

- Minimal Spanning Tree

- Nearest Neighbor

- Nearest Insertion Heuristik

Implemented heuristic

Take 3 points in a coordinate system A, B, C with random coordinates, where A is the start and end node. To build a circuit there a 2 possibilities ((3-1)! = 2! = 2):

A -> B -> C-> A

A -> C -> B -> A

Both circuits have the same distance, because only the directions is changing. So we know, it doesn’t matter how we connect 3 points, it is always the optimal route. That’s where our heuristic starts at. You take 3 random points:

A -> B -> C -> A

Now another random point joins them, the computer checks on which position between the original points D has to be, so the route still is optimal:

A->B -> C -> D -> A

A->B -> D -> C -> A

A->D -> B -> C -> A

For 4 points the heuristic needs to calculate 3 possibilities instead of 6. This difference is rather small but the more points u got the more the difference gets (s. table).

We take A->B -> C -> D -> A as an optimal solution.

If now another random Point E needs to be added, we take the optimal route and check, on which place E has to be added:

A-> B -> C -> D -> E -> A

A-> B -> C -> E -> D -> A

A-> B -> E -> C -> D -> A

A-> E -> B -> C -> D -> A

Again u take the best combination to add more and more points.

This way the computer needs only Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{n-1} i

steps instead of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):   (n-1)!

The results are often the same, like in this example, even if it just takes a fractional part of the time:

13 nodes:

60 nodes:

Quellen

- Wikipedia Eintrag zum TSP ausführliche Informationen zum Traveling Salesman Problem

- Algorithmus der Woche TSP oder die optimale Tour für den Nikolaus

- Online Touren-Planer kostenloser TSP-Solver zur Routenoptimierung