Traveling Salesman Problem - THI · PDF filereise die – entsprechend den Möglichkeiten der Heuristik – so kurz wie möglich und dabei so lang wie nötig ist

Leibniz Universität HannoverInsitut für Theoretische Informatik

Traveling Salesman ProblemVergleich von Heuristiken zur Lösung des Problems des

Handlungsreisenden

Eine Bachelorarbeit von

Florian Nöhring

18. August 2007

Prof. Dr. Heribert VollmerErstprüfer

Prof. Dr. Udo LipeckZweitprüfer

Erklärung

Hiermit versichere ich, dass ich die vorliegende Arbeit selbstständig verfasst und dabeikeine anderen als die aufgeführten Quellen und Hilfsmittel verwendet habe.

Hannover, den 18. August 2007

Inhaltsverzeichnis

1 Einführung 71.1 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Motivation dieser Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3 Begriffe, Konventionen und Definitionen . . . . . . . . . . . . . . . . . . . 9

2 Instanzen 112.1 TSPLIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Heuristiken 133.1 Einfache Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1.1 Nearest Neighbor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1.2 Random Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Ausgefeiltere Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2.1 Minimum Spanning Tree-Heuristik . . . . . . . . . . . . . . . . . . 173.2.2 Die Heuristik von Christofides . . . . . . . . . . . . . . . . . . . . . 19

3.3 Sonstige Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3.1 Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3.2 Genetischer Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Testdurchführung 274.1 Testsystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.2 Laufzeitanalyse und Testergebnisse . . . . . . . . . . . . . . . . . . . . . . 27

5 Bewertung der Ergebnisse 43

Literaturverzeichnis 45

5

1 Einführung

1.1 Traveling Salesman Problem

Das Problem des Handlungsreisenden äußert sich in dem Wunsch für eine gegebene

Menge von Städten eine Rundreise zu finden, die nacheinander zu jeder Stadt genau

einmal führt und schließlich zur Ausgangsstadt zurückkehrt und dabei eine möglichst

kurze Strecke zurücklegt.

Das Problem ist dabei nicht auf Städte beschränkt, sondern lässt sich auch auf ähnliche

Situationen übertragen und findet damit Relevanz nicht nur bei einem Paketdienstleister

oder Vertreter, der seine Kunden ohne Umwege besuchen möchte, sondern auch in der

Fertigungsindustrie, etwa bei einem Bestückungs- oder Schweißroboter, für den die Zeit

minimiert werden soll, die er benötigt um zu den Steckplätzen oder Schweißstellen zu

gelangen, damit der Fertigungsprozess nicht unnötig verlangsamt wird.

Am Beispiel der Suche nach der kürzesten Rundreise durch die 16 Landeshauptstädte

Deutschlands wird deutlich wie schwierig es ist die kürzeste Rundreise zu finden. Ein

Mensch kann für solch eine kleine Menge von Städten noch sehr kurze und oft sogar

die kürzeste Rundreise durch scharfes Hinsehen erkennen, weil er bei einem Blick auf

die Karte die Lage der Orte im Ganzen erfassen kann und erkennt, dass die kürzeste

Rundreise beispielsweise nicht von Kiel über München, zurück nach Hamburg und an-

schließend über Stuttgart führt.

Der Mensch zerlegt das Problem intuitiv in kleinere Teile1 und erkennt, dass beispiels-

weise München–Stuttgart–Saarbrücken–Mainz–Wiesbaden–Düsseldorf oder auch

Hannover–Bremen–Hamburg–Kiel derart positioniert sind, dass sie mit größter Wahr-

scheinlichkeit in dieser Reihenfolge auch Teil der gesuchten Lösung sind. Diese Teillö-

sungen können dann zusammengesetzt werden.

1Dies folgt dem divide et impera-Paradigma, dt. teile und herrsche.

7

Kapitel 1. Einführung

Ein Computerprogramm sieht nicht das Gesamtbild und kann daher nicht dieselben

Schlüsse ziehen wie ein Mensch. Es muss ein anderer Lösungsweg gefunden werden.

Für nur 16 Städte existieren bereits mehr als 650 Mrd. verschiedene Rundreisen; zu viele

um alle auszuprobieren.

Das Problem des Handlungsreisenden (en.: Travelling Salesman Problem, amer.: Trave-

ling ∼; kurz MinTSP) gehört zu einer Klasse von Problemen genannt NPO. Es existiert

eine Variante von MinTSP, genannt TSP, bei der es sich um das zugehörige Entschei-

dungsproblem handelt.

Das Optimierungsproblem MinTSP

MinTSP = (I, Sol,m, goal) mit

• I = {〈(di,j)1≤i,j≤n〉 | n, di,j ∈ N}• Sol(D) ist die Menge aller Rundreisen in D, d. h. Sol(D) = Sn, die Gruppe der

Permutationen von n Elementen.

• m(D,π) ist die Länge Rundreise in π in D, d. h. m(D,π) =n−1∑i=1

dπ(i),π(i+1) +

dπ(n),π(1).

• goal = min.

aus [7], S. 31

Das Entscheidungsproblem TSP

TSP = {〈(di,j)1≤i,j≤n, B〉 | n, di,j , B ∈ N und es gibt π ∈ Sn mitn−1∑i=1

dπ(i),π(i+1) +

dπ(n),π(1) ≤ B}aus [7], S. 29

Beim Entscheidungsproblem wird neben der Menge von Städten noch eine Zahl B über-

geben, und es ist lediglich die Antwort auf die Frage gesucht, ob eine Rundreise durch

alle Städte existiert, die eine Strecke nicht länger als B zurückgelegt.

TSP ist ein klassisches NP-vollständiges Problem. Damit ist MinTSP NP-hart ([7], S. 33),

und es ist kein effizientes Verfahren bekannt um MinTSP zu lösen.

8

1.2. Motivation dieser Arbeit

1.2 Motivation dieser Arbeit

Weil für NP-harte Probleme keine effizienten Lösungsverfahren bekannt sind, ist es prak-

tisch unmöglich das Problem des Handlungsreisenden für eine große Menge von Städten

zu lösen.

Im Folgenden soll daher nicht mehr versucht werden die optimale Lösung, also die kür-

zeste Rundreise, zu finden, sondern mit Hilfe von verschiedenen Heuristiken eine Rund-

reise die – entsprechend den Möglichkeiten der Heuristik – so kurz wie möglich und

dabei so lang wie nötig ist.

Diese Arbeit stellt einen empirischen Vergleich an zwischen einigen Heuristiken, die für

das Problem des Handlungsreisenden effizient Näherungslösungen finden.

1.3 Begriffe, Konventionen und Definitionen

Instanz

Die hier vorgestellten Heuristiken und anderen Verfahren versuchen eine möglichst kur-

ze Rundreise für eine gegebene Menge von Städten zu bestimmen. Eine solche Einga-

bemenge, auf die eine Heuristik angewandt werden kann, wird als Probleminstanz oder

kurz Instanz bezeichnet. Die Dimension einer Instanz ist die Anzahl ihrer Städte.

Die Instanzen werden als Graphen modelliert, mit den Städten als Knoten und den Ent-

fernungen als Kantengewichte. Diese Gewichte werden auch als Kosten bezeichnet. Für

alle Graphen und damit auch für die zugrunde liegenden Instanzen gelten dabei einige

Einschränkungen. Sie sind einfach, vollständig und ungerichtet, also auch symmetrisch,

sowie metrisch, das heißt die Dreiecksungleichung2 ist erfüllt.

Formal ist eine Instanz mit n Städten entweder gegeben als

• eine Menge C = {c1, c2, . . . , cn} von Punkten mit Koordinaten, die die Städte re-

präsentieren und eine Funktion d : (i, j)→ N, die ∀ i, j ∈ {1, . . . , n} die Entfernung

zwischen ci und cj berechnet,

oder als2Die Distanz zwischen den Städten A und C kann niemals länger sein als der Umweg von A über eine

beliebige Stadt B nach C.

9

Kapitel 1. Einführung

• eine symmetrische (n × n)-Matrix A, bei der an Position Ai,j die Entfernung zwi-

schen den Städten i und j steht.

Rundreise

Eine Rundreise durch eine Instanz mit n Städten wird modelliert als Permutation

π =

(1 2 3 4 . . . n

p1 p2 p3 p4 . . . pn

), p1, . . . , pn ∈ {1, . . . , n}.

π(i) gibt dabei die Stadt an, die nach Stadt i besucht wird.

Als kürzere Darstellung dient die Zyklenschreibweise

π = ( q1 q2 q3 q4 . . . qn ), q1, . . . , qn ∈ {1, . . . , n},

bei der die Städte in der angegebenen Reihenfolge besucht werden.

Eine solche Rundreise, bei der jede Stadt genau einmal besucht wird, wird auch als

Lösung bezeichnet, auch wenn es sich dabei nicht um die gesuchte kürzeste Rundreise

handelt. Eine weitere Bezeichnung für eine Rundreise ist Tour.

Die Maßzahl einer Rundreise oder Lösung π ist ihre Gesamtlänge. Das ist

n∑i=1

d(i, π(i)

)bzw.

n∑i=1

Ai,π(i).

Performanz

Die Performanz einer Lösung, auch Güte genannt, gibt das Verhältnis von ihrer Maßzahl

zu der Maßzahl der optimalen Lösung an. ([5], S. 39)

10

2 Instanzen

Um Heuristiken effektiv vergleichen zu können, müssen Metriken gefunden werden, mit

deren Hilfe die Qualität eines Verfahrens objektiv beurteilt werden kann.

Hierfür eignen sich besonders die benötigte Zeit und die Performanz einer gefundenen

Tour. Später wird außerdem die Varianz der Güte ermittelter Lösungen eines Verfahrens

bei wiederholter Anwendung auf dieselbe Instanz von einiger Bedeutung sein.

Wegen der NP-Härte des Problems lässt sich für größere Instanzen in vertretbarer Zeit

effektiv keine optimale Lösung bestimmen. Deswegen können nicht eigens für die Mes-

sungen Testinstanzen zufällig erzeugt werden, und es muss auf Instanzen mit bekannten

Lösungen zurückgegriffen werden.

2.1 TSPLIB

Um die Heuristiken vergleichen zu können wird daher auf TSPLIB [1] zurückgegriffen.

Dies ist eine Sammlung von über 100 Probleminstanzen des symmetrischen Problems

des Handlungsreisenden unterschiedlicher Größe. Die kleinste Instanz burma14.tsp ver-

fügt über 14 Städte oder Knoten, die größte über 85.900 (pla85900.tsp).

Die Instanzen haben meist einen realitätsbezogenen Hintergrund. So finden sich in der

TSPLIB u. a. folgende Instanzen:

• 666 Städte rund um die Welt (gr666.tsp)• 16 und 22 Stationen auf der Irrfahrt des Odysseus (ulysses16.tsp undulysses22.tsp)• 127 Biergärten in Augsburg (bier127.tsp)

11

Kapitel 2. Instanzen

Die Instanzen können dabei im Wesentlichen in drei verschiedenen Formaten vorliegen.1

Punktmenge in der euklidischen Ebene Jede Stadt ist als kartesische Koordinate gege-

ben. Die Distanz zwischen zwei Städten muss nach Pythagoras berechnet werden.

Punktmenge geografischer Koordinaten aus Breiten- und Längengraden Die Distanz

zwischen zwei Punkten muss mittels aufwändiger trigonometrischer Funktionen

berechnet werden. Es gilt stets die direkte Luftlinie unabhängig etwaiger Hinder-

nisse.

Explizite Angabe aller Distanzen Die Distanzen liegen als obere oder untere Dreiecks-

oder als vollständige Adjazenzmatrix vor. Dadurch wird zwar keine Zeit zur Be-

rechnung benötigt, aufgrund der Repräsentation der Distanzen als 32 Bit-Ganz-

zahlen wird zur Speicherung der Dreiecksmatrix jedoch (n2−n)2 · 4 Byte Speicher-

platz benötigt, was bei großen Instanzen wie d18512.tsp (18.512 Städte in

Deutschland) bereits 650 MB und bei pla85900.tsp sogar über 13 GB Speicher-

bedarf bedeutet.

Abbildung 2.1: Schematische Darstellung der 16 Knoten aus ulysses16.tsp. In Wirk-lichkeit liegen die Punkte auf der gekrümmten Erdoberfläche. Die Pro-portionen der paarweisen Distanzen in dieser Abbildung stimmen dahernicht mit der Wirklichkeit überein.

1Es gibt außerdem noch die Möglichkeit Instanzen zu formulieren, bei denen die Distanz zwischen zweiKnoten auf spezielle Art berechnet oder gerundet werden muss, was hier jedoch von nur geringemInteresse ist.

12

3 Heuristiken

Anders als Algorithmen, die für ein bestehendes Problem garantiert eine Lösung finden,

falls es sie gibt, sind Heuristiken Verfahren, die meist einfacher durchzuführen sind und

eine Näherungslösung finden, die zwar nicht perfekt aber oft zufriedenstellend ist.

3.1 Einfache Heuristiken

Einfache Heuristiken stellen intuitive Lösungsansätze dar. Im Gegenzug bieten sie jedoch

keine Garantien bezüglich der Güte einer ermittelten Lösung.

3.1.1 Nearest Neighbor

Dies stellt die einfachste und intuitivste Heuristik dar. Ausgehend von einem beliebigen

Startknoten wird die Tour stets über denjenigen Knoten fortgesetzt, der dem zuletzt

besuchten am nächsten ist, bis alle Knoten einmal besucht wurden. Schließlich wird

zum Startknoten zurückgekehrt.

Die Schritte des Vorgehens im Einzelnen sind:

1. Setze beliebigen Knoten als Startknoten der Tour.2. Solange noch Knoten existieren, die noch nicht zur Tour hinzugefügt

wurden, wiederhole den folgenden Schritt.2.1 Bestimme den Knoten, der dem zuletzt hinzugefügten am nächsten

ist und noch nicht hinzugefügt wurde, und füge ihn als nächstenzur Tour hinzu.

3. Verbinde den ersten und letzten Knoten um eine Rundreise zu erhalten.

Hierbei ist zu beachten, dass je nach Wahl des Startknotens, das Verfahren stark abwei-

chende Ergebnisse liefern kann und die Güte der Lösung damit vom Zufall abhängt, weil

13

Kapitel 3. Heuristiken

sich nicht vorhersehen lässt, welcher Knoten als Startknoten gut oder schlecht geeignet

ist.

Bei der Instanz fri26.tsp sorgt dies beispielsweise dafür, dass bei Wahl des optimalen

Startknotens Knoten 12 eine Tour gefunden wird, deren Länge die der optimalen Tour

nur um 3 % übersteigt. Fällt die Wahl des Startknotens dagegen auf Knoten 23, so liefert

das Verfahren eine Lösung, die 37 % länger ist als die optimale.

Beispiel

2

7

4 5

8 9

3

6

1

Abbildung 3.1: Knoten 2 wird als nächstes besucht.

Im Beispiel in Abbildung 3.1 wird als nächstes die 2 und anschließend die 7 zur Tour

hinzugefügt werden. Bei einer optimalen Tour hingegen müssten zunächst die Knoten 3

und 9 besucht werden, da die Knoten 2 und 7 dann auf dem Rückweg zur 1 ohne großen

Umweg berücksichtigt werden könnten.

2

7

4 5

8 9

3

6

1

Abbildung 3.2: Mit Knoten 2 als Startknoten wird im Beispiel die optimale Tour gefun-den, weil diesmal die 2 nach der 5 nicht als Nachfolger in Frage kommt.

14

3.1. Einfache Heuristiken

Anhand des Beispiels wird deutlich, dass das Verfahren nicht vorausschaut um die Ge-

samtlänge möglichst gering zu halten, sondern in jedem Schritt lediglich die momenta-

nen Schrittkosten minimal hält. Algorithmen und Heuristiken, die nach diesem Muster

vorgehen werden auch als gierig bezeichnet.

Für das Verfahren ergibt sich insgesamt ein Laufzeit von O(n2), denn Schritt 2.1 wird

n-mal ausgeführt, und bei jeder dieser Iteration müssen O(n) Distanzen berechnet wer-

den.

Ausiello et al. haben (in [5]) gezeigt, dass für die Performanz von Nearest Neighbor die

obere Schranke 12(dlog ne+ 1) existiert.

3.1.2 Random Insertion

Auch bei Random Insertion handelt es sich um ein gieriges Verfahren, und es ähnelt auch

dem Vorgehen bei Nearest Neighbor. Hier werden jedoch nicht Knoten nacheinander an

den zuletzt besuchten angehängt, sondern so in eine vorhandene Teiltour eingefügt, dass

die geringstmögliche Verlängerung der Tour bewirkt wird.

Gestartet wird dabei nicht mit einem, sondern mit drei1 Knoten und einer Rundreise

durch eben diese drei.

Im Detail setzt sich das Verfahren aus diesen Schritten zusammen:

1. Wähle 3 Startknoten und bilde eine Rundreise durch diese.1.1 Diese erste Rundreise besteht aus 3 Toursegmenten, nämlich den

Kanten zwischen jeweils 2 der 3 Startknoten.2. Solange noch Knoten existieren, die noch nicht zur Tour hinzugefügt

wurden, wiederhole die folgenden Schritte.2.1 Wähle zufällig einen noch nicht hinzugefügten Knoten Z aus.2.2 Berechne die Distanzen von Z zu allen bisher eingefügten Knoten.2.3 Bestimme die zwei benachbarten Knoten P und Q der

unvollständigen Rundreise, so dass, wenn Z zwischen ihneneingefügt wird, die Rundreise minimal verlängert wird.

2.4 Füge Z zur Rundreise hinzu, indem die Strecke PQ durch PZ und ZQersetzt wird.

1Man könnte auch mit 2 Knoten und einer Rundreise durch diese 2 starten; natürlich nur, wenn die Instanzüberhaupt so viele Knoten enthält.

15


Für Random Insertion ergibt sich, wie für Nearest Neighbor, ebenfalls eine Laufzeit von

O(n2). Schritte 2.1 bis 2.4 werden n-mal ausgeführt, und in jeder Iteration müssen O(n)

Distanzen berechnet werden.

41

3

6

25

41

3

6

25

Abbildung 3.3: Knoten 6 wird als nächstes ausgewählt und findet seinen Platz zwischen2 und 3.

Bei Nearest Neighbor wird sichergestellt, dass die Distanz von jedem Knoten zu seinem

Nachfolgeknoten möglichst gering ist. Die Distanz zum Vorgänger dagegen bleibt unbe-

rücksichtigt. Für das letzte Toursegment gibt es dann keinerlei Wahlmöglichkeiten mehr;

es muss immer den ersten und letzten Knoten miteinander verbinden, und diese beiden

können unter Umständen sehr ungünstig liegen.

Random Insertion hingegen misst die Distanz zu Vorgänger und Nachfolger und wählt

den jeweils besten Kompromiss. Dadurch ist die Wahl nie so eingeschränkt wie bei Nea-

rest Neighbor, und es werden üblicherweise – nicht jedoch grundsätzlich – auch bessere

Ergebnisse erzielt.

Das Wort Random im Titel impliziert allerdings schon, dass das Verfahren bei wieder-

holter Anwendung verschiedene Ergebnisse liefern kann, also die Performanz der Lö-

sung nicht mehr nur von der Wahl der Startknoten (wie bei Nearest Neighbor) abhängt,

sondern auch bei exakt gleichen Startbedingungen unterschiedliche Ergebnisse liefern

kann. Wie sehr die Ergebnisse von wiederholten Verfahrensanwendungen voneinander

abweichen können wird im Abschnitt 4.2 auf Seite 31 untersucht.

16

3.2. Ausgefeiltere Heuristiken

3.2 Ausgefeiltere Heuristiken

Die hier vorgestellten Verfahren unterscheiden sich von den einfachen Heuristiken haupt-

sächlich dadurch, dass sie nicht gierig vorgehen, sondern einen minimalen Spannbaum

zu Hilfe nehmen um eine Vorauswahl der Kanten zu treffen.

Speziell handelt es sich hierbei um c-Approximationsalgorithmen. Das bedeutet, dass im

schlechtesten Fall noch immer eine Güte von c garantiert werden kann.

3.2.1 Minimum Spanning Tree-Heuristik

Die Idee bei der Minimum Spanning Tree-Heuristik (kurz MST-Heuristik, auch TreeTSP

bei Vollmer [7]) ist es, zunächst einen minimalen Spannbaum über der Knotenmenge zu

spannen. Die Reihenfolge der ermittelten Lösung ergibt sich dann daraus, den Spann-

baum entlangzulaufen und die Knoten in der Reihenfolge des Besuches zu notieren.

Wird dabei ein Knoten erneut besucht, wird er übersprungen.

Technisch kann das Verfahren auf die folgende Weise durchgeführt werden:

1. Konstruiere einen minimalen Spannbaum über der Knotenmenge.2. Überführe den dabei entstehenden Graphen in einen Multigraphen, indem

jede Kante dupliziert wird.3. Ausgehend von einem beliebigen Startknoten, finde eine Eulertour

durch den Multigraphen und füge die Knoten in der Reihenfolge desBesuches zur Lösung hinzu.

4. Streiche jedes wiederholte Auftreten eines Knotens aus der Lösung.

Der minimale Spannbaum eignet sich, um eine Vorauswahl der zu wählenden Kanten zu

treffen, weil er alle Knoten miteinander verbindet bei kleinstmöglichem Gesamtkanten-

gewicht.

Sofern jedoch Verzweigungen im minimalen Spannbaum vorkommen, kann die Lösung

nicht eindeutig aus der Eulertour bestimmt werden. Abbildung 3.4 zeigt den Multigra-

phen eines einfachen Spannbaumes. Die Eulertour führt 3-mal am Knoten 2 vorbei. Zwei

dieser Besuche müssen durch zusätzliche Kanten zwischen den Nachbarn überbrückt

werden. Welche dies sind schreibt die MST-Heuristik nicht vor.

17


15

3

4 2

6

15

3

4 2

6

Abbildung 3.4: Multigraph mit Eulertour und eine gültige Lösung. Beim Vorgehen nachder MST-Heuristik können bei Verzweigungen – wie hier – ungünstigeEntscheidungen getroffen werden.

Definition

„Eine Eulertour in einem Graphen [. . . ] ist ein Weg, der jede Kante des Graphen genau

einmal enhält und dessen Anfangs- und Endknoten identisch sind. Enthält ein Graph

eine Eulertour, so nennt man ihn eulersch.“ ([9], S. 72)

Die Laufzeit des Verfahrens ergibt sich anhand der einzelnen Schritte zu O(n2) bei Ver-

wendung des Algorithmus’ von Prim-Jarník zur Bestimmung des minimalen Spannbau-

mes.

Schritt Zeitbedarf1 O(n2)2 O(n)3 O(n)4 O(n)

Tabelle 3.1: Zeitbedarf der Schritte der MST-Heuristik

Satz: Die MST-Heuristik ist ein 2-Approximationsalgorithmus ([2], [7]).

Beweis (nach [7]): Das Gesamtgewicht des minimalen Spannbaumes WMST kann nicht

größer als die Länge der optimalen Rundreise Wopt. sein.

WMST ≤Wopt.

18


Wäre dies doch der Fall, könnte man von der optimalen Rundreise eine Kante entfernen

und erhielte wieder einen Spannbaum, der noch leichter als der minimale Spannbaum

wäre.

Weil in der Eulertour jede Kante des in Schritt 2 erzeugten Multigraphen genau einmal

benutzt wird, hat diese eine Gesamtlänge von 2 ·WMST.

WEuler ≤ 2 ·Wopt.

Aufgrund der Dreiecksungleichung ist die von der MST-Heuristik ermittelte Lösung nicht

länger als die Eulertour durch den Multigraphen. Damit gilt:

WLösung ≤ 2 ·Wopt. �

2

3

4

81

16

5

15

1413

126

7

10 9

11

Abbildung 3.5: Der minimale Spannbaum und eine von der MST-Heuristik ermittelteRundreise zu ulysses16.tsp. Diese Lösung hat eine Performanz von1,13 und liegt damit deutlich unter der oberen Schranke von 2.

3.2.2 Die Heuristik von Christofides

Die Heuristik von Christofides (auch Christofides’ Algorithmus genannt) baut auf der

MST-Heuristik auf. Sie verwendet ebenfalls einen minimalen Spannbaum um eine erste

Auswahl der für die Rundreise zu wählenden Kanten zu treffen.

19


Letztendlich wird auch hier die Rundreise ermittelt indem eine Eulertour durch einen

Multigraphen gesucht wird. Der Multigraph wird dabei jedoch nicht erzeugt indem jede

Kante des Spannbaumes dupliziert wird, sondern durch Bestimmen eines gewichtsmini-

malen perfekten Matchings auf der Menge der Knoten des Spannbaumes mit ungeradem

Grad und Hinzufügen jeder Kante dieses Matchings zum Spannbaum.

Definition

Ein Matching eines Graphen G = (V,E) ist eine Teilmenge M ⊆ E, so dass dieinzidenten Knoten aller Kanten aus M paarweise disjunkt sind, jeder Knoten aus V alsonur mit höchstens einer Kante aus M inzidiert.

M heißt perfekt, wenn zusätzlich gilt:

|M | = |V |2,

also wenn jeder Knoten aus V mit genau einer Kante aus M inzidiert.

Das Gesamtgewicht eines Matchings ist die Summe seiner Kantengewichte.

Ein gewichtsminimales perfektes Matching M eines Graphen G ist ein Matching, sodass kein anderes Matching M ′ von G existiert mit geringerem Gesamtgewicht als M .

[7], [9]

Durch dieses Vorgehen wird ein Multigraph erzeugt, in dem alle Knoten von geradem

Grad sind. Ein solcher Graph ist stets eulersch ([9], S. 73).

Die weitere Durchführung entspricht wieder der MST-Heuristik.

1. Konstruiere einen minimalen Spannbaum über der Knotenmenge.2. Bestimme ein gewichtsminimales perfektes Matching für die Menge der

Knoten des Spannbaumes, die von ungeradem Grad sind.3. Füge jede Kante des Matchings zum Spannbaum hinzu um einen

Multigraphen zu erhalten.4. Ausgehend von einem beliebigen Startknoten, finde eine Eulertour

durch den Multigraphen und füge die Knoten in der Reihenfolge desBesuches zur Lösung hinzu.

5. Streiche jedes wiederholte Auftreten eines Knotens aus der Lösung.

20


Schritt Zeitbedarf1 O(n2)2 s. u.3 O(n)4 O(n)5 O(n)

Tabelle 3.2: Zeitbedarf der Schritte der Heuristik von Christofides

Schritt 2 stellt den zeitkritischen Schritt dar. Die Berechnung eines gewichtsminimalen

perfekten Matchings ermöglicht der Algorithmus von Edmonds in Zeit O(n4). Außerdem

existieren Verbesserungen des Algorithmus’ u. a. von Gabow, die in Zeit O(n3) auskom-

men ([6], S. 2).

In dieser Arbeit wird zur Bestimmung eines gewichtsminimalen perfekten Matchings auf

eine Implementierung des Algorithmus’ von Edmonds von Michael Maguire und Luis

Goddyn ([3]) zurückgegriffen.

Alternativ dazu wird untersucht, wie eine Heuristik zur Bestimmung einer Näherungslö-

sung eines gewichtsminimalen perfekten Matchings Laufzeit und Performanz der Heu-

ristik von Christofides beeinflusst. Dazu wird ein Verfahren von Wattenhofer & Watten-

hofer ([10]) verwendet, das in Zeit O(n2 log n) ein perfektes Matching findet, das nicht

schwerer als (log n)-mal das gewichtsminimale Matching ist.

Die Laufzeit der Heuristik von Christofides ergibt sich damit zu O(n4) für die exakte und

O(n2 log n) für die approximierte Lösung.

2

3

4

8

1

16

5

15

14

1312

67

10 9

1111 Knoten des Spannbaumes mit ungera-

dem Grad (zu matchender Knoten)

Kante des Spannbaumes

Kante, die beim Matching bestimmt wurde

Abbildung 3.6: Der Multigraph zu ulysses16.tsp, der durch Hinzufügen des perfek-ten Matchings entsteht. Schematische Darstellung: die Proportionen derEntfernungen in der Darstellung stimmen nicht mit den echten überein.Vgl. Abbildungen 2.1 und 3.5.

21


Genau wie bei der MST-Heuristik ist auch nach Christofides die Auswertung des Mul-

tigraphen, also die Bestimmung der Eulertour nicht genau beschrieben. Gefordert ist

lediglich eine beliebige Eulertour.

1614

13

12 3

……68

52

904

406

913

449

1614 13

12 3

……

52 406

913

1614

1312 3

……

68 904

449

Abbildung 3.7: Zwei mögliche Teillösungen für den Multigraphen aus Abb. 3.6. (Ent-fernungen sind Kilometerangaben.)

Abbildung 3.7 zeigt einen Ausschnitt aus dem Multigraphen zu ulysses16.tsp. Die er-

mittelte Eulertour führt 2-mal an der 13 vorbei. Die rechts dargestellte Lösung der zwei

möglichen Alternativen ist die bessere, weil sie das geringere Gesamtgewicht der be-

troffenen Kanten hat. Mit dem Verfahren nach Christofides wird das jedoch nicht be-

rücksichtigt. Die Performanz hängt damit auch vom Zufall ab, weil bei der Anwendung

zufällig eine der Möglichkeiten gewählt wird.

Dieser Zufallsfaktor sorgt dafür, dass bei Verwendung des approximierten Matchings

nach Wattenhofer & Wattenhofer, bei dem gegenüber dem exakten Matching nach Ed-

monds ein Multigraph mit höherem Gesamtgewicht entsteht, trotzdem eine kürzere

Rundreise gefunden werden könnte. Ob dieser Umstand tatsächlich eintritt, wird in Ab-

schnitt 4.2 auf Seite 34 geklärt.

Unabhängig dieser Problematik und davon wie effizient eine Lösung anhand der Euler-

tour gewählt wird, ist die Performanz der ermittelten Lösung stets nicht größer als 1,5.

Satz: Die Heuristik von Christofides ist ein 32 -Approximationsalgorithmus.

Den Beweis dazu liefert Vollmer ([7], S. 38).

22

3.3. Sonstige Verfahren

3.3 Sonstige Verfahren

3.3.1 Brute Force

Dem Brute Force-Ansatz nachzugehen stellt die einfachste und naivste Vorgehensweise

dar. Es wird nacheinander jede mögliche Permutation der Knoten ausprobiert, wobei

garantiert die optimale Lösung gefunden wird.

Der Aufwand lässt sich reduzieren, indem ein beliebiger Startknoten festgelegt wird.

Dies ist möglich, da dennoch alle möglichen Touren untersucht werden. Ist beispielswei-

se (5 4 6 1 3 2) eine optimale Tour und wird Knoten 1 als Startknoten festgelegt, so wird

trotzdem die Tour (1 3 2 5 4 6) oder (1 6 4 5 2 3) gefunden. All diese drei Touren besu-

chen die Knoten in der gleichen oder genau umgekehrten Reihenfolge. Die ermittelten

Längen der drei Lösungen sind identisch.

Eine weitere Einsparung lässt sich vornehmen, wenn nicht jedesmal die gesamte Länge

einer Tour, sondern nur der in der Iteration geänderte Teil berechnet wird. Dies ent-

spricht einer Tiefensuche durch den Suchbaum, bei dem die Zwischendistanz an den

Verzweigungen gespeichert und nur die Distanz von jeder Verzweigung zum Blatt be-

rechnet werden muss.

Außerdem braucht nur jeweils eine der zwei möglichen Rundreisen pro Permutation

berechnet werden.

Durch diese Einsparungen müssen noch (n−1)!2 mögliche Touren berechnet werden. Der

Zeitbedarf wächst exponentiell an, und das Verfahren ist schon für kleine Instanzen nicht

praktikabel.

3.3.2 Genetischer Algorithmus

Genetische Algorithmen ([8], S. 157) sind Verfahren, die in der Lage sind eine Vielzahl

unterschiedlicher Probleme zu lösen, nicht nur das des Handlungsreisenden. Dazu ar-

beiten sie mit einer Menge von gültigen aber noch nicht zufriedenstellenden Lösungen.

In mehreren wiederholten Iterationen werden vorhandene Lösungen paarweise mitein-

ander kombiniert um neue, möglicherweise günstigere Lösungen zu erhalten.

Die Bezeichnung genetischer Algorithmus kommt von der Ähnlichkeit dieses Vorgehens

zur natürlichen Auslese nach der Evolutionstheorie von Charles Darwin (1858/1859).

23


Die Menge der Lösungen heißt daher Population, die einzelnen Lösungen Individuen.

Das Kombinieren zweier Individuen, wodurch ein Nachfolger, das Kind, entsteht, wird

Kreuzung genannt. Dabei können mit geringer Wahrscheinlichkeit Variationen, die Mu-

tationen auftreten. Die sich ändernden Zustände der Population, die durch hinzufügen

neuer Individuen entstehen, werden als Generationen bezeichnet.

Die sogenannte Fitnessfunktion entscheidet dabei wie kräftig ein Individuum ist. Dadurch

können schwache Individuen verworfen werden, die starken Individuen überleben bzw.

geben ihre Gene an die Nachkommen weiter. So wird verhindert, dass die Population

zu groß wird, der Algorithmus kann seine Suche auf die günstig scheinenden Lösungen

konzentrieren.

Als Anfangspopulation werden k Individuen zufällig erzeugt. Während der Durchfüh-

rung befinden sich auch stets nur k Individuen in der Population.

Das Verfahren kann schließlich in einem der drei folgenden Fälle anhalten:

1. Eine zufriedenstellende Lösung wurde ermittelt.

2. Eine festgelegte Anzahl von Generationen wurde erzeugt.

3. In einer festgelegten Anzahl nachfolgender Generationen trat keine Besserung ein.

Der Algorithmus gibt dann die beste Lösung aus der Population zurück.

Um mit dem genetischen Algorithmus nun eine günstige Rundreise für den Handlungs-

reisenden zu ermitteln wird er folgendermaßen angewandt.

Die Individuen stellen Permutationen der n Städte oder Knoten dar. Damit handelt es

sich um beliebig schlechte aber gültige Lösungen, da sie Rundreisen entsprechen, die

nacheinander jede Stadt einmal besuchen.

Als Anfangspopulation dienen k zufällig erzeugte Permutationen. Die Fitnessfunktion

misst einfach die Länge der Rundreise der entsprechenden Lösung, wobei kürzere Lö-

sungen fitter also kräftiger sind.

Die Nachfolgegeneration wird hier stets nach folgendem Muster erzeugt.

Sämtliche Individuen der Population werden paarweise mit jedem anderen Individuum

gekreuzt. Dabei entstehen(k2

)Kinder, die gegebenenfalls mutieren. Von den k alten und

k(k−1)2 neuen Individuen werden die k besten nach der Fitnessfunktion gewählt und in

die neue Generation übernommen; der Rest wird verworfen.

24

3.3. Sonstige Verfahren

Die Kreuzung zwischen zwei Individuen i1, i2 wird durchgeführt, indem von i1 eine Teil-

tour t1 der Länge⌊n2

⌋zufällig bestimmt wird. Eine zweite Teiltour t2 der Länge

⌈n2

⌉wird

gebildet, indem von i2 alle Knoten entfernt werden, die schon in t1 enthalten sind. Die

restlichen Knoten werden ausgehend von einem beliebigen Startknoten in der gleichen

Reihenfolge wie in i2 aneinander gereiht und bilden t2.

t1 und t2 stellen dabei keine Rundreisen, sondern lediglich Sequenzen oder Ketten von

Knoten dar. Erst durch Aneinanderreihen entsteht eine Rundreise. Dies geschieht da-

bei auf diejenige der zwei Arten, bei denen die kürzere Gesamtlänge entsteht. Mit einer

Wahrscheinlichkeit von 5 % mutiert anschließend die entstandene Rundreise. Dazu wer-

den zwei Knoten zufällig ausgewählt, die einfach ihre Positionen tauschen.

Beispiel

Das Beispiel zeigt eine Kreuzung zweier Lösungen von ulysses16.tsp.

2

3

4

8

1

16

5

15

14

1312

67

10 9

11

2

3

4

8

1

16

5

15

14

1312

67

10 9

11

Abbildung 3.8: Diese zwei Individuen sollen gekreuzt werden. Links ist t1 bereits her-vorgehoben.

2

3

4

8

1612

10 9

Abbildung 3.9: t2 entsteht durch Auftrennen einer zufällig ausgewählten Kante der üb-rig gebliebenen Rundreise aus i2.

25


2

34

8

16

12

10 9

1

515

14

13

6

7

11

t1 t2

Abbildung 3.10: Die 2 Teiltouren werden zusammengefügt. Falls dadurch die Gesamt-tour kürzer wird, wird t2 zuvor umgedreht.

2

3

4

8

1

16

5

15

14

1312

67

10 9

11

Abbildung 3.11: Hier fand keine Mutation statt. Die gekreuzte Rundreise hat eine Per-formanz von 1,32. Damit trat bei dieser Kreuzung keine Besserunggegenüber den Eltern (1,24 bzw. 1,21) ein.

Das Beispiel macht deutlich, dass nicht bei jeder Kreuzung eine Besserung eintritt.

Es wird sogar immer unwahrscheinlicher, je besser die Performanz der Eltern ist, noch

eine Besserung per Kreuzung zu erzielen. Während anfangs noch bei fast jeder Genera-

tion mit einer besseren Lösung gerechnet werden kann, werden im Laufe des Verfahrens

mit zunehmender Güte im Mittel immer mehr Generationen nötig um überhaupt noch

eine Besserung zu erzielen.

Deswegen skaliert das Verfahren nicht für große Instanzen, auch wenn für kleine Instan-

zen in kurzer Zeit die optimale Tour gefunden werden kann.

Damit bietet der genetische Algorithmus keine Garantie bzgl. der Performanz der ermit-

telten Lösung.

26

4 Testdurchführung

4.1 Testsystem

Als Testsystem dient ein iMac (Late 2006).

HardwareProzessor: Intel Core 2 Duo 2,16 GHzArbeitsspeicher: 2 GB DDR2 SDRAMSoftwareBetriebssystem: Mac OS X 10.4.10Java: J2SE 1.5.0_07-164

4.2 Laufzeitanalyse und Testergebnisse

Für die Verfahren Nearest Neighbor und Random Insertion wurden zur Ermittlung der

Performanz Testserien durchgeführt mit 50 Wiederholungen pro Instanz für alle Instan-

zen mit Ausnahme von pla33810.tsp und pla85900.tsp; bei ihnen wurden nur 5 Wie-

derholungen durchgeführt. Die Startknoten wurden dabei in jeder Iteration stets zufällig

gewählt. Für die folgenden Ergebnisse wird der arithmetische Mittelwert über alle Itera-

tionen betrachtet. Die Verfahren MST-Heuristik und Heuristik von Christofides hingegen

liefern reproduzierbare Ergebnisse und wurden nur jeweils einmal ausgeführt.

Zur Messung der Laufzeit wurden alle Heuristiken ebenfalls nur jeweils einmal ange-

wandt, weil bei wiederholter Anwendung die nachfolgenden Iterationen ansonsten teil-

weise erheblich schneller ausgeführt werden konnten, was auf die Verwendung von Ca-

ches zurückgeführt werden kann.

27

Kapitel 4. Testdurchführung

Nearest Neighbor

Abbildung 4.1 zeigt die gemittelten Performanzen der Testserie mit 50 Wiederholungen

aller Testinstanzen bis 2.392 Knoten. Nicht dargestellt sind 13 Instanzen aus TSPLIB mit

Dimensionen zwischen 3.000 und 85.900 Knoten.

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30Random Insertion

0 400 800 1200 1600 2000 24001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

3000 14000 25000 360001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35


Nearest Neighbor

Perf

orm

anz

Dimension

40 210 380 550 720 890 10601,0

1,1

1,2

1,3

1,4

1,5Christo�des (approx.)

Christo�des (exakt)

Performanz von Nearest Neighbor

0

55

110

165

220

275

330Anzahl

1,02

69

1,02

56

1,02

44

1,02

31

1,02

19

1,02

06

1,01

94

1,01

81

1,01

69

1,01

56

1,01

44

1,01

31

1,01

19

1,01

06

0

20

40

60

80

1001,

3040

1,29

40

1,28

40

1,27

40

1,26

40

1,25

40

1,24

40

1,23

40

1,22

40

1,21

40

1,20

40

0

30

60

90

1,30

40

1,29

40

1,28

40

1,27

40

1,26

40

1,25

40

1,24

40

1,23

40

1,22

40

1,21

40

1,20

40

0

30

60

90

1,30

40

1,29

90

1,29

40

1,28

90

1,28

40

1,27

90

1,27

40

1,26

90

1,26

40

1,25

90

1,25

40

1,24

90

1,24

40

1,23

90

1,23

40

1,22

90

1,22

40

1,21

90

1,21

40

1,20

90

1,20

40

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35

1,40

Perf

orm

anz

Dimension

Abbildung 4.1: Performanzen von Nearest Neighbor für alle Instanzen bis 3.000 Kno-ten. Jedes Kästchen steht für eine Instanz, für die der arithmetischeMittelwert aus 50 Testwiederholungen ermittelt wurde.

Es sollen einige Instanzen genauer betrachtet werden. si1032.tsp sticht durch seine au-

ßerordentlich gute Performanz hervor. Mit einer Dimension von 1.032 wurde im Mittel

eine Performanz von 1,0197 erreicht. In einem eigenen Test wird die Häufigkeitsvertei-

lung der Performanzen für jeden möglichen Startknoten der 1.032 Knoten untersucht.

Abbildung 4.2 zeigt die Häufigkeitsverteilung der Performanzen auf Intervalle der Länge

0,00125 an.

Die Lösungen liegen extrem nah beieinander. Egal welcher Knoten als Startknoten be-

stimmt wird, eine mit Nearest Neighbor ermittelte Lösung für die Instanz si1032.tsp

wird niemals mehr als 2,25 % länger sein als die optimale Lösung. Damit handelt es

sich ganz und gar nicht um eine typische Instanz aus TSPLIB. si1032.tsp selbst liegt

nur als Adjazenzmatrix vor und kann deshalb nicht grafisch dargestellt werden. Bei Be-

trachtung der Adjazenzmatrix fällt jedoch auf, dass die Distanz von vielen Knoten zu

ganzen Mengen von anderen Knoten gleich ist. So nehmen beispielsweise die Gewichte

28

4.2. Laufzeitanalyse und Testergebnisse

der mehr als eintausend inzidenten Kanten des ersten Knotens nur weniger als 100 ver-

schiedene Werte an. Zwei weitere Instanzen, die fast ebenso stark nach unten ausreißen

sind si175.tsp und si535.tsp mit den gleichen Besonderheiten wie si1032.tsp.

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25


0 400 800 1200 1600 2000 24001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

3000 14000 25000 360001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35


Nearest Neighbor

Perf

orm

anz

Dimension

40 210 380 550 720 890 10601,0

1,1

1,2

1,3

1,4




0

20

40

60

80

100

1,30

40

1,29

40

1,28

40

1,27

40

1,26

40

1,25

40

1,24

40

1,23

40

1,22

40

1,21

40

1,20

40

0

30

60

90

1,30

40

1,29

40

1,28

40

1,27

40

1,26

40

1,25

40

1,24

40

1,23

40

1,22

40

1,21

40

1,20

40

0

30

60

90

1,30

40

1,29

90

1,29

40

1,28

90

1,28

40

1,27

90

1,27

40

1,26

90

1,26

40

1,25

90

1,25

40

1,24

90

1,24

40

1,23

90

1,23

40

1,22

90

1,22

40

1,21

90

1,21

40

1,20

90

1,20

40

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35

1,40

Perf

orm

anz

Dimension

0

55

110

165

220

275

330

1,02

56

1,02

44

1,02

31

1,02

19

1,02

06

1,01

94

1,01

81

1,01

69

1,01

56

1,01

44

1,01

31

1,01

19

1,01

06

Anz

ahl

Intervallzentrum

Abbildung 4.2: Verteilung der Performanzen für alle 1.032 möglichen Startknoten vonsi1032.tsp. Die Werte an der Abszisse geben das Zentrum des Inter-valls an. An der Ordinate lässt sich ablesen wie viele der 1.032 Lösungenin das jeweilige Intervall fallen.

Mit der Instanz nrw1379.tsp (1.379 Städte in Nordrhein-Westfalen) soll ein typischer

Vertreter von TSPLIB mit der gleichen Methode wie si1032.tsp untersucht werden.

2500 3500 4500 55005500

6500

7500

8500

0

30

60

90

1,30

40

1,29

90

1,29

40

1,28

90

1,28

40

1,27

90

1,27

40

1,26

90

1,26

40

1,25

90

1,25

40

1,24

90

1,24

40

1,23

90

1,23

40

1,22

90

1,22

40

1,21

90

1,21

40

1,20

90

1,20

40

Anzah

l

Intervallzentrum

Abbildung 4.3: Die nordrein-westfälischen Städte sowie die Häufigkeitsverteilung derPerformanzen für alle möglichen Startknoten. Die Intervalle haben eineLänge von 0,0025.

29


Man sieht, dass bei einer recht gleichmäßig verteilten Menge an Städten die Perfor-

manzen aller Startknoten auch auf einem wesentlich größeren Bereich verteilt sind als

bei speziellen Instanzen wie si1032.tsp. Nearest Neighbor liefert für jeden möglichen

Startknoten für nrw1379.tsp eine Performanz zwischen 1,205 und 1,3025.

Random Insertion

Bei Analyse der Ergebnisse der Testserie zur Bestimmung der Performanzen von Random

Insertion lässt sich feststellen, dass im Vergleich zu Nearest Neighbor hier mit besseren

Ergebnissen gerechnet werden kann. Abbildung 4.4 stellt die Messergebnisse der beiden

Verfahren gegenüber.

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35

1,40

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

0 400 800 1200 1600 2000 24001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

3000 14000 25000 360001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35


Nearest Neighbor

Perf

orm

anz

Dimension

40 210 380 550 720 890 10601,0

1,1

1,2

1,3

1,4




Performanz von Random Insertion

0

55

110

165

220

275

330Anzahl

1,02

69

1,02

56

1,02

44

1,02

31

1,02

19

1,02

06

1,01

94

1,01

81

1,01

69

1,01

56

1,01

44

1,01

31

1,01

19

1,01

06

0

30

60

90

1,30

40

1,29

90

1,29

40

1,28

90

1,28

40

1,27

90

1,27

40

1,26

90

1,26

40

1,25

90

1,25

40

1,24

90

1,24

40

1,23

90

1,23

40

1,22

90

1,22

40

1,21

90

1,21

40

1,20

90

1,20

40

Abbildung 4.4: Performanzen aller Instanzen unter 3.000 Knoten der Testserie von Ran-dom Insertion und noch einmal zum Vergleich die von Nearest Neighbor

Es lässt sich der Eindruck gewinnen, dass mit zunehmender Dimension mit Nearest

Neighbor bessere und mit Random Insertion schlechtere Ergebnisse erzielt werden. Ein

Blick auf die restlichen Instanzen aus TSPLIB, die in Abbildung 4.4 nicht dargestellt sind,

zeigt, dass dies allgemein nicht so ist.

30


0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35

1,40

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

0 400 800 1200 1600 2000 24001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

3000 14000 25000 360001,0

1,1

1,2

1,3

1,4

1,5

1,6MST-Heuristik

0 400 800 1200 1600 2000 24001,00

1,05

1,10

1,15

1,20

1,25

1,30

1,35


Nearest Neighbor

Perf

orm

anz

Dimension

40 210 380 550 720 890 10601,0

1,1

1,2

1,3

1,4




Performanz von Random Insertion

0

55

110

165

220

275

330Anzahl

1,02

69

1,02

56

1,02

44

1,02

31

1,02

19

1,02

06

1,01

94

1,01

81

1,01

69

1,01

56

1,01

44

1,01

31

1,01

19

1,01

06

0

30

60

90

1,30

40

1,29

90

1,29

40

1,28

90

1,28

40

1,27

90

1,27

40

1,26

90

1,26

40

1,25

90

1,25

40

1,24

90

1,24

40

1,23

90

1,23

40

1,22

90

1,22

40

1,21

90

1,21

40

1,20

90

1,20

40

1500 7000 12500 18000 23500 29000 345001,05

1,15

1,25

1,35Pe

rfor

man

z

Dimension

Abbildung 4.5: Vergleich der Instanzen großer Dimension. Nicht abgebildet istpla85900.tsp, wofür Nearest Neighbor und Random Insertion jeweilseine Performanz von 1,15 ermittelt haben.

„Wie random ist Random Insertion?“

In Abschnitt 3.1.2 auf Seite 16 kam die Frage auf wie sehr die Ergebnisse von wieder-

holten Verfahrensanwendungen bei gleichen Startbedingungen voneinander abweichen

können.

0

5

10

15

20

25

30

35nrw1379.tsp

pa561.tsp

bier127.tsp

berlin52.tsp

ulysses22.tsp

1,231,211,191,171,151,131,111,091,071,051,031,01

Anzah

l

Intervallzentrum

Abbildung 4.6: Häufigkeitsverteilung von jeweils 50 Anwendungen von Random Inser-tion auf Instanzen unterschiedlicher Größe mit jeweils immer gleichenStartbedingungen.

31


Anhand von fünf Beispielinstanzen unterschiedlicher Dimension soll dies untersucht

werden.

Abbildung 4.6 zeigt die Häufigkeitsverteilung der Performanzen, die in 50 Testwiederho-

lungen mit jeweils immer gleichen Startbedingungen ermittelt wurden. Die Ergebnisse

zeigen ähnliche Performanz und ähnliches Streuverhalten aller fünf Instanzen. Ledig-

lich ulysses22.tsp zeigt verhältnismäßig gute Ergebnisse, was jedoch – hier nicht zu

sehen – alle Testinstanzen mit Dimensionen unter 50 gemeinsam haben.

ulysses22.tsp berlin52 bier127.tsp pa561.tsp nrw1379.tsp0,036 0,031 0,026 0,013 0,007

Tabelle 4.1: Standardabweichungen der 5 Instanzen aus Abbildung 4.6 bei 50 Wieder-holungen mit jeweils gleichen Startbedingungen

Die Zahlen der beiden gierigen Verfahren im Vergleich der Testserie über alle Testinstan-

zen sind in Tabelle 4.2 zu sehen.

Nearest Neighbor Random InsertionSchlechteste Performanz: 1,3662 1,2320Beste Performanz: 1,0197 1,0230Arithmetisches Mittel: 1,2445 1,1105Median: 1,2532 1,1086Varianz: 0,0036 0,0021Standardabweichung: 0,06 0,0459

Tabelle 4.2: Zusammenfassung der Messergebnisse zu Nearest Neighbor und RandomInsertion für alle 110 Testinstanzen

MST-Heuristik

Die MST-Heuristik liefert die durchweg schlechtesten Ergebnisse. Abbildung 4.7 zeigt

die Häufigkeitsverteilung der Performanzen auf Intervalle der Länge 0,05.

Der Mittelwert beträgt 1,34 und die Standardabweichung 0,09.

Abbildung 4.8 zeigt die Performanz der Testinstanzen gegenüber der Dimension.

32


0

5

10

15

20

25

30

35

1,57

5

1,52

5

1,47

5

1,42

5

1,37

5

1,32

5

1,27

5

1,22

5

1,17

5

1,12

5

1,07

5

1,02

5

Intervallzentrum

Anzah

l

Abbildung 4.7: Häufigkeitsverteilung der Performanzen aller Instanzen mit Ausnahmevon pla85900.tsp bei Verwendung der MST-Heuristik

10 100 1000 10000 1000001,0000

1,0500

1,1000

1,1500

1,2000

1,2500

1,3000

1,3500

1,4000

1,4500

1,5000

1,5500

Dimension

Performanz

Abbildung 4.8: Performanzen der MST-Heuristik aller Instanzen mit Ausnahme vonpla85900.tsp nach Dimension unter Verwendung einer logarithmi-schen Skala für die Dimension. Auffällig: die Positionen der Punkte sindfast auf ein Dreieck im oberen Bereich beschränkt. Nur drei Instanzenliegen deutlich darunter. Es handelt sich um si175.tsp, si535.tsp undsi1032.tsp.

33


Die Heuristik von Christofides

Die von Michael Maguire und Luis Goddyn entwickelte Implementierung des Algorith-

mus’ von Edmonds, die hier zur Bestimmung eines gewichtsminimalen perfekten Mat-

chings verwendet wird, funktioniert nur bei Instanzen, bei denen die Knoten in der

euklidischen Ebene liegen.

Dem gegenüber gestellt wird die Implementierung eines Verfahrens von Wattenhofer

und Wattenhofer zur Bestimmung einer Näherungslösung eines gewichtsminimalen per-

fekten Matchings.

40 244 448 652 856 10601,0

1,1

1,2

1,3

1,4



44 94 144 194 2441,0

1,1

1,2

1,3

244 346 448 550 652 754 856 958 10601,0

1,1

1,2

1,3

Näherungslösung (Wattenhofer)

Exakte Lösung (Edmonds)

Dimension

Perf

orm

anz

Abbildung 4.9: Die Performanzen der Instanzen mit euklidischer Knotenmenge bei Ver-wendung der Heuristik von Christofides. Jedes Kästchen steht für eineTestinstanz.

Abbildung 4.9 zeigt die Ergebnisse der beiden Implementierungen im Vergleich. Bei Ver-

wendung des exakten gewichtsminimalen perfekten Matchings wurde im Mittel eine

Performanz von 1,1053 und bei Verwendung des approximierten1 Matchings eine Per-

formanz von 1,1659 erreicht.

In nur einem einzigen Fall (pr144.tsp) führte die Verwendung eines approximierten

Matchings zu einer insgesamt kürzeren Rundreise als bei Verwendung des exakten Mat-

chings. Dort konnte aus einer längeren Eulertour zufällig eine günstigere Lösung ermit-

telt werden.

1Dies gilt bei Wattenhofer nur für die Menge der in Abbildung 4.9 dargestellten euklidischen Instanzen.Tabelle 4.3 zeigt die Ergebnisse für alle gültigen Testinstanzen einschließlich der nicht-euklidischen.

34


Allgemein sorgt die Verwendung einer Näherungslösung für das gesuchte gewichtsmini-

male perfekte Matching dafür, dass für die Heuristik von Christofides eine Güte von 1,5

nicht mehr garantiert werden kann.

Die Messergebnisse über alle Testinstanzen, das sind alle euklidischen sowie solche mit

expliziten Entfernungsangaben, zeigt jedoch, dass selbst für die Näherungslösung nie-

mals eine Performanz schlechter als 1,3 ermittelt wurde. Wenn 1,3 auch keine echte

obere Schranke darstellt, so zeigt dies doch zumindest, dass es schon speziell konstru-

ierter Instanzen bedarf um möglichst schlechte Ergebnisse zu erzielen.

MST-Heuristik Christofides Christofides(exakt) (approx.)

Schlechteste Performanz: 1,5166 1,1760 1,2704Beste Performanz: 1,0380 1,0318 1,0160Arithmetisches Mittel: 1,3441 1,1053 1,1630Median: 1,3596 1,1074 1,1698Varianz: 0,0082 0,0009 0,0022Standardabweichung: 0,0908 0,0298 0,0474Anzahl der Testinstanzen: 109 51 94

Tabelle 4.3: Zusammenfassung der Messergebnisse zu MST-Heuristik und Heuristik vonChristofides

Laufzeiten der Verfahren

Bei der Analyse der Laufzeiten muss zwischen den Formaten der Instanzen differenziert

werden. Instanzen, bei denen die Distanzen explizit gegeben sind, werden sich – bei

gleicher Dimension – immer schneller lösen lassen als Instanzen mit euklidischen oder

geografischen Koordinaten.

Auch existiert keine Instanz mit explizit gegebenen Distanzen mit größerer Dimension

als 1.032 und keine geografische Instanz mit größerer Dimension als 666.

Bei solch kleinen Dimensionen liegen die Messergebnisse noch recht nah beieinander. Le-

diglich die Heuristik von Christofides bei Verwendung der Implementierung von Magui-

re/Goddyn zur Bestimmung eines gewichtsminimalen perfekten Matchings zeigt Lauf-

zeiten, die deutlich höher liegen. Auch wenn dieses Verfahren mit O(n4) die erwar-

tungsgemäß höchsten Laufzeiten hat, so ist dieser Umstand wohl eher darin zu sehen,

35


dass die Implementierung primär für ein Applet geschrieben wurde um Matchings zu

visualisieren für kleine Mengen bis ca. 50 Knoten.

0 200 400 600 800 10000

0,05

0,1

0,15

0,2

0,25

0,3

0,35

0,4

0,45

0,5

0,55

0,6

0,65

0,7

0,75

0,8

0,85

Christof. (approx., eu-klidisch)

MST (euklidisch)

Nearest Neighbor (eu-klidisch)

Random Insertion (eu-klidisch)

MST (Geo)

Nearest Neighbor (Geo)

Random Insertion (Geo)

Christof. (approx., ex-plizit)

MST (explizit)

Nearest Neighbor (ex-plizit)

Random Insertion (ex-plizit)

Dimension

LaufzeitinSekunden

Abbildung 4.10: Laufzeiten für kleine Instanzen bis 1.000 Knoten. Es zeichnet sich be-reits ab, dass Random Insertion und Nearest Neighbor sowie MST-Heuristik und Christofides (approx.) stets recht nah beieinander lie-gen. Hier nicht dargestellt: Christofides mit exaktem gewichtsminima-lem Matching.

Abbildung 4.10 stellt die Laufzeiten der Testinstanzen bis 1.000 und Abbildung 4.11

bis 7.500 Knoten grafisch dar. Der leichte Einschnitt in der Laufzeit in Abbildung 4.11

bei ca. n = 4.500 Knoten für die MST-Heuristik kommt daher, dass bei der Instanz

fnl4461.tsp die Koordinaten in ganzen Zahlen und bei der Instanz fl3795.tsp in ge-

brochenen Zahlen in Exponentialschreibweise vorliegen, was höheren Rechenaufwand

bedeutet.

Dort ist ebenfalls der Verlauf der Laufzeiten für Brute Force bei Verwendung von In-

stanzen mit explizit angegebenen Distanzen dargestellt. Selbst in diesem Fall beträgt die

Laufzeit bei nur 13 Städten bereits rund 20 Minuten.

Die Laufzeiten der nicht in den Diagrammen dargestellten Instanzen sind in Tabelle 4.4

36


aufgelistet.

0 200 400 600 800 10000

0,05

0,1

0,15

0,2

0,25

0,3

0,35

0,4

0,45

0,5

0,55

0,6

0,65

0,7

0,75

0,8

0,85

Christof. (approx., eu-klidisch)

MST (euklidisch)

Nearest Neighbor (eu-klidisch)

Random Insertion (eu-klidisch)

MST (Geo)

Nearest Neighbor (Geo)

Random Insertion (Geo)

Christof. (approx., ex-plizit)

MST (explizit)

Nearest Neighbor (ex-plizit)

Random Insertion (ex-plizit)

DimensionLaufzeitinSekunden

0 1000 2000 3000 4000 5000 6000 7000 80000

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

160

170

Christofides (exakt)

Christofides (approx.)

MST-Heuristik

Nearest Neighbor

Random Insertion

Brute Force (explizit)

Dimension

LaufzeitinSekunden

Abbildung 4.11: Laufzeiten für euklidische Instanzen. Christofides’ Heuristik steigtschon früh dramatisch an, was nicht zuletzt an der Implementierungvon Edmonds’ Algorithmus liegt.

Dimension Christofides MST-Heuristik Nearest Neighbor Random Insertion(approx.)

11.849 3 min 31 s 3 min 25 s 24 s 27 s13.509 8 min 7 min 30 s 31 s 36 s14.051 3 min 39 s 3 min 8 s 33 s 38 s15.112 8 min 30 s 7 min 40 s 39 s 44 s18.512 12 min 27 s 11 min 15 s 57 s 1 min 5 s33.810 70 min 27 s 63 min 7 s 3 min 55 s 4 min 42 s85.900 unbestimmt unbestimmt 24 min 34 s 31 min 48 s

Tabelle 4.4: Laufzeiten für große Instanzen

Genetischer Algorithmus

Auf 4 Beispielinstanzen unterschiedlicher Größe soll der genetische Algorithmus ange-

wandt werden. Mit einer Populationsgröße von 10 sollen 100 Generationen erzeugt wer-

37


den. Abbildung 4.12 zeigt den Verlauf.

0 10 20 30 40 50 60 70 80 90 1001

3

5

7

9

11

13

15

17 u574.tsp

ulysses22.tsp

gr137.tsp

fri26.tsp

Performan

z

Generation

0 10 20 30 40 50 60 70 80 90 1001

3

5

7

9

11

13

15

17 u574.tsp

ulysses22.tsp

gr137.tsp

fri26.tsp

Performan

z

Generation

Abbildung 4.12: Verlauf des genetischen Algorithmus’. Jedes Kästchen steht für eineGeneration in der eine Verbesserung gegenüber der Elterngenerationeingetreten ist. Die Performanz steht für das kräftigste Individuum derjeweiligen Generation.

Man erkennt, dass für kleine Instanzen durchaus schnell gute Ergebnisse erzielt werden

konnten. Die beiden größeren Instanzen hingegen lieferten nicht so gute Ergebnisse.

Hinzu kommt, dass die Laufzeiten hier für 100 Generationen bereits schon recht hoch

sind wie der Vergleich mit der Laufzeit der MST-Heuristik zeigt.

Instanz Genetischer Algorithmus MST-Heuristikulysses22.tsp 66 ms 370 µs

fri26.tsp 200 ms 175 µsgr137.tsp 1 s 13 ms

u574 5 s 200 ms

Tabelle 4.5: Laufzeiten für 100 Generationen des genetischen Algorithmus’

Abbildung 4.13 zeigt warum das Verfahren nicht skaliert. Bei einer Steigerung der An-

zahl der Generationen auf 2.000 konnte die Performanz für die Instanz u574.tsp nur

38


auf 3,5 gesenkt werden gegenüber dem ersten Versuch, bei dem in 100 Generationen

eine Performanz von 11,6 erreicht wurde. Die Kurve konvergiert jedoch immer langsa-

mer, dieser zweite Versuch dauerte bereits 111 Sekunden und in nur 972 Generationen

konnte eine Verbesserung gegenüber der Elterngeneration erreicht werden; beim ersten

Versuch trat noch in jeder Generation eine Besserung ein.

0 10 20 30 40 50 60 70 80 90 1001

3

5

7

9

11

13

15

17 u574.tsp

ulysses22.tsp

gr137.tsp

fri26.tsp

Performan

zGeneration

0 400 800 1200 1600 20001

3

5

7

9

11

13

15

17

Performan

z

Generation

Abbildung 4.13: Wiederholung des genetischen Algorithmus für u574.tsp mit diesmal2.000 Generationen

Was es sonst noch gibt

Mit Concorde ([4]) steht alternativ eine Software zur Verfügung, die den Ansatz der

linearen Optimierung verfolgt um das Problem des Handlungsreisenden zu lösen.

Dabei handelt es sich tatsächlich nicht mehr um Näherungslösungen, sondern die kür-

zestmögliche Rundreise durch die jeweilige Instanz. Concorde ist auch das Programm,

mit dem die optimalen Lösungen zu 106 der 110 Testinstanzen von TSPLIB ermittelt

werden konnten.

39


Die Brute Force-Methode ist mit ihrer exponentiell anwachsenden Laufzeit ungeeignet

um exakte Lösungen zu bestimmen; Concorde schafft dies deutlich schneller.

Die Laufzeit von Concorde für einige Testinstanzen ist in Tabelle 4.6 und Abbildung 4.14

dargestellt.

Instanz Concorde ChristofideskroA100.tsp 1 0,7pr144.tsp 2 0,5a280.tsp 2,5 1,8

lin318.tsp 7,4 2,4rd400.tsp 53 7,6fl417.tsp 34 6,6d493.tsp 251 19,9u574.tsp 28 15,3

Instanz Concorde Christofidesrat575.tsp 163 24p654.tsp 13 31d657.tsp 150 28u724.tsp 220 34pr1002 44 132

u1060.tsp 616 164nrw1379 502pr2392 63

Tabelle 4.6: Laufzeit von Concorde einiger ausgewählter Instanzen und Vergleichmit Christofides. Alle Angaben in Sekunden. Mit der Maguire/Goddyn-Implementierung von Edmonds’ Algorithmus ließen sich keine Matchingsbestimmen für größere Instanzen als u1060.tsp.

0 800 1600 24000

34

68

102

136

170Christo�des

Concorde

Dimension

Lauf

zeit

in S

ekun

den

Abbildung 4.14: Grafische Darstellung der Ergebnisse aus Tabelle 4.6. Nicht dargestelltsind die Ergebnisse, deren Laufzeit 170 Sekunden übersteigt.

Die Laufzeiten bei Concorde schwanken mitunter sehr stark. Während beispielsweise

nrw1379.tsp sehr lange braucht, kann die deutlich größere Instanz pr2392.tsp viel

40


schneller abgeschlossen werden. In Abbildung 4.15 wird ersichtlich warum.

500 6000 115001000

8500

16000

Abbildung 4.15: Die 2.392 Knoten aus pr2392.tsp. Das Vorhandensein speziellerStrukturen und lokaler Gruppen begünstigt das Ausnützen linearerOptimierung. Bei nrw1379.tsp sind die Städte/Knoten dagegen gleich-mäßig verteilt.

41


Abbildung 4.16: Concorde mit der optimalen Lösung zu p654.tsp

42

5 Bewertung der Ergebnisse

Auch mit vorliegenden Messergebnissen fällt die Bewertung noch nicht ganz leicht. Es

lassen sich aber schon einige Beobachtungen äußern.

Der gierige Ansatz der einfachen Heuristiken lieferte durchweg Ergebnisse, gegen die

die ausgefeiltere Methodik der MST-Heuristik nicht ankam. Ihren Vorteil gegenüber den

einfachen Heuristiken, nämlich die Gütegarantie, konnte die MST-Heuristik nicht aus-

spielen, weil alle Verfahren sowieso Ergebnisse erzielten, die deutlich unter den oberen

Schranken lagen. Mit nur einer einzigen Testinstanz überhaupt überschritt die MST-

Heuristik die obere Schranke von 1,5 der verbesserten Heuristik von Christofides knapp.

Die Ergebnisse der beiden Varianten der Christofides-Heuristik liegen ebenfalls derart

niedrig, dass bei Verwendung einer Näherungslösung des gewichtsminimalen perfekten

Matchings die Gefahr des Überschreitens der oberen Schranke von 1,5 praktisch nicht

gegeben ist, wenn man nicht gerade Instanzen konstruiert, die genau darauf abzielen.

Was die Ergebnisse deutlich zeigen, ist dass Nearest Neighbor das schnellste Verfahren

darstellt, Random Insertion jedoch nur unwesentlich langsamer ist; zudem kann bei

Random Insertion im Mittel mit besseren Ergebnissen gerechnet werden.

Die Ergebnisse von Random Insertion sind sogar so gut, dass sie fast gleichauf mit denen

der Christofides-Heuristik liegen, für welche im Mittel die beste Performanz ermittelt

wurde.

„Christofides’ Algorithmus ist der beste heute bekannte Approximationsalgorithmus für

MinMTSP1.“ (aus [7])

Der Satz hätte selbst dann Bestand, wenn die Messergebnisse der Testinstanzen von Ran-

dom Insertion deutlich besser wären als die von Christofides, weil es sich bei Random

Insertion nicht um einen Approximationsalgorithmus handelt. Dennoch fällt es nicht

ganz leicht das bessere der beiden Verfahren zu bestimmen.

1Mit MinMTSP ist das hier behandelte Problem MinTSP gemeint. M: metrisch, hier Voraussetzung.

43

Kapitel 5. Bewertung der Ergebnisse

Die Performanz aller möglichen Testinstanzen der beiden Verfahren liegt im Mittel bei

1,1053 (Christofides) und 1,1105 (Random Insertion) und damit sehr nah beieinander.

Bei Beschränkung der Instanzen auf diejenigen, auf die auch Christofides angewandt

werden konnte, ergibt sich zwar ein Mittelwert von 1,0995 für Random Insertion und

damit ein geringfügig besserer Schnitt als für Christofides; all diese Werte liegen jedoch

derart nah beieinander, dass sich nur aufgrund dessen kein vernünftiges Urteil treffen

lässt.

Die Heuristik von Christofides hat jedoch zwei entscheidende Nachteile.

1. Ein Verfahren zu implementieren, das in der Lage ist ein gewichtsminimales per-

fektes Matching zu bestimmen stellt die anspruchsvollste Aufgabe bei der Imple-

mentierung der hier vorgestellten Verfahren dar.

2. Die Heuristik von Christofides stellt die mit Abstand langsamste der hier vorge-

stellten Verfahren dar.

Punkt 2 lässt sich relativieren, wenn man berücksichtigt, dass zum einen Algorithmen

existieren, die ein gewichtsminimales perfektes Matching in Zeit O(n3) bestimmen und

zum anderen die hier verwendete Maguire/Goddyn-Implementierung nicht für so große

Mengen von Knoten, wie sie hier vorkommen, geschrieben wurde und sich nicht so ganz

nahtlos in die restliche Implementierung einbinden lässt.

Wegen dieser Problematik der unbefriedigenden Implementierung von Edmonds’ Algo-

rithmus sind die Laufzeiten von Christofides’ Heuristik, wie sie sich in Abbildung 4.11

darbieten, nur schwer zu beurteilen.

Was jedoch bleibt ist das Wissen, dass Christofides’ Heuristik, selbst bei Verwendung

eines approximierten Matchings, eine gegenüber Random Insertion erheblich längere

Laufzeit aufweist, die Performanz jedoch allenfalls gleichauf liegt und sich somit allein

mit dem einzigen Vorteil der Heuristik von Christofides gegenüber Random Insertion,

nämlich der Gütegarantie von 32 , kaum argumentieren lässt, dass der Mehraufwand bei

Implementierung und Anwendung von Christofides’ Heuristik gerechtfertigt ist.

Das letzte Verfahren, der genetische Algorithmus, enttäuscht ebenfalls bei großen In-

stanzen und ist allenfalls geeignet für kleine Instanzen, hat dort allerdings wegen seines

stochastischen Einflusses das Potential selbst die besten Lösungen der anderen Verfahren

noch zu unterbieten und sogar die optimale Lösung zu finden.

44

Literaturverzeichnis

[1] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

[2] http://de.wikipedia.org/wiki/MST-Heuristik.

[3] http://www.math.sfu.ca/~goddyn/Courseware/Visual_Matching.html.

[4] http://www.tsp.gatech.edu/concorde.html.

[5] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and

M. Protasi. Complexity and Approximation. Springer, 1999.

[6] William Cook and André Rohe. Computing minimum-weight perfect matchings,

August 1998.

[7] Prof. Dr. Heribert Vollmer. Skript zur Vorlesung - Komplexität von Algorithmen,

Sommersemester 2005.

[8] Stuart Russel and Peter Norvig. Künstliche Intelligenz: Ein moderner Ansatz. Pearson

Education, Inc, publishing as Prentice Hall, 2. Auflage 2004 edition, 2003.

[9] Angelika Steger. Diskrete Strukturen 1. Springer, 1. korrigierter Nachdruck 2002

edition, 2002.

[10] Mirjam Wattenhofer and Roger Wattenhofer. Fast and Simple Algorithms for

Weighted Perfect Mathing. In CTW on Graphs and Combinatorial Optimization

(CTW), Milano, Italy), 2004.

45

Documents

Traveling Salesman Problem - THI · PDF filereise die – entsprechend den Möglichkeiten der Heuristik – so kurz wie möglich und dabei so lang wie nötig ist