Single Vehicle Round-Trip Routing. Das Problem des Handlungsreisenden

Inhaltsverzeichnis

1. Einleitung

2. Das Rundreiseproblem
2.1 Herkunft und Ziel des Reisenden
2.2 Graphentheorie
2.3 Mathematische Formulierung des STSP
2.4 Komplexität

3. Heuristische Verfahren
3.1 Konstruktionsheuristiken
3.1.1 Nearest Neighbor Heuristik
3.1.2 Farthest Insertion
3.1.3 Christofides' Heuristik
3.2 Verbesserungsheuristiken
3.2.1 2-opt Heuristik
3.2.2 Übersicht reinerVerbesserungsverfahren

4. Metaheuristische Verfahren zur Lösung des TSP
4.1 Metaheuristiken
4.2 Tabu Search

5. Fazit

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1. Einleitung

„Remember that time is money.“

Benjamin Franklin, 1748

Dieses Verhältnis von Zeit zu Geld hat sich vom 18. bis in das 21. Jahrhundert nicht gewandelt. Im Gegenteil, mit voranschreitender Globalisierung und Vernetzung der interkontinentalen Infrastruktur wächst der Wettbewerbsdruck auf konkurrierende Unternehmen. Produkte müssen binnen kürzester Zeit produziert und an den Kunden versendet werden. Ein Aspekt um die Wettbewerbsfähigkeit aufrecht zu erhalten ist die effiziente Koordination für die Beschaffung der zur Produktion notwendige Materialien und auch der Versendung der Endprodukte.

Um die externe und interne Unternehmenslogistik effizient zu gestalten, müssen die logistischen Abläufe bezüglich zurückzulegender Distanzen und die daraus resultierenden Kosten minimiert werden. Dieses kombinatorische Optimierungsproblem lässt sich unter dem Namen „Traveling Salesman Problem“ (TSP) zusammenfassen. Je höher die Anzahl an kombinierenden Elementen eines Optimierungsproblems ist, umso rechenintensiver werden die Arbeitsschritte und desto schwieriger ist es eine optimale Lösung zu finden.

Seit mehreren Jahrzehnten werden deshalb Heuristiken konzipiert, um sich dem TSP möglichst gut anzunähern. Dennoch ist es bis heute nicht gelungen einen Algorithmus zu schreiben, der jede TSP Problemgröße optimal lösen kann. Deswegen ist es von enormer Bedeutung die bereits bestehenden Approximationsalgorithmen bezüglich ihrer Attribute und Lösungsqualität zu evaluieren.

Ziel dieser Ausarbeitung ist, die Nearest Neighbor Heuristik, Farthest Insertion und den Algorithmus von Christofides zu analysieren und untereinander zu vergleichen. Zusätzlich werden diese drei Heuristiken separat und in Verbindung mit dem 2-opt Verfahren an einem eigens implementierten Beispiel „dr13“ angewendet. Nachdem einige weitere Annäherungsmethoden zur Übersicht vorgestellt werden, wird die Metaheuristik Tabu Search^[1] ebenfalls evaluiert und fortführend anhand der Beispielimplementierung getestet, sodass die erhöhte Leistungsfähigkeit von Metaheuristiken gegenüber reinen Nachoptimierungsverfahren deutlich wird.

2. Das Rundreiseproblem

Dieses Kapitel gibt eine kurze historische Einleitung in das Thema und erläutert grundlegende Begriffe und Definitionen, die für das Verständnis dieser Ausarbeitung unabdingbar sind. Der graphischen Modellierung des TSPs folgt die mathematische Formulierung des symmetrischen TSPs (STSP). Abschließend wird die Problematik der kombinatorischen Optimierung bezüglich ihrer AP-Schwere erläutert.

2.1 Herkunft und Ziel des Reisenden

Wie sich der Begriff des „Traveling Salesman Problems“ in der englischen Literatur festigte und wer diesen aufwarf ist bis heute nicht eindeutig. Der Wissenschaftler Merril Flood gibt an, diesen Namen erstmalig in einem mathematischen Zusammenhang in Gegenwart von A. W. Tucker, der ihn 1937 an der Princeton Universität aufschnappt haben soll, gehört zu haben. Dieser konnte Floods Aussage allerdings nicht bestätigen (vgl. Hoffmann und Wolfe, 1985). In der deutschsprachigen Literatur hingegen wurde das Rundreiseproblem erstmalig von F. Voigt (1832) in seinem Buch, „Der Handlungsreisende, wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein“, benannt (vgl. Domschke und Scholl, 2010; vgl. Hoffmann und Wolfe, 1985).

Sicher hingegen ist die grundlegende Zielsetzung, die der Reisende innerhalb des Traveling Salesman Problems verfolgt - die Ermittlung der kürzesten Rundreise. Dabei beginnt die Tour in einer Stadt, die als Ausgangspunkt dient. Einmal gestartet sollen alle Städte, die zu besuchen sind, in der kombinatorisch günstigsten Reihenfolge, entfernungs- bzw. kostenminimal, besucht werden. Im Verkauf dieser Arbeit werden Kosten und Entfernungen bedeutungsgleich als Synonym verwendet. Abschließend kehrt der Reisende wieder zu seinem Ausgangspunkt zurück und schließt damit seine Rundreise. Unabdingbar für die Planung allerdings, dass der Reisende die Entfernungen zwischen allen zu bereisenden Städten kennt (vgl. Applegate et al., 2006; vgl. Hoffmann und Wolfe, 1985).

Unter den verschiedenen Traveling Salesman Touren kann nur der Zyklus entfernungsminimal sein, der den Reisenden in keine einzige Stadt doppelt leitet. Ein solcher Zyklus, der jede Stadt exakt einmal besucht, wird Hamiltonscher Zyklus genannt. Beim Lösen des TSPs wird also versucht den entfernungsminimalen Hamiltonkreis zu ermitteln (vgl. Vahrenkamp, 2003), der seinen Namen William Rowan Hamilton verdankt. Er war einer der größten Mathematiker des 19. Jahrhunderts, der die Idee für den gleichnamigen Zyklus seinem eigen entworfenen Icosian-Spiel verdankt. Dabei handelt es sich um eine geometrische Figur, dem Dodekaeder^[2], mit 20 fixen Knotenpunkten, die es im Sinne des Hamiltonkreises zu einer Tour zu verbinden gilt (vgl. Applegate, 2006).

2.2 Graphentheorie

Um das TSP zu illustrieren, benötigt es eine grafische Modellierung anhand der Graphentheorie, die Bestandteil dieses Kapitels ist und fortan als Grundlage für diese Arbeit dient.

Ein ungewichteter Graph G = (V, E) besteht aus verschiedenen Variablen. V = {vt,..., vn} steht für eine endliche nicht leere Menge an Knotenpunkten, die im Bezug des TSPs die zu besuchenden Städte repräsentieren. Der Index n steht hierbei für die endliche Anzahl zu besuchender Knoten im Graphen. Dies geht aus N = {1,..., n} hervor. E stellt die Kantenmenge dar, die in dem gegebenen Graphen vorhanden ist. Dabei gilt E Ç V X V, was bedeutet, dass jede Kante einem Knotenpaar i und j aus V zugeordnet werden kann. Eine Kante, die zwei Knoten miteinander verbindet, e = {i, j}, steht im Kontext für die Verbindung zwischen zwei Städten des Reisenden. Die Gesamtheit der Kantenmenge E wird definiert durch E = {{v¿, v;·}: 1 < i < j < n}, sodass alle Knoten im Graphen über eine Kante miteinander verbunden sind. Dieses Netzwerk wird nun als vollständig bezeichnet. Beim Zurücklegen einer Wegstrecke von Knoten i zu Knoten j wird zwangsläufig eine Entfernung bewältigt, wodurch gilt, dass die Entfernung oder auch die Kosten c¿;· > 0 sein müssen. Dadurch wird aus dem ungewichteten nun ein gewichteter Graph G = (V, E, c) (Abb. 2.1 und 2.2)^[3], der zur Lösung des TSPs benötigt wird und auch als Grundlage der zu lösenden TSPs innerhalb dieser wissenschaftlichen Arbeit dient (vgl. Domschke und Drexl, 2007; vgl. Vahrenkamp und Mattfeld, 2007).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.1: Ungewichtete Kante

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2: Gewichtete Kante.

Um die Koordinaten der Knoten im Netzwerk und die zugehörigen Kanten zu ermitteln und festzulegen, werden euklidische Daten verwendet. Das bedeutet, dass sich die Koordinaten eines Knotens in der zweidimensionalen Ebene befinden, wie in einem rechtwinkligen (X,Y)-Koordinatensystem. Die Distanzen zwischen zwei Knoten werden wie folgt berechnet (vgl. Vahrenkamp und Mattfeld, 2007):

Abbildung in dieser Leseprobe nicht enthalten

Die Verwendung der euklidischen Distanzmetrik setzt voraus, dass die Dreiecksungleichung innerhalb des TSPs eingehalten wird. Diese besagt, dass das Erreichen eines Endknotens über einen dritten Knoten vom Startknoten aus nicht kürzer sein kann, als der direkte Weg vom Start- zum Endknoten (vgl. Reinelt, 1994). Siehe dazu (2):

Abbildung in dieser Leseprobe nicht enthalten

Weiterhin lässt sich das TSP bezüglich seiner Symmetrie differenzieren. Handelt es sich um ein Asymmetrisches (ATSP), so ist es notwendig die Richtung zu kennen, in der sich der Reisende bewegt, denn die Kosten mit denen eine Kante ei;· gewichtet ist können variieren, abhängig davon in welche Richtung sich der Reisende auf ihr bewegt (vgl. Reinelt, 1994). Es gilt also ciJ- Ψ c¡i (vgl. Domschke und Scholl, 2010). Aufgrund dieser Voraussetzung kann der Fall eintreten, dass das ATSP nicht der Dreiecksungleichung unterliegt (vgl. Reinelt, 1994). Ein solcher Graph wird auch gerichteter Graph^[4] genannt und ließe sich in der Realität beispielsweise durch das Befahren einer Einbahnstraße erklären. Daher ist es sinnvoll bei einer graphischen Darstellung eines Digraphen die Kanten zusätzlich mit Pfeilen zu versehen, um zu erkennen, welches der Start- und welches der Endknoten ist (Abb. 2.4). Beim gegenteiligen Fall, einem STSP, handelt es sich um einen ungerichteten Graphen^[5]. Bei diesem ist es unnötig zu wissen, ob sich der Reisende von Knoten i nach j oder umgekehrt bewegt, wie in Abb. 2.3 zu sehen ist (vgl. Domschke und Drexl, 2007). Daraus ergibt sich, dass im STSP die Einhaltung der Dreiecksungleichung vorausgesetzt ist (vgl. Reinelt, 1994), denn die Entfernungen sind in beide Richtungen gleich, ciJ· = c¡i (vgl. Johnson, 1990). Im Verlauf dieser Arbeit wird sich der Reisende ausschließlich im symmetrischen Raum bewegen.

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Domschke und Drexl, 2007. Domschke und Drexl, 2007.

Im Hinblick auf die zu untersuchenden heuristischen Algorithmen ist es notwendig, den Begriff des Spannbaumes innerhalb einer Graphenmodellierung näher zu erläutern. Ist ein zusammenhängender^[6] Graph G = (V, E, c) gegeben, dann existiert genau dann ein Spannbaum, wenn der Teilgraph G' von G, der die selben Knoten aufweist wie G, mit einer Teilmenge E' 1Ξ E Kanten, welche die Knoten so verbinden, dass keine Zyklen entstehen (Abb. 2.5). Anders formuliert, würde eine Kante aus einer bestehenden Rundreise entfernt, so ergäbe sich ein Spannbaum. Dabei werden die Knoten mit einem Grad gi = 1 als Blätter bezeichnet. Der Knotengrad gibt an, wie viele Kanten mit einem Knoten verbunden sind (vgl. Domschke und Scholl, 2010; vgl. Vahrenkamp und Mattfeld, 2007).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.5: Ein zusammenhängender Graph mit gewichteten Kanten.

Die vollen Kanten zeigen den minimalen Spannbaum im Graphen mit einer Länge von d(T) — 37. Quelle: Cormen et al., 2010.

Innerhalb eines zusammenhängenden Graphen gibt es verschiedene Möglichkeiten einen Spannbaum zu erstellen. Die Länge des Spannbaumes ergibt sich aus (3). Ziel bei der Erstellung soll es allerdings sein, den, wie in Abbildung 2.5 zu sehen, minimalen Spannbaum zu ermitteln. Dazu bietet sich zum einen der Algorithmus von Prim und zum anderen der Algorithmus von Kruskal an, der in Kapitel 3.1.3 genauer erläutert und angewendet wird (vgl. Cormen et al., 2010).

Abbildung in dieser Leseprobe nicht enthalten

Ein zusammenhängender Graph ist Eulersch, wenn alle im Graphen befindlichen Knoten einen geraden Knotengrad von mindestens zwei besitzen (Abb. 2.6 und 2.7). Eine Eulertour oder ein Eulerkreis beschreibt einen Zyklus, der alle Kanten des Eulergraphen exakt einmal enthält. Bewiesen ist, dass ein Eulerscher Graph einen Eulerkreis besitzt. Egal welcher Knoten als Ausgangsknoten der Eulertour in Abbildung 2.7 gewählt wird, es entsteht immer eine Eulertour (vgl. Vahrenkamp, 2003; vgl. Vahrenkamp und Mattfeld, 2007).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.6: Nicht Eulerscher Graph, Quelle: Vahrenkamp, 2003.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.7: Eulerscher Graph, Quelle: Vahrenkamp, 2003.

2.3 Mathematische Formulierung des STSP

Um das kombinatorische Zuordnungsproblem des TSPs abzubilden, benötigt es neben einer graphischen Modellierung auch eine mathematische Formulierung. Diese gibt Aufschluss über die zu optimierende Zielfunktion und die Nebenbedingungen, denen diese unterliegt. Das STSP, welches ein Spezialfall des ATSPs darstellt, lässt sich wie in (4) als ganzzahlige Optimierung formulieren (vgl. Punnen, 2002; vgl. Goetschalckx, 2011).

Abbildung in dieser Leseprobe nicht enthalten

Die in (4) zu sehende Zielfunktion stellt das STSP dar. Diese Formulierung bedeutet, dass die Länge der Traveling Salesman Tour aus der Summe der zurückgelegten Entfernung Cij multipliziert mit der Binärvariable Xij (siehe (7)) minimiert wird. Die Notation der beiden Sigmas geben an, dass die Summierung der Strecke bei der ersten Kante zwischen den Knoten i und j beginnt und bei der letzten Kante zwischen den Knoten η — 1 und n endet.

Folgende Nebenbedingungen sollen das Minimierungsproblem in seiner Optimierung weiter einschränken (vgl. Punnen, 2002; vgl. Goetschalckx, 2011).

Abbildung in dieser Leseprobe nicht enthalten

Nebenbedingung (7) limitiert die Variable xij auf eine Binärvariable. Diese nimmt nur den Wert 1 an, wenn sich der Reisende auf direktem Weg von Knoten i nach j oder umgekehrt begibt und somit die Kante e = {i, j} benutzt. Andernfalls ist sie 0 (vgl. Domschke und Scholl, 2010). Restriktion (5) bestimmt den Grad eines Knotens. Die Addition aus den Summen der eintreffenden und der verlassenden Kante, in und von dem Knoten j weg, ergibt 2. Demnach darf j nur zu zwei Kanten inzident sein. Dadurch wird das Eintreffen in und das Verlassen eines Knotens garantiert und ist zwingende Voraussetzung zur Konstruktion einer Rundreise. Gleichzeitig ist impliziert, dass die Anzahl der Kanten E in einer Traveleing Salesman Tour gleich der Anzahl an Knoten V ist (vgl. Vahrenkamp und Mattfeld, 2007).

Restriktion (6)^[7] soll die Konstruktion einer Rundreise ohne die Entstehung von Subtouren oder Kurzzyklen garantieren. S ist eine Teilmenge der im TSP befindlichen Knoten N. Solange die Summe der realisierten Kanten zwischen den Knoten, die sich in der Teilmenge S befinden, kleiner ist als die Teilmenge |S| — 1, wobei S mindestens den Wert 2 annehmen muss, ist diese Nebenbedingung nicht erfüllt. Daher kann es im Graphen nie zu einer Subtour kommen, da bei einer solchen Rundreise exakt gleich viele Kanten und Knoten auftreten. Deswegen ist die einzige Tour, die gebildet werden kann , eine Traveling Salesman Tour (vgl. Groetschalckx, 2011).

Abbildung in dieser Leseprobe nicht enthalten

Nachdem die Grundlage zur Konstruktion einer Salesman Tour geschaffen ist, müssen noch die gewichteten Kanten, also die Kosten c^·, sinnvoll und übersichtlich bereitgestellt werden. Die Notation erfolgt mit Hilfe einer Distanz- oder Kostenmatrix, die sich gemäß Definition aus Kapitel 2.2 nach Symmetrie und Asymmetrie unterteilen lässt (Tab. 2.1). Die Formulierung (8) und dementsprechend auch die nxn Distanz­oder Kostenmatrix ist wie folgt zu lesen. Der Reisende begibt sich von einem Knoten, erste Spalte, zu einem Zielknoten, erste Zeile. Die Ziffer im Schnittpunkt beider Knoten repräsentiert die Entfernung zwischen den gewählten Knoten. Damit Start- und Endknoten nicht identisch gewählt werden können, sind die Kosten auf unendlich festgelegt, um noch einmal zu verdeutlichen, dass, diese Kombination aufgrund unserer zu minimierenden Zielfunktion unmöglich ist (vgl. Domschke und Scholl, 2010).

Abbildung in dieser Leseprobe nicht enthalten

Tab. 2.1: Symmetrische und asymmetrische Distanzmatrix, Quelle: ähnlich Domschke und Scholl, 2010.

2.4 Komplexität

Das TSP gehört zu den kombinatorischen Optimierungsproblemen und kann dementsprechend einer von zwei Klassifizierungen angehören - der leicht oder schwierig zu lösenden Probleme. Um zu ermitteln, welcher Klasse diese Problemstellung angehört, muss die Komplexität der Algorithmen, die zur Lösung des TSPs verwendet werden, untersucht werden (vgl. Johnson und Papadimitriou, 1985a). Die in diesem Kapitel folgenden Feststellungen bezüglich der Problemklassifizierung und der Komplexität dienen lediglich dem besseren Verständnis und sollen keine Beweisführung darstellen.

Zuerst gilt es die Begriffe des Problems und der Probleminstanz voneinander zu differenzieren. Ein zu lösendes Problem S hängt von der Fragestellung ab, ob beispielsweise ein Graph einen Hamiltonkreis besitzt. Es ist ein klassisches Entscheidungsproblem, wobei die möglichen Antworten nur „ja“ und „nein“ sein können. Die Instanz I eines Problems S ist durch die Gegebenheit konkreter Parameterwerte definiert. Voraussetzung hierfür ist ein kompletter Graph G = (V, E, c). Kann die Problemstellung mit „ja“ beantwortet werden, wird im Folgenden das Optimierungsproblem anhand einer Zielfunktion gelöst. Die Laufzeit eines Algorithmus wird anhand der gegeben Parameter durch die Instanz I als binärer Zeichencode in Form einer Komplexitätsfunktion L(I) dargestellt. Die Länge der Funktion hängt von den elementaren ausgeführten Rechenoperationen ab, wie beispielsweise Addition und Multiplikation (vgl. Reinelt, 1994; vgl. Vahrenkamp und Mattfeld, 2007).

Die Funktion L(I) wird durch die Schreibweise O(L) abgeschätzt. Um Algorithmen zum Lösen eines Problems S gegeben einer Instanz I zu vergleichen, werden Kennzahlen als Maßstab der Zeitkomplexität verwendet (Vahrenkamp und Mattfeld, 2007). Der Worst-Case-Fall ist eine davon. Er beschreibt die maximal auftretende

Anzahl an Rechenoperationen, die zur Lösung eines Problems S benötigt werden. Damit ist gleichzeitig eine obere Schranke festgelegt, die garantiert, dass ein Algorithmus keinesfalls mehr Rechenzeit benötigt als von der Worst-Case-Schranke angegeben. In der Praxis werden jedoch kaum Fälle zu finden sein, bei denen der tatsächliche schlechteste anzunehmende Fall eintritt (Johnson und Papadimitriou, 1985a).

Vahrenkamp und Mattfeld (2007) beschreiben einen Worst-Case-Fall durch die Abschätzung der Zeitkomplexität eines minimalen Spannbaums. Sequentiell können immer nur zwei Kanten e miteinander verglichen und daraufhin sortiert werden. Im schlechtesten Fall besitzt das Sortieren etwa eine Komplexität von e2. Die Auswahl der Kanten zum Verbinden der Knoten n bedingt nur eine lineare Laufzeit. Beide Prozesse zusammen werden so abgeschätzt, dass das höchste Polynom in der Laufzeitabschätzung dominiert, wie es in (9) formuliert ist.

Abbildung in dieser Leseprobe nicht enthalten⁸

Johnson und Papadimitriou (1985a) nennen einen Algorithmus effizient, falls dessen Komplexität wie in (9) im schlechtesten Fall polynomial ist. Algorithmen, die keine polynomial laufende Zeitkomplexität aufweisen, werden demnach als ineffizient eingestuft. Dabei handelt es sich um Funktionen, die exponentiell wachsende Zeitkomplexitäten besitzen, wie beispielsweise 0(2n ). Tabelle 2.2 soll den Unterschied zwischen einem effizienten und einem ineffizientes Algorithmus verdeutlichen.

Abbildung in dieser Leseprobe nicht enthalten

Tab. 2.2: Rechenzeiten in Abhängigkeit der Komplexität eines Algorithmus,

Quelle: ähnlich Vahrenkamp und Mattfeld, 2007.

Eine Rechenoperation der in Tabelle 2.2 angeführten Komplexitäten dauert 10-6 Sekunden (Vahrenkamp und Mattfeld, 2007). Es wird deutlich, dass Algorithmen mit exponentiellem Zeitaufwand bei steigender Größe der Probleminstanz massiv an Optimierungsdauer zunehmen. Bei polynomialer Laufzeit hingegen bleibt die Berechnungsdauer bei n = 50 unter einer Sekunde, wohingegen der exponentielle Algorithmus über 35 Jahre bräuchte.

Gemäß Reinelt (1994) sind viele Optimierungsprobleme, so auch das TSP, nicht in polynomialer Zeit lösbar. Kann das Entscheidungsproblem einer Instanz I mit „ja“ beantwortet werden, werden die Eingabedaten s, welche die Lösung des Problems sein könnten, als nichtdeterministisch geschätzt. In einem weiterführenden Schritt wird deterministisch überprüft, ob die Dateneingabe s die Lösung des Problems darstellt oder nicht. Wenn keine positive Antwort ermittelt werden kann, liefe der Algorithmus ewig, da er keine zutreffende Lösung ermitteln kann. Am Beispiel des Hamiltonkreisproblems wird eine Abfolge s ermittelt, die einen Kreis über alle Knoten hinweg bildet. Diese könnte einen Hamiltonschen Kreis abbilden. Die Laufzeit der eingegeben Daten s ist polynomial. Abschließend muss geprüft werden, ob s das Hamiltonkreisproblem tatsächlich löst, oder nicht. Diese Art von Problem, die nicht einfach in polynomialer Zeit „P“ gelöst werden können, gehörten der nichtdeterministisch polynomialen „NP“ Klasse an.

Da noch keine Beweisführung vorliegt, wird vermutet, dass P Ψ NP. Um zu zeigen, dass ein Entscheidungsproblem „A“ NP-vollständig ist, wird die Probleminstanz eines anderen Entscheidungsproblems „B“, welches NP-vollständig ist, auf Problem „A“ reduziert. Ein Algorithmus, der Problem „A“ löst, kann auch als Lösungsalgorithmus für Problem „B“ genutzt werden (vgl. Cormen et al., 2010). Über diese Polynomialreduktion hinaus muss das Entscheidungsproblem A G NP sein. Das euklidische STSP erfüllt als Entscheidungsproblem die NP-Vollständigkeit, das Optimierungsproblem erfüllt diese jedoch nicht. Daher ist das STSP nicht NP- vollständig, sondern wird als NP-schweres Problem bezeichnet (Johnson und Papadimitriou, 1985a).

3. Heuristische Verfahren

Im folgenden Kapitel wird aufgrund der gewonnen Kenntnisse über die Problemschwere eine Auswahl von deterministischen Konstruktionsheuristiken bezüglich ihrer Anwendungsflexibilität, individueller Stärken- und Schwächenanalysen, ihrer Laufzeitkomplexität und ihrer Lösungsgüte verglichen. Im Anschluss daran wird jede Konstruktionsheuristik an einer einheitlichen Probleminstanz I angewendet, sodass die Optimierungsergebnisse untereinander hinsichtlich der analysierten Maßstäbe vergleichbar sind. Fortführend folgt eine Übersicht von Verbesserungsverfahren, die in ihrer Funktionsweise beschrieben und illustriert werden, wobei anhand des 2-opt Verfahren die verschiedenen konstruierten Touren der Beispielinstanz I weiter verbessert und anschließend wieder miteinander verglichen werden.

3.1 Konstruktionsheuristiken

Wegen der AP-Schwere des TSP, ließe sich die optimale Kombinatorik einer Rundreise nur ineffizient, also abhängig der Probleminstanz mit hohem Zeitaufwand, bestimmen. Häufig werden daher Heuristiken zum Lösen des TSP praktisch angewendet. Diese bieten eine Annäherung des optimalen Zielfunktionswertes der Problemstellung. Diese lassen sich in zwei Kategorien, den Konstruktions- und Verbesserungsheuristiken, unterteilen.

Um eine erste Rundreise zu ermitteln, können verschiedene Algorithmen angewendet werden. Diese werden als Konstruktions- oder Eröffnungsheuristiken bezeichnet und können deterministisch oder stochastisch sein. Diese beiden Arten von Heuristiken unterscheiden sich darin, dass deterministische Verfahren angewendet auf eine Instanz I stets dieselbe Lösung generieren und stochastische Algorithmen bei mehrfacher Anwendung meist zu unterschiedliche Ergebnisse erzielen (vgl. Domschke und Scholl, 2010). In der Regel werden durch diese Heuristiken keine optimalen Touren berechnet, sondern stellen lediglich zulässige Lösungen des TSP dar (vgl. Golden und Stewart, 1985). Wie nah sich eine zulässige Lösung am Optimum befindet, ist von der angewendeten Heuristik und dem Startpunkt der Kombinierung abhängig (vgl. Vahrenkamp, 2003).

Die Annäherungsalgorithmen werden anhand von fünf Aspekten untersucht. Zwei dieser Kriterien sind die im schlechtesten Fall anzunehmende Laufzeitkomplexität O(Ľ) und die Lösungsgüte, durch die das Verhältnis der ermittelten Tourlänge einer Heuristik zur optimalen Länge der Tour beschrieben wird. Diese Lösungsgüte wird anhand des Worst-Case-Szenarios definiert. Darüber hinaus werden die Konstruktionsalgorithmen individuell auf Stärken und Schwächen in ihrer Ausführung untersucht und ob diese flexibel für STSP und ATSP anwendbar sind. Abschließend werden die Eröffnungsverfahren bezüglich ihrer Abweichung vom Optimum der Instanz „dr13“^[9] anhand empirischer Forschungsergebnisse verglichen.

3.1.1 Nearest Neighbor Heuristik

Der Algorithmus des Nächsten Nachfolgers oder Nachbarn verfolgt einen simplen Ablauf. Gegeben eines willkürlich oder auch bewusst gewählten Startknotens v1 werden iterativ j = {2,..., n] weitere Knoten v, der Tour hinzugefügt, bis alle Knoten in die Rundreise eingebunden sind, also vn G V. Es wird jeweils der Knoten vj der Tour hinzugefügt, der die kürzeste Distanz zum zuletzt zugefügten Knoten Vj_1 aufweist. Der Algorithmus ist flexibel für STSP und ATSP mit einer geschätzten Zeitkomplexität 0(n2) anwendbar (vgl. Domschke und Scholl, 2010; vgl. Reinelt 1994).

Domschke und Scholl (2010) und Reinelt (1994) beschreiben die Prozedur des nächsten Nachbarn Heuristik zur Berechnung einer ersten Rundreise im STSP wie folgt:

Start Nächster Nachfolger

Abbildung in dieser Leseprobe nicht enthalten

Ende Nächste Nachfolger

Der dargestellte Pseudocode des Algorithmus ist folgendermaßen zu interpretieren. Zeile (1) wählt zufällig einen Knoten v1 aus und setzt die Länge F der Rundreise auf Null. Im zweiten Schritt wird die Iteration j exakt so häufig wiederholt, bis kein Knoten n der Tour mehr hinzugefugt werden kann. Abschnitt (2.1) ermittelt den Knoten Vj mit geringster Distanz zum vorherigen zugefügten Knoten Vj_t. Die bereits im Verlauf dieser Iteration der Tour hinzugefügten Knoten werden aus der Knotengesamtheit V ausgeschlossen, sodass diese bei der weiteren Berechnung der Tour nicht mehr berücksichtigt werden. Im darauffolgendem Verfahrensschritt (2.2) wird der eben ermittelte Knoten Vj der Kette von Knoten angefügt. Am Ende jeder Iteration (2.3) erhöht sich die Länge der Verkettung um die zugefügte Kante und speichert diesen für den darauffolgenden Durchlauf. Abschließend wird in Schritt (3) der letzte zugefügte Knoten Vj mit dem Startknoten vt über eine Kante verbunden, sodass aus der Knotenverkettung eine zulässige Rundreise wird. Die Länge der Tour passt sich dementsprechend an.

Abbildung 3.1 soll das Ablaufschema des Nächsten Nachfolgers noch einmal verdeutlichen. In diesem Beispiel dient Knoten A als Startknoten. Die erste Iteration berechnet, dass Knoten E die geringste Distanz^[10] zum Startknoten aufweist und wird folgerichtig mit der Kante eae verbunden. In der zweiten Iteration ist Knoten C der nächste zu seinem Vorgängerknoten E und wird der Kette hinzugefügt. Die dritte und vierte Wiederholung dieses Verfahrensschrittes wird analog zu den ersten Beiden durchgeführt. Nach vier Iterationen sind alle Knoten dieser Instanz im Sinne einer Kette verbunden. Abschließend wird die Kette zu einer Rundreise geschlossen, indem der zuletzt zugefügte Knoten D mit dem Startknoten A verbunden wird. Die Reihenfolge der Tour ist demnach [A,E,C,B,D,A] mit einer Gesamtlänge von 15,62.^[11]

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3.1: Illustrative Anwendung des Nearest Neighbor Algorithmus.

Johnson und Papadimitriou (1985b) erläutern eine offensichtliche Schwäche des Nearest Neighbor Algorithmus. Diese spiegelt sich auch in Abbildung 3.1 wider. Obwohl im Ablauf der Heuristik stets die noch verfügbaren Knoten mit minimaler Distanz der Tour hinzugefügt werden, ist es möglich, dass die letzte Kante, welche die Tour schließt, nicht minimal sondern sehr lang ist. In Abbildung 3.1 wird dieser Nachteil durch die Kante eda deutlich. Die Distanzmatrix^[12] zeigt, dass von allen möglichen Entfernungen zwischen zwei Knoten die Distanz cda = 5,59 die längste von allen ist. Variiert der Startknoten beispielsweise von A zu B, ergibt sich eine von [A,E,C,B,D,A] abweichende Abfolge [B,A,E,C,D,B] der zu bereisenden Knoten mit einer geringeren Gesamtlänge von 12,45.^[13] Die Qualität der Optimierung ist also von der Wahl des Startknotens abhängig. Allerdings handelt es sich bei diesem Algorithmus um ein simples, leicht nachzuvollziehendes Prinzip (vgl. Vahrenkamp und Mattfeld, 2007).

[...]

---

^[1] Zu dt. „Tabu Suche“.

^[2] Ein geometrische Körper mit zwölf gleichgroßen Fünfecken als Flächen, 20 Ecken und 30 gleich langen Kanten.

^[3] Abbildung 2.1 und 2.2 sind auf Grundlage der im Text erlangten Erkenntnisse entstanden.

^[4] Auch Digraph genannt, was sich aus dem englischen Terminus „directed graph“ übersetzen lässt (vgl. Reinelt, S.5, 1994).

^[5] Im englischen auch „undirected graph“ (vgl. Reinelt, S.4, 1994).

^[6] Zusammenhang in Verbindung mit einem Graphen bedeutet, dass sich zwei zufällig ausgewählte Knoten i und j G V über eine Kantenabfolge, auch über andere Knoten hinweg, verbinden lassen (Vahrenkamp und Mattfeld, S.13, 2007).

^[7] Engl. „sub tour elimination constraint“ ( vgl. Goetschalckx, S.220, 2011).

^[8] Anders als hier werden im Verlauf dieser Ausarbeitung die Laufzeitfunktionen mit der Variable n statt mit e für eine Probleminstanz angegeben.

^[9] Siehe TSP-Instanz dr13 und deren optimale Rundreise in Anhang 7.

^[10] Siehe Tabelle A.1 für Knotenkoordinaten und die daraus resultierende Distanzmatrix.

^[11] Siehe Berechnung (Startknoten A) im Anhang 1.

^[12] Siehe Tabelle A.1 im Anhang 1.

^[13] Siehe Berechnung (Startknoten B) im Anhang 1.