TSP Software 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Theorie) |
(→Implemented heuristic) |
||
(17 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
− | == | + | == Theory== |
The ''''T'''raveling '''S'''alesman '''P'''roblem' (or 'travelling salesperson problem') is an [http://en.wikipedia.org/wiki/NP-hard 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. | The ''''T'''raveling '''S'''alesman '''P'''roblem' (or 'travelling salesperson problem') is an [http://en.wikipedia.org/wiki/NP-hard 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. | ||
Zeile 16: | Zeile 16: | ||
Following this formula the possible solutions raise like this: | Following this formula the possible solutions raise like this: | ||
− | nodes (cities): possible routes: | + | nodes (cities): possible routes: runtime (3GHz Single Core): |
3 2 0,063 sec | 3 2 0,063 sec | ||
4 6 0,073 sec | 4 6 0,073 sec | ||
Zeile 26: | Zeile 26: | ||
10 262.880 0,265 sec | 10 262.880 0,265 sec | ||
11 3.628.800 1,279 sec | 11 3.628.800 1,279 sec | ||
− | 12 39.916.800 12,293 sec (ca. | + | 12 39.916.800 12,293 sec (ca. runtime of n=11 x 12) |
− | 13 479.001.600 143,474 sec (ca. | + | 13 479.001.600 143,474 sec (ca. runtime of n=12 x 13) |
− | 14 6.227.020.800 29,987 min (ca. | + | 14 6.227.020.800 29,987 min (ca. runtime of n=13 x 14) |
− | 15 87.178.291.200 ~ 7,400 h (ca. | + | 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. | + | 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. | + | 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. | + | 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. | + | 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. | + | 20 121.645.100.408.832.000 ~ 1,600 ty (ca. runtime of n=19 x 20) |
== Calculation of a route == | == Calculation of a route == | ||
+ | |||
'''How does the computer calculate the distance?''' | '''How does the computer calculate the distance?''' | ||
Zeile 46: | Zeile 47: | ||
<math>\sqrt{(ax - bx)^2 + (ay - by)^2}</math> | <math>\sqrt{(ax - bx)^2 + (ay - by)^2}</math> | ||
− | |||
− | ''' | + | '''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: | |
− | + | ||
− | + | <math>\sum_{i=0}^{n-1} \sqrt{(a_{i}x - b_{i}x)^2 + (a_{i}y - b_{i}y)^2}</math> | |
− | |||
+ | '''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. | ||
− | |||
− | + | [[Datei:Bruteforce.gif]] | |
+ | == Solution methods == | ||
− | + | To solve the TSP there a plenty of algorithms and heuristic known, which some of are done in OR: | |
− | |||
− | |||
− | |||
− | + | '''Exact algorithms''' | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | ''' | + | |
- [https://bisor.wiwi.uni-kl.de/orwiki/Integer_linear_optimization:_Branch_%26_Bound_1 Branch and Bound] ([http://de.wikipedia.org/wiki/Branch-and-Cut Branch and Cut]) | - [https://bisor.wiwi.uni-kl.de/orwiki/Integer_linear_optimization:_Branch_%26_Bound_1 Branch and Bound] ([http://de.wikipedia.org/wiki/Branch-and-Cut Branch and Cut]) | ||
− | ''' | + | '''Heuristic and approximation algorithms''' |
- [https://bisor.wiwi.uni-kl.de/orwiki/Heuristics:_Minimal_Spanning_Tree_1 Minimal Spanning Tree] | - [https://bisor.wiwi.uni-kl.de/orwiki/Heuristics:_Minimal_Spanning_Tree_1 Minimal Spanning Tree] | ||
Zeile 90: | Zeile 82: | ||
- [http://de.wikipedia.org/wiki/Nearest-Insertion-Heuristik Nearest Insertion Heuristik] | - [http://de.wikipedia.org/wiki/Nearest-Insertion-Heuristik 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 -> B -> C-> A | ||
Zeile 101: | Zeile 91: | ||
− | + | 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 | 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 -> C -> D -> A | ||
Zeile 116: | Zeile 106: | ||
− | + | 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 -> D -> E -> A |
− | A->B -> C -> E -> D -> A | + | A-> B -> C -> E -> D -> A |
− | A->B -> E-> C -> D -> A | + | A-> B -> E -> C -> D -> A |
− | A->E -> B-> 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 <math> \sum_{i=0}^{n-1} i </math> steps instead of <math> (n-1)!</math> | ||
− | + | The results are often the same, like in this example, even if it just takes a fractional part of the time: | |
− | + | '''13 nodes:''' | |
− | |||
[[Datei:13 Staedte.jpg]] | [[Datei:13 Staedte.jpg]] | ||
− | '''60 | + | |
+ | '''60 nodes:''' | ||
[[Datei:100 Staedte.jpg]] | [[Datei:100 Staedte.jpg]] |
Aktuelle Version vom 30. Juni 2013, 15:25 Uhr
Inhaltsverzeichnis
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
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