Inhaltsviv Zeitaufw and b ei Einsatz einer Kandidatenmenge Laufzeit f ur die Berec hn ung v on...

Traveling Salesman Problemmit Iteriertem Matching

Frank Lauxtermann

Diplomarbeit im Studiengang Diplom Mathematikan der Universit�at Osnabr�uck

im Fachbereich Mathematik�Informatik

vorgelegt beiProfessor Dr� Oliver Vornberger

am �� M�arz ��

vonFrank LauxtermannBonhoe�erstra�e �� Osnabr�uck

Inhaltsverzeichnis

� De�nition �� Das Traveling Salesman Problem � � � � � � � � � � � � � � � � � � � � � � � �� Komplexit�at von Algorithmen � � � � � � � � � � � � � � � � � � � � � � � � � �

�� Die O�Notation � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Die Klassen P und NP � � � � � � � � � � � � � � � � � � � � � � � � �

�� Testinstanzen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� Das TSP in der Praxis �� Platinenproduktion � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Auftrags�Abarbeitung in einem Lagerhaus � � � � � � � � � � � � � � � � � � �� Kristall�Analyse � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Zuschneiden von Tapeten � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Gruppierung von Datenfeldern � � � � � � � � � � � � � � � � � � � � � � � � � � �� Verwaltung eines Fuhrparks � � � � � � � � � � � � � � � � � � � � � � � � � � �

� Bekannte L�osungsstrategien �� Kandidatenmengen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� N�achste Nachbarn � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Delaunay Graph � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Konstruktive Heuristiken � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Nearest�Neighbour Heuristik � � � � � � � � � � � � � � � � � � � � � � �� Insertion Heuristiken � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Doubletree�Heuristik � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Verfahren von Christo�des � � � � � � � � � � � � � � � � � � � � � � � �� Savings Heuristik � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Greedy Algorithmus � � � � � � � � � � � � � � � � � � � � � � � � � � ��

� Iterative Verfahren � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Node und Edge Insertion � � � � � � � � � � � � � � � � � � � � � � � � � � �� Opt Verfahren � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Lin�Kernighan�Heuristiken � � � � � � � � � � � � � � � � � � � � � � � � � � Simulated Annealing� Genetische Algorithmen � � � � � � � � � � � � �

i

INHALTSVERZEICHNIS ii

� Eine Heuristik mit iteriertem Matching �� Begri�sde�nitionen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Skizze des L�osungsalgorithmus � � � � � � � � � � � � � � � � � � � � � � � � � �� Darstellung einer L�osung � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Speichern mehrerer Wege � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Wahl der Bene�tfunktion � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Einsatz von Kandidatenmengen � � � � � � � � � � � � � � � � � � � � � � � � �� Zusammenfassen zweier Knoten � � � � � � � � � � � � � � � � � � � � � � � � � Vor� und Nachbereitung des Matchings � � � � � � � � � � � � � � � � � � � � ��

�� Berechnung des Pre�Bene�ts � � � � � � � � � � � � � � � � � � � � � � �� Kandidatenmengen auf echten Clustergraphen � � � � � � � � � � � � �

�� Artikulationskanten � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Zusammenfassende Beschreibung des Algorithmus � � � � � � � � � � � � � � ��

� Ergebnisse und Vergleich �� Ein�u� der Parameter auf die Ergebnisse � � � � � � � � � � � � � � � � � � � ��

�� Einsatz der Kandidatenmengen � � � � � � � � � � � � � � � � � � � � �� Wahl der Bene�tfunktion � � � � � � � � � � � � � � � � � � � � � � � � �� Ein�u� der Bene�t�Optionen � � � � � � � � � � � � � � � � � � � � � � �� Ein�u� der Selektion � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Ergebnisse im Vergleich zu anderen Heuristiken � � � � � � � � � � � � � � � ��

� Beschreibung der Benutzerober��ache �� Men�uf�uhrung � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Darstellung des Graphen und der L�osung � � � � � � � � � � � � � � � � � � � �� Einstellung der Parameter � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Abfrage statistischer Daten � � � � � � � � � � � � � � � � � � � � � � � � � � ��

Zusammenfassung und Ausblick

Literaturverzeichnis �

Danksagung �

Erkl�arung �

Abbildungsverzeichnis

�� Zwei verschiedene optimale L�osungen f�ur ein Problem � � � � � � � � � � � � �� Transformation eines asymmetrischen in einen symmetrischen Graphen � � �

�� Zuschneiden von Tapeten � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Gruppierung von Datenfeldern � � � � � � � � � � � � � � � � � � � � � � � � � �

�� Ein ��Nearest�Neighbour Teilgraph � � � � � � � � � � � � � � � � � � � � � � � �� Voronoi Diagramm und Delaunay Triangulation � � � � � � � � � � � � � � � �� Ein Delaunay Graph � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Vereinigung eines Delaunay Graphen und eines ��Nearest�Neighbour Teil�

graphen � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Laufzeit f�ur die Berechnung von ��Nearest�Neighbour Teilgraphen � � � � �� Minimaler Spannbaum � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Illustration der Savings Heuristik � � � � � � � � � � � � � � � � � � � � � � � �� Node� und Edge Insertion � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Opt Schritt � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Illustration eines Lin�Kernighan Schrittes � � � � � � � � � � � � � � � � � � � �

�� Vergleich Maximales und Maximum Weight Matching � � � � � � � � � � � � �� Speichern mehrerer Touren � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Artikulationskante � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � Einfache Darstellung einer L�osung als Baum � � � � � � � � � � � � � � � � � �� Ausf�uhrliche Darstellung eines L�osungsbaumes � � � � � � � � � � � � � � � � �� Ermittlung des Pre�Bene�ts � � � � � � � � � � � � � � � � � � � � � � � � � � �� Einf�uhrung einer Mindestqualit�at � � � � � � � � � � � � � � � � � � � � � � � � Berechnung des Bene�ts unter globalen und lokalen Gesichtspunkten � � � �� Ubergang von Pre�Bene�ts zu Bene�ts � � � � � � � � � � � � � � � � � � � � �� Einsatz von Kandidatenmengen � � � � � � � � � � � � � � � � � � � � � � � � �� Laufzeiten eines Matchings mit und ohne Kandidatenmengen � � � � � � � � �� Nutzen der Schwerpunkte in geometrischen Graphen � � � � � � � � � � � � �� Kombination zweier Touren f�uhrt zu billigerer neuer Tour � � � � � � � � � � �� Erweiterter Bin�arer Suchbaum � � � � � � � � � � � � � � � � � � � � � � � � � �� Transformation der Kandidatenmenge auf neuen Clustergraphen � � � � � � �� Suche nach Artikulationskanten � � � � � � � � � � � � � � � � � � � � � � � � ��

iii

ABBILDUNGSVERZEICHNIS iv

�� Zeitaufwand bei Einsatz einer Kandidatenmenge � � � � � � � � � � � � � � � �� Laufzeit f�ur die Berechnung von Kandidatenmengen � � � � � � � � � � � � � � �� Abh�angigkeit der L�osungsqualit�at von der Wahl der Bene�tfunktion � � � � �� Laufzeiten bei verschiedenen Bene�tfunktionen � � � � � � � � � � � � � � � � �� L�osungsqualit�at in Abh�angigkeit vom globalen Ein�u� � � � � � � � � � � � �� Abh�angigkeit der L�osungsqualit�at vom Referenzfaktor � � � � � � � � � � � � �� Abh�angigkeit der L�osungsqualit�at von der Mindestqualit�at � � � � � � � � � �� L�osungsqualit�at in Abh�angigkeit von der Selektionsrate � � � � � � � � � � � �� Laufzeit in Abh�angigkeit von der Selektionsrate � � � � � � � � � � � � � � � �� Vergleich der Laufzeiten der Savings�Heuristik und des Iterierten Matchings ��

�� Die Benutzerober��ache � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Dialog

�Parametereinstellung� � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Dialog�Kandidatenmenge� � � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Ausgabe statistischer Daten � � � � � � � � � � � � � � � � � � � � � � � � � � ��

Tabellenverzeichnis

�� Beispielinstanzen f�ur das TSP � � � � � � � � � � � � � � � � � � � � � � � � � ��

�� Konstruktion einer Tour � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

�� Qualit�at der L�osungen bei Einsatz einer Kandidatenmenge � � � � � � � � � � �� Qualit�atsvergleich mit anderen Heuristiken � � � � � � � � � � � � � � � � � � ��

v

Einleitung

Wohl jeder Mensch hat sich schon einmal � bewu�t oder unbewu�t � mit dem TravelingSalesman Problem �TSP� besch�aftigt� Es ist gleichzeitig ein sehr allt�agliches wie mathema�tisch schwer l�osbares Problem� Es geht darum� eine Rundreise durch eine gegebene Mengevon Orten zu �nden� bei der jeder Ort genau einmal besucht wird und die Streckenl�angeminimal ist� Anwendungen �nden sich nicht nur f�ur den dem Problem den Namen geben�den Handlungsreisenden� sondern auch f�ur Platinenhersteller� in der Textilindustrie und inder Kristallographie� um nur eine kleine Auswahl zu nennen�

Das TSP geh�ort zu der Klasse der Optimierungsprobleme� Ein Optimierungsproblem istcharakterisiert durch eine Menge von Variablen� einigen Bedingungen und einer Zielfunkti�on� Letztere gilt es zu minimieren� wobei die Bedingungen� die den m�oglichenWertebereichder Variablen einschr�anken� einzuhalten sind� Das TSP ist wohl der bekannteste Vertreterder Optimierungsprobleme�

Wie bereits angedeutet� geh�ort das Traveling Salesman Problem zu den mathematischschwierigsten Problemen� es ist NP�schwierig� Das bedeutet� da� im allgemeinen eine ex�akte L�osung nicht oder nur mit nicht vertretbarem Aufwand zu �nden ist� Daher versuchtman� sich mit Heuristiken zu helfen� die in deutlich geringerer Laufzeit recht gute N�ahe�rungsl�osungen berechnen� Die L�osungsqualit�at solcher Verfahren ist meistens umgekehrtproportional zur Laufzeit� In kurzer Rechenzeit sind meist nur relativ schlechte N�ahe�rungsl�osungen zu �nden�

Obwohl viel Energie in die Suche nach e�zienten Heuristiken f�ur das TSP gesteckt wurde�werden immer noch neue Erfolge auf diesem Gebiet erzielt� Zum einen erlaubt die wachsen�de Leistung moderner Computer die Implementierung von Algorithmen� deren Umsetzungbisher an praktischen Grenzen �zu wenig Speicherplatz� mangelnde Rechenleistung� schei�terten� Es werden aber auch neue Verfahren entwickelt oder aus anderen Einsatzgebietenauf das TSP �ubertragen�

Auch diese Arbeit stellt eine neue Heuristik vor� Sie basiert auf Iteriertem Matching� einemVerfahren� welches bereits bei der Anwendung auf zweidimensionale Packprobleme guteErgebnisse lieferte� Die Idee besteht darin� die Menge von Orten durch Zusammenfassensukzessive zu verkleinern� Dazu werden geeignete Ortspaare gebildet� Allgemein bedeutet

�

Einleitung �

�geeignet� so viel wie

�nah beieinander�� Diese Ortspaare werden dann wie ein einzelner

neuer Ort aufgefa�t�

Durch diese Ma�nahme ist das Problem auf die Suche einer Tour durch eine etwa halb sogro�e Anzahl von Orten reduziert� Zu jedem dieser Orte werden Wege durch die Teilortegespeichert� aus denen sie bestehen� Wird das Verfahren nun wiederholt auf die immergr�o�er werdenden Orte angewandt� so m�ussen am Ende nur noch die Wege der letztenbeiden Orte verbunden werden� Es entsteht eine Tour durch alle Orte des urspr�unglichenProblems�

In Kapitel � werden die wichtigsten Grundlagen der Graphentheorie und zur Komplexit�atvon Problemen und Algorithmen vorgestellt� Au�erdem werden Testinstanzen vorgestellt�anhand derer das hier erl�auterte Verfahren getestet werden soll� In Kapitel � werden Pro�bleme aus der Praxis beschrieben� die mit Hilfe von TSP�Heuristiken zu l�osen sind� Kapitel fa�t eine Reihe von Verfahren f�ur das TSP zusammen� Sie dienen als Grundlage f�ur einenVergleich mit der neuen Heuristik� Diese wird in den Kapiteln und � ausf�uhrlich beschrie�ben� Im ersten Teil werden die einzelnen Schritte des Verfahrens erl�autert� im zweiten danndie Ergebnisse aufgezeigt�

Um die Suche nach einer L�osung verfolgen zu k�onnen� wurde neben einer rein textorien�tierten Fassung des Programms auch eine gra�sche Benutzerober��ache implementiert� IhreM�oglichkeiten werden in Kapitel � dargelegt� Eine zusammenfassende Betrachtung bildetneben einem Ausblick den Abschlu� dieser Arbeit�

Kapitel �

De�nition

Dieses Kapitel soll die wichtigsten Begri�e aus der Graphentheorie und der Optimierungeinf�uhren� sowie eine formale De�nition des Traveling Salesman Problems vorstellen�Wich�tige Grundlagen f�ur die Analyse der Komplexit�at von Algorithmen bilden einen weiterenAbschnitt� Abschlie�end werden Probleminstanzen vorgestellt� anhand derer das in dieserArbeit erl�auterte Verfahren getestet werden soll�

�� Das Traveling Salesman Problem

Das Traveling Salesman Problem �ndet man sowohl in der Graphentheorie als auch in derkombinatorischen Optimierung� Dementsprechend gibt es viele� selbstverst�andlich �aqui�valente De�nitionen� Hier soll eine graphentheoretische Formulierung vorgestellt werden�Dazu bedarf es jedoch einiger anderer De�nitionen vorweg�

Zuerst sollen die wichtigsten Begri�e aus der Graphentheorie eingef�uhrt werden� Ein �un�gerichteter oder symmetrischer� Graph G � �V�E� besteht aus einer endlichen Menge vonKnoten V und Kanten E� Eine Kante e � E hat zwei Endknoten u� v � V � Sie wird daherauch mit e � uv oder e � �u� v� bezeichnet� In diesem Fall hei�t es auch� e inzidiert mitu und v� Die Anzahl aller mit u inzidierenden Kanten hei�t der Grad von u� Ein Graphhei�t gerichtet oder asymmetrisch� wenn die Kanten �u� v� und �v� u� nicht identisch sind�

In einem gewichteten Graphen sind den Kanten Gewichte oder Kosten zugeordnet� DieKosten einer Kante uv werden mit cuv� die Kosten einer Kantenmenge F � E mitc�F � �

P�u�v��F cuv bezeichnet� Sind den Kanten keine Kosten zugeordnet� hei�t der Graph

ungewichtet�

Ein Graph hei�t vollst�andig� wenn er f�ur jedes Knotenpaar u� v � V die Kante �u� v� � E

enth�alt� Ein vollst�andiger Graph auf n Knoten wird auch durch Kn bezeichnet� Ein Graph

Kapitel � De�nition

G� � �V �� E�� hei�t Teilgraph vonG� wenn V � � V und E� � E� EinWeg ist eineMenge vonKanten fv�v�� v�v�� vkgmit vi �� vj wenn i �� j und �vi� vi�� E f�ur alle i � �� k��gilt� Ein Graph hei�t zusammenh�angend� wenn es einen Weg zwischen jedem u und v ausV gibt� Eine Zusammenhangskomponente ist ein zusammenh�angender Teilgraph von G�

Die folgenden De�nitionen beziehen sich auf ungerichtete� gewichtete Graphen�

De�nition �� Zyklus � Ein Menge von Kanten C � fv�v�� v�v�� vkv�g hei�t Zyklusder L�ange k oder k�Zyklus� wenn vi �� vj f�ur i �� j� Abgek�urzt schreibt man auch C ��v�� v�� vk�� Ein Graph hei�t nicht�zyklisch� wenn er keinen Zyklus enth�alt�

De�nition �� Hamilton�Tour � Ein Zyklus der L�ange n in einem Graphen mit nKnoten hei�t Hamilton�Tour� Die Kosten eine Hamilton�Tour T sind de�niert durchc�T � �

P�u�v��T cuv�

Selbstverst�andlich gibt es Graphen� auf denen es keine Hamilton�Touren gibt� Diese sindaber in der Praxis ohne gro�e Bedeutung� Besonders interessant dagegen sind vollst�andigeGraphen� deren Knoten Punkte in einer Ebene repr�asentieren und deren Kantengewichtesich durch metrische Funktionen �Abst�ande� berechnen lassen� In diesen existieren immerHamilton�Touren� Sie seien im folgenden geometrische Graphen genannt�

Ein spezieller Zyklus auf einem vollst�andigen Graphen ist die konvexe H�ulle�

De�nition �� Konvexe H�ulle � Eine Menge W � R� hei�t konvex� wenn f�ur zwei

Punkte x� y � W auch �x� y� � W gilt� Die konvexe H�ulle einer endlichen Teilmenge S �fx�� xng � R

� ist die kleinste konvexe Menge HS � R�� f�ur die gilt xi � HS f�ur alle

xi � S�

De�nition �� Symmetrisches Traveling Salesman Problem � Gegeben sei dervollst�andige Graph Kn� Das �Symmetrische� Traveling Salesman Problem besteht darin�auf diesem Graphen eine Hamilton�Tour zu �nden� deren Kosten minimal sind� also eineHamilton�Tour Tmin� f�ur die gilt c�Tmin� � minT ist Hamilton�Tour c�T ��

Man beachte� da� es in der Regel keine eindeutige L�osung dieses Problems gibt� Abbildung�� zeigt ein Beispiel�

Die L�osungssuche f�ur ein TSP auf einem nicht vollst�andigen� aber symmetrischen GraphenG � �V�E� kann auf einem vollst�andigen Graphen simuliert werden� Dazu werden einfachalle fehlenden Kanten eingef�ugt� wobei ihre Gewichte sehr hoch gesetzt werden� beispiels�weise auf

P�i�j��E cij� Wird nun eine optimale L�osung dieses Problems gefunden� in der

eine dieser eingef�ugten Kanten auftritt� so gibt es keinen Hamilton�Zyklus im originalenProblem� Ansonsten ist die optimale L�osung auch f�ur das originale Problem g�ultig�

Ist der Graph G � �V�E� mit den Kantengewichten cij asymmetrisch� gibt es also Kanten�i� j� und �j� i� mit cij �� cji� hilft man sich mit einem �ahnlichen Trick� Man erstellt einen

Kapitel � De�nition �

Abbildung �� Zwei verschiedene optimale L�osungen f�ur ein Problem

C D

A B1

4

567

8

2

9

103

11

12

A’ B

C D’

1

2

3

4

5

9

10

11

12

7

-90

8

-90

-90

-90

C’

A

6

B’

D

Abbildung �� Ein asymmetrischer Graph �links� und seine Transformation ineinen symmetrischen Graphen �rechts��

neuen Graphen �G dessen Knotenmenge �V zus�atzlich zu den Knoten aus V � f�� ngn � jV j weitere Knoten �� n enth�alt� Ein Knoten �� hei�e Spiegelknoten zu i� AlsKantenmenge nimmt man �E � f�i�� i � �� ng � f�� j� � �i� j� � Eg� Man kommtalso von einem Originalknoten immer nur zu einem Spiegelknoten und umgekehrt� DieKantengewichte werden mit �ci�� M f�ur i � �� n und �c��j � cij f�ur �i� j� � E

gew�ahlt� Dabei ist M ausreichend gro� zu w�ahlen� beispielsweise M �P

�i�j��E cij� Esist o�ensichtlich� da� f�ur jeden gerichteten Hamilton�Zyklus in G mit den Kosten c einungerichteter Hamilton�Zyklus mit den Kosten �c � c � nM existiert� Dazu geht maneinfach f�ur jede Kante �i� j� im Hamilton�Zyklus auf G den Weg �i��j�� auf �G� Au�erdemwird jede optimale Tour in �G alle Kanten mit dem Gewicht �M enthalten� Solch eine Tourkann man wieder zu einem gerichteten Hamilton�Zyklus in G wandeln� indem man einfachden oben genannten Schritt umgekehrt durchf�uhrt�


Das asymmetrische Traveling Salesman Problem und das TSP auf allgemeinen �nicht�vollst�andigen� Graphen lassen sich also durch einen Algorithmus f�ur das symmetrische TSPl�osen� Die folgenden Betrachtungen beschr�anken sich daher auf das symmetrische TravelingSalesman Problem� es sei denn� es wird ausdr�ucklich auf einen anderen Fall hingewiesen�

Nun geh�ort das TSP zu der Klasse der NP�schwierigen Optimierungsprobleme� F�ur dieselassen sich im allgemeinen keine exakten L�osungen �nden� beziehungsweise w�urde die Su�che danach zu gro�en Aufwand bedeuten� Nat�urlich werden auch mehr und mehr Verfahrenentwickelt� um optimale L�osungen f�ur das TSP zu �nden� doch ist es in der Praxis vongr�o�erem Interesse� m�oglichst schnell m�oglichst gute N�aherungen zu �nden� Wird im fol�genden von L�osungen gesprochen� so sind damit N�aherungsl�osungen gemeint� eine wirklicheL�osung des Problems �� wird dagegen von nun an

�optimale L�osung� genannt�

�� Komplexit�at von Algorithmen

Neben der Qualit�at einer N�aherungsl�osung spielt auch die ben�otigte Zeit eine erheblicheRolle bei der Beurteilung eines Algorithmus� So kann es beispielsweise sinnvoller sein� eineschlechtere L�osung in Kauf zu nehmen� als viele Stunden Rechenzeit zu investieren� Bei Al�gorithmen� die in jedem Fall exakte L�osungen liefern sollen� ist die Zeit das Hauptkriteriumf�ur ihre Beurteilung�

�� Die O�Notation

Selbstverst�andlich kann man keine Aussagen �uber die wirkliche Laufzeit eines Algorith�mus machen� da diese von der tats�achlichen Implementierung und der Plattform� auf derdiese l�auft� abh�angt� Im allgemeinen ist man aber auch mehr daran interessiert� Aussagen�uber das Verhalten bei wachsender Gr�o�e n der zu behandelnden Probleminstanzen zubekommen�

Die O�Notation gibt eine obere Schranke f�ur den Aufwand im ung�unstigsten Fall � worstcase genannt � an�

De�nition �� Gegeben seien f � N� N und g � N � N� Die Funktion f hei�t O�g�n��in ihrer Input�L�ange n �oder� hat den Aufwand O�g�n�� wenn positive Konstanten c undn� existieren� so da� � � f�n� � c � g�n� �n n��

Beispielsweise gibt es f�ur die Suche eines Maximums in einer unsortierten Menge von n

Zahlen Algorithmen� die dieses mit linearem Aufwand l�osen� Sie sind O�n��


Die Input�L�ange ist ein Ma� f�ur die Menge der Eingabedaten f�ur eine zu l�osende Pro�bleminstanz� Das Au�nden des Maximums von n Zahlen ben�otigt nur diese Zahlen alsEingabedaten� Die Input�L�ange betr�agt also n� Sucht man dagegen die Kante eines GraphenG � �V�E� mit den gr�o�ten Kosten� so ist die Input�L�ange die Anzahl der Kanten jEj�

Die O�Notation kann sowohl f�ur die Laufzeit als auch f�ur den Speicherplatzbedarf einesAlgorithmus benutzt werden� Wird im folgenden gesagt� ein Algorithmus habe einen Auf�wand O�g�n�� so ist grunds�atzlich der zeitliche Aufwand gemeint� Wird die Notation f�urden Speicherplatz gebraucht� wird dies ausdr�ucklich notiert� Au�erdem beziehen sich alleAussagen auf sequentielle Algorithmen�

Man ist nat�urlich daran interessiert� f�ur gegebene Probleme m�oglichst schnelle Algorith�men zu �nden� Daher gibt man nicht eine beliebige obere Schranke f�ur einen Algorithmusan� sondern �von Konstanten abgesehen� die kleinste� also die asymptotische Laufzeit desAlgorithmus� Beispielsweise ist der Quicksort�Algorithmus f�ur das Sortieren von n Zahlennicht nur O�n�� wie auch der Bubblesort� sondern O�n log n��

Bei der Suche nach dem schnellsten Algorithmus gibt es nat�urlich Grenzen� So gibt esbeispielsweise keinen Algorithmus� der das Sortieren mit geringeremAufwand alsO�n log n�l�ost� Es ist sinnvoll� die O�Notation auch auf Probleme zu �ubertragen�

De�nition �� Gegeben sei g � N � N� Ein Problem l�a�t sich in O�g� l�osen� wenn eseinen Algorithmus gibt� der beliebige Probleminstanzen in O�g� l�ost�

Von einem AlgorithmusA� f�ur den ein Polynom p existiert� so da� A den Aufwand O�p�n��hat� sagt man� er habe polynomialen Aufwand beziehungsweise er ist polynomiell� Alleanderen Algorithmen haben exponentiellen Aufwand �sind exponentiell��

�� Die Klassen P und NP

Bei der Untersuchung der Probleme auf ihre Komplexit�at werden zwei Klassen unterschie�den� Zum einen gibt es die Entscheidungsprobleme� deren L�osung

�Ja� oder

�Nein� lautet�

zum anderen dieOptimierungsprobleme� Ein Optimierungsproblem ist charakterisiert durcheine Menge von Variablen� durch Bedingungen� die den Wertebereich dieser Variablen ein�schr�anken und durch eine Zielfunktion� die unter Beachtung der Bedingungen minimiertwerden soll�

De�nition �� Die Klasse P bezeichne die Menge aller Entscheidungsprobleme� die mitpolynomialem Aufwand l�osbar sind�

Die meisten interessanten Probleme aus der kombinatorischen Optimierung geh�oren zurKlasse NP P� Sie lassen sich bisher nicht mit polynomialem Aufwand l�osen� Es ist sehrwahrscheinlich� da� dieses auch gar nicht m�oglich ist�

Kapitel � De�nition

Die De�nition der Klasse NP kann mit Hilfe der nicht�deterministischen Turing Maschinegeschehen� An dieser Stelle soll keine vollst�andige De�nition der Turing Maschine gegebenwerden� F�ur das Verst�andnis der Klasse NP gen�ugt es� sich die nicht�deterministischeTuring Maschine als ein theoretisches Werkzeug vorzustellen� das die �ublichen Algorithmenverarbeiten kann� aber noch einen weiteren Befehl erlaubt� Dieser Befehl erm�oglicht es� zweiverschiedene Abschnitte eines Algorithmus gleichzeitig auszuf�uhren� Liefert ein Abschnittdes Algorithmus f�ur eine Instanz eines gegebenen Entscheidungsproblems die Antwort

�Ja��

dann wird die Instanz mit�Ja� beantwortet und die Abarbeitung des Algorithmus beendet�

Nur wenn kein Abschnitt�Ja� liefert� lautet die Antwort f�ur die Instanz

�Nein��

De�nition �� F�ur ein Entscheidungsproblem P gilt genau dann P � NP� wenn dienicht�deterministische Turing Maschine f�ur jede beliebige Instanz des Problems die richtigeAntwort liefert und sie f�ur jede

�Ja��Antwort polynomialen Aufwand ben�otigt�

Da die nicht�deterministische Turing Maschine auch deterministische Algorithmen verar�beiten kann� gilt P � NP� Bisher konnte aber weder P �� NP noch P � NP bewiesenwerden� Es gibt gute Gr�unde daf�ur� da� P eine echte Teilmenge ist� Schlie�lich hat manf�ur eine Vielzahl von Problemen nur Algorithmen exponentiellen Aufwands gefunden�

De�nition �� Polynomielle Reduzierbarkeit � Ein ProblemA hei�t polynomiell re�duzierbar auf ein Problem B� wenn es einen polynomiellen Algorithmus f�ur A gibt� der dieL�osung von B als Teilschritt benutzt� Jeder Aufruf des Algorithmus f�ur B z�ahlt dabei alsein Schritt� unabh�angig von dem tats�achlich notwendigen Aufwand�

De�nition �� NP�Vollst�andigkeit � Ein Entscheidungsproblem P hei�t NP�vollst�andig� wenn einerseits P � NP und andererseits jedes Problem aus NP polynomiellreduzierbar auf P ist�

Mit anderen Worten� Wird f�ur ein NP�vollst�andiges Problem ein polynomieller Algorith�mus gefunden� so sind automatisch alle NP�vollst�andigen Probleme mit polynomialemAufwand l�osbar und es w�urde P � NP gelten� Da viele Forscher f�ur die unterschied�lichsten dieser Probleme vergeblich nach polynomiellen Algorithmen gesucht haben� wirdangenommen� da� dem nicht so ist� Der Beweis ist aber � wie schon erw�ahnt � nochnicht erbracht�

Bisher wurden nur Theorien f�ur Entscheidungsprobleme vorgestellt� Um Aussagen �uberdas TSP machen zu k�onnen� ben�otigt man analoge Aussagen f�ur Optimierungsprobleme�Diese gewinnt man� indem man jedem Optimierungsproblem ein Entscheidungsproblemzuordnet� Das Verfahren soll anhand des TSPs erl�autert werden�

De�nition �� Traveling Salesman Entscheidungsproblem � Gegeben sei derGraph G � �V�E�� und eine Zahl b� Das Traveling Salesman Entscheidungsproblem istdann die Frage� ob es einen Hamilton�Zyklus gibt� dessen Kosten maximal b sind�


Dieses Problem istNP�vollst�andig �Joh �� Ein Optimierungsproblem� dessen zugeh�ori�ges EntscheidungsproblemNP�vollst�andig ist� nennt man NP�schwierig� Das hei�t in die�sem Fall

Satz �� Das Traveling Salesman Problem ist NP�schwierig�

Mit Hilfe des Entscheidungsproblems kann man auch das Optimierungsproblem l�osen� Dazu�uberlegt man sich� da� eine Hamilton�Tour auf einem Graph G � �V�E� niemals teurerals U � cmax � n mit cmax � max�i�j��E jcijj und jV j � n sein kann� Ebenso wenig kann siebilliger als L � �cmax � n sein� Mit diesen beiden Werten als oberer und unterer Grenzebeginnt man eine bin�are Suche� Man l�ost also das Entscheidungsproblem f�ur b � L�U

��

verkleinert das Suchintervall je nach Ergebnis auf �L� b� oder �b� U � und wiederholt dieseSchritte� bis obere und untere Grenze des Suchintervalls zusammenfallen� Diese Grenze istdann der Wert bopt einer optimalen L�osung�

Mit Hilfe dieses Wertes kann man die optimale L�osung selbst bestimmen� Dazu erh�ohtman nach und nach die Kosten jeder Kante des Graphen auf U � �� uberpr�uft nach dieser�Anderung� ob es immer noch einen Hamilton�Zyklus mit den Kosten bopt gibt und machtdie �Anderung im negativen Fall r�uckg�angig� Alle nicht ge�anderten Kanten stellen dann eineoptimale L�osung dar�

Ist also ein Entscheidungsproblem in P� so ist auch das zugeh�orige Optimierungsproblempolynomiell l�osbar� denn das Verfahren zur Suche des Wertes der optimalen L�osung fragtO�log n� mal nach einer Antwort auf das Entscheidungsproblem� der Algorithmus zur Be�stimmung der L�osung selbst im Falle des TSP O�n�� mal�

Nun w�are man vielleicht zufrieden� g�abe es wenigstens einen Algorithmus� der in polynomia�ler Zeit eine L�osung mit den Kosten cH liefert� f�ur die gilt cH � r � copt� r �� Dann k�onnteman Verfahren implementieren� die mit polynomialem Aufwand gute N�aherungsl�osungenliefern� Leider ist auch das nicht m�oglich� wie in �Sah �� bewiesen wird�

�� Testinstanzen

Um einen Vergleich mit anderen Verfahren zu erm�oglichen� gibt es eine Reihe von Beispiel�instanzen� die gr�o�tenteils praktische Probleme repr�asentieren� In der TSPLIB �Rei ��von Gerhard Reinelt sind viele dieser Beispielinstanzen in einer einheitlichen Beschreibungverf�ugbar� Eine kleine Auswahl dieser Beispiele schl�agt Reinelt in �Rei �� vor� Sowohldas Beschreibungsformat als auch die Beispielinstanzen �Tabelle �� wurden hier �uber�nommen� In der Tabelle sind die Namen der Beispielinstanzen� ihre Gr�o�e �die Anzahl derKnoten� und die Kosten einer optimalen L�osung gegeben� Ist bisher noch keine optimaleL�osung gefunden worden� so sind die Grenzen angegeben� innerhalb derer sich die Kosteneiner solchen be�nden werden�

Kapitel � De�nition ��

Problem Gr�o�e Grenzkostend�� lin � � �� pcb� � ��u�� p�� rat� � ��pr�� u�� pcb�� d�� rl� � � � �� u� � � � �� d�� vm�� rl�� u�� pr� �� pcb � � � �� fnl�� rl��

Tabelle �� Beispielinstanzen f�ur das TSP mit den Kosten bzw� den Grenzender optimalen L�osungen

Bei den Beispielinstanzen handelt es sich ausnahmslos um geometrische Probleme� Dieszeigt die au�ergew�ohnliche Bedeutung dieser Gruppe� Auf eine Auswahl praxisnaher Pro�bleme wurde R�ucksicht genommen� da zuf�allige Instanzen kaum die Besonderheiten prak�tischer Anwendungen modellieren k�onnen�

Die Qualit�at eines Verfahrens wird bestimmt durch die L�osungen� die es liefert� Die L�osun�gen werden daher nicht in absoluten Zahlen� sondern mit Hilfe der Formel

q � ��

�cH

cL� �

�angegeben� Dabei sind cH die Kosten der durch die Heuristik gefundenen L�osung und cLdie Kosten der optimalen L�osung beziehungsweise die untere Grenze daf�ur�

Kapitel �

Das TSP in der Praxis

Die praktische Relevanz des TSP ist schon durch die De�nition einsichtig� Es gibt unz�ahligeVarianten des Problems� eine k�urzeste Tour durch eine vorgegebene Anzahl an Orten zu�nden� Doch es gibt auch noch andere Anwendungen� bei denen Heuristiken zum TSPsinnvoll und e�ektiv eingesetzt werden k�onnen� Einige Beispiele sollen an dieser Stelleaufgef�uhrt werden�

�� Platinenproduktion

Eine Standardanwendung f�ur TSP�Heuristiken ist das Bohren von Platinen� Um einenLeiter von einem Layer der Platine auf ein anderes zu f�uhren� oder um Bausteine auf derPlatine befestigen zu k�onnen� mu� in die Platine ein Loch gebohrt werden� Dabei k�onnenunterschiedliche Durchmesser erforderlich sein� Es ist klar� da� das Wechseln des Bohrerserheblich mehr Zeit erfordert� als das Bewegen des Bohrers und das Bohren an sich� Daherwird man alle L�ocher gleichen Durchmessers in einem Durchgang bohren und erst dannden Bohrer wechseln�

Nimmt man also die Ausgangsposition der Bohrmaschine sowie die Positionen aller L�ochereines Durchmessers als Knoten und die Zeit� die beim Bewegen des Bohrers von einer Po�sition zur n�achsten ben�otigt wird� als Kantengewichte� so hat man ein Traveling SalesmanProblem� von dem in diesem Fall mehrere nacheinander zu l�osen sind� Je eine L�osung stelltden k�urzesten Weg f�ur den Bohrer �uber alle L�ocher mit gleichem Durchmesser dar�

Doch schon vor der eigentlichen Produktion der Platine ist das TSP anwendbar� F�ur jedesLayer der Platine mu� eine Maske produziert werden� Diese wird im allgemeinen mit einemmechanischen Plotter erstellt� Auch die Steuerung dieses Ger�ates kann durch eines der imfolgenden vorgestellten Verfahren optimiert werden�

��

Kapitel � Das TSP in der Praxis ��

�� Auftrags�Abarbeitung in einem Lagerhaus

Aus einem Lager sei eine Menge unterschiedlicher Gegenst�ande zu besorgen� Dazu wird einFahrzeug durch die G�ange zu den einzelnen Regalen gefahren� das Material gesammelt undam Ende abgeliefert� Betrachtet man die Orte� an denen die Gegenst�ande gelagert sind�als Knoten eines Graphen und die Zeit� die von einem Ort zum n�achsten ben�otigt wird alsKantengewichte� so hat man ein Traveling Salesman Problem� Eine L�osung des Problemsstellt die zeitlich k�urzeste Tour f�ur das Fahrzeug dar� mit der alle Gegenst�ande besorgtwerden k�onnen�

�� Kristall�Analyse

Die Analyse von Kristallen kann durch die Messung unterschiedlicher Intensit�aten vonre�ektierten R�ontgenstrahlen geschehen� Dazu mu� eine entsprechende Apparatur zu meh�reren zehntausend Positionen bewegt werden� an der sie die Messungen durchf�uhren kann�Auch hier hat man mit den verschiedenen Positionen als Knoten und den Zeiten� dieben�otigt werden� um die Positionen anzusteuern� als Kantengewichte ein Traveling Sales�man Problem in drei Dimensionen vorliegen� Seine L�osung � also die zeitlich k�urzeste Tour

�uber alle Positionen � kann aufgrund der gro�en Zahl an Knoten erhebliche Zeitgewinnegegen�uber einer zuf�allig gew�ahlten Tour bedeuten�

�� Zuschneiden von Tapeten

Bisher sind nur Anwendungen aufgez�ahlt worden� bei denen die Analogie zum TravelingSalesman Problem o�ensichtlich war� Das Zuschneiden von Tapeten scheint dagegen kei�nerlei �Ahnlichkeit aufzuweisen�

Es seien n Bahnen einer Tapete von einer Rolle zuzuschneiden� Diese Tapete habe einMuster� dessen L�ange � sein soll� Das l�a�t sich mit geeigneter Skalierung immer erreichen�Die Bahn i soll nun an Position ai imMuster beginnen und an Position bi enden� � � ai� bi �� siehe Abb� �� Wird nun die Bahn j direkt nach Bahn i geschnitten� so entsteht einVerschnitt von

cij �

�aj � bi wenn bi � aj

� � aj � bi sonst

Legt man nun noch den Anfang der Rolle mit a� fest und verlangt man� da� abschlie�endnoch ein Schnitt gemacht wird� so da� die Rolle auch wieder bei b� � a� endet� so wirddie Aufgabe� den Gesamtverschnitt zu minimieren� zu einem TSP mit n � � Knoten und

Kapitel � Das TSP in der Praxis �

bi

ai

bi

ai

1

Bahn i

Abbildung �� Die Werte ai und bi bezeichnen den Anfang und das Ende einerTapetenbahn bez�uglich eines Musters

der Kostenmatrix �cij�� Die L�osung dieses Problems beschreibt die Reihenfolge� in der dieBahnen von der Rolle abzuschneiden sind�

�� Gruppierung von Datenfeldern

In vielen Bereichen gibt es Fragen nach dem gegenseitigen Ein�u� unterschiedlicher Fak�toren� Dazu kann man eine Matrix A � �aij� aufstellen� in der der Wert von aij ein Ma�f�ur den Ein�u� eines Faktors i auf einen Faktor j ist� Beispielsweise k�onnten die ZeilenMarketing Strategien darstellen� w�ahrend die Spalten Situationen kennzeichnen� in denendiese Strategien erfolgreich eingesetzt wurden�

Das Ziel ist es� die Zeilen und Spalten der Matrix so zu vertauschen� da� Abh�angigkei�ten von Teilmengen der Zeilen und Spalten klar sichtbar werden� In Abbildung �� wirdnach den Permutationen klar� da� zwischen den Zeilen �� und den Spalten �� starkeAbh�angigkeiten existieren� Das gleiche gilt f�ur die Zeilen �� und die Spalten �� Umdieses Ziel zu erreichen� wird ein E�ektivit�atsma� eines Permutationspaares E�� ein�gef�uhrt� Seien � und � Permutationen der Zeilen beziehungsweise der Spalten� Dann erh�altman die Summe der Produkte von benachbarten Elementen in einer m� n�Matrix durch

E�� mXi�

nXj�

a��i�ja��i��j �nX

j�

mXi�

ai��j�ai��j��

Kapitel � Das TSP in der Praxis �

��

�BBBB��

�CCCCA

� � �a�

� ��

�BBBB��

�CCCCA

� � �b�

Abbildung �� Gruppierung von Datenfeldern

wobei F�ullzeilen und �spalten zugef�ugt wurden� deren Elemente alle � sind� F�ur die Permu�tationen gilt ��m� �� n � �� Beide Summen k�onnen unabh�angigvoneinander optimiert werden� F�ur diese Optimierung werden zwei Traveling SalesmanProbleme gel�ost� eines mit der Kostenmatrix

cij � �nX

k�

aikajk

f�ur das Zeilenproblem und entsprechend eines mit der Kostenmatrix

�cij � �mXk�

akiakj

f�ur das Spaltenproblem� Die negativen Vorzeichen sind n�otig� um das ursp�ungliche Maxi�mierungsproblem auf ein Minimierungsproblem zu �uberf�uhren� Die L�osung der Problemebeschreibt die Reihenfolge� in der die Zeilen beziehungsweise die Spalten anzuordnen sind�Eine L�osung f�ur das in Abb� ��a� gezeigte Problem ist �wie in �b� zu sehen� �� f�urdas Zeilenproblem und �� f�ur das Spaltenproblem�

�� Verwaltung eines Fuhrparks

Bei der Verwaltung eines Fuhrparks hat man neben der Tatsache� da� man f�ur mehrereFahrzeuge optimale Routen �nden will� auch andere Erg�anzungen und Einschr�ankungendes TSP zu beachten� So hat beispielsweise jedes Fahrzeug nur eine bestimmte Kapazit�at�bei der Auslieferung m�ussen eventuell Termine eingehalten werden� Tank� und Raststopsm�ussen eingeplant werden� Desweiteren m�ussen manche Orte gegebenenfalls vor anderenangefahren werden� Solche Orte w�aren Depots� an denen die Ladung erst einmal aufge�nommen werden mu��

Kapitel � Das TSP in der Praxis ��

Das Vehicle Routing Problem umfa�t die meisten dieser Punkte� die anderen k�onnen durchgeschickte Modellierung aufgenommen werden� Gibt es keine zeitlichen Einschr�ankungenund ist die Zahl m der Fahrzeuge fest� so l�a�t sich das Vehicle Routing Problem als TSPl�osen� Dazu steht zun�achst jedes Fahrzeug an einem festgelegten Knoten n � �� JederKnoten des Graphen mu� von genau einem Fahrzeug genau einmal besucht werden� Manverbindet mit dem Einsatz eines Fahrzeuges i noch zus�atzliche Kosten wi� Dadurch werdenBetriebskosten simuliert� die unabh�angig von der Streckenl�ange beim Einsatz eines Fahr�zeuges entstehen� Die Aufgabe� unter allen m Fahrzeugen eine Teilmenge auszuw�ahlen�die alle St�adte unter den gegebenen Nebenbedingungen besucht� nennt man auch das m�Salesman Problem oder m�TSP� In �Bel �� wird eine Transformation des m�TSP in einasymmetrisches TSP vorgestellt�

Kapitel �

Bekannte L�osungsstrategien

Die zur L�osung des TSP eingesetzten Heuristiken lassen sich zwei Klassen zuordnen� Zumeinen gibt es die

�konstruktiven Verfahren�� die mit unterschiedlichen Strategien die Kno�

ten des Graphen nach und nach zu einer Tour verbinden� Sie werden vornehmlich eingesetzt�um m�oglichst schnell grobe N�aherungsl�osungen zu ermitteln� Die

�iterativen Verfahren��

die eine gegebene L�osung mit geeigneten Ver�anderungen verbessern� liefern dagegen bes�sere L�osungen� ben�otigen dazu allerdings auch mehr Zeit� Diese Gruppe von Heuristikenl�a�t sich noch einmal dadurch unterteilen� da� manche terminieren� wenn sie keine Verbes�serungsm�oglichkeiten mehr �nden� w�ahrend andere beliebig lange laufen k�onnen und diegefundenden N�aherungsl�osungen sich im allgemeinen immer mehr dem Optimum n�ahern�Wichtige Repr�asentanten dieser Gruppen sollen hier vorgestellt werden� Vorher sollen abernoch Ma�nahmen besprochen werden� die der Vorbereitung der L�osungssuche dienen�

�� Kandidatenmengen

Prinzipiell kann jedes Knotenpaar eines geometrischen Graphen in einer Hamilton�Tourbenachbart sein� Mit blo�em Auge erkennt man jedoch� da� es in vielen F�allen unvern�unf�tig w�are� zwei Knoten unmittelbar nacheinander zu besuchen� Man w�u�te von vornherein�da� es� sucht man einen Rundweg durch Deutschland� keinen Sinn macht� von Hamburgdirekt nach M�unchen zu reisen� Man versucht daher die Menge der zu betrachtenden Nach�folgeknoten einzuschr�anken� Bei geeigneter Wahl wird die L�osungsqualit�at nicht oder nurunwesentlich schlechter� die Laufzeit daf�ur bei einigen Verfahren erheblich geringer�

��

Kapitel � Bekannte L�osungsstrategien ��

�� N�achste Nachbarn

In vielen Problemen gen�ugt es� als Kandidaten f�ur Folgeknoten nur eine bestimmte Anzahlan n�achsten Nachbarn zu w�ahlen�

De�nition �� k�nearest�neighbour Teilgraph � Der k�nearest�neighbour TeilgraphN eines Graphen G � �V�E� auf n Knoten ist de�niert durch N � �V�EN� mit

EN � fuv � E � cuv � cuwk � wobei cuw�� cuwn f�ur alle uwi � Eg

Um diese Kandidatenmenge zu berechnen� ist im allgemeinen ein Aufwand von O�n�� zuleisten� Speziell f�ur Graphen� die die Dreiecksungleichung erf�ullen �cuv�cvw cuw �u� v� w �V �� kann jedoch mit Hilfe des Delaunay Graphen eine schnellere Variante implementiertwerden �siehe unten�� In Abbildung �� sieht man eine solche Kandidatenmenge� Leider gibtes F�alle� in denen der Graph nicht mehr zusammenh�angend ist� Dieser Fall tritt besondersdann auf� wenn der Graph aus mehreren Gruppen besteht� in denen die Knoten sehr dichtbeieinander liegen� die aber selbst deutlich voneinander getrennt sind� Dann �nden sichn�amlich die n�achsten Nachbarn eventuell ausschlie�lich unter den Knoten der gleichenGruppe�

F�ur gleichm�a�iger verteilte Knoten ist diese Wahl� die einen sehr d�unn besetzten Graphenerzeugt und daher f�ur gute Laufzeiten sorgt� jedoch sehr hilfreich� Auf der Probleminstanzpr�� ndet sich eine optimale L�osung im �Nearest�Neighbour Teilgraph� auf der Instanzpcb� sogar im ��Nearest�Neighbour Teilgraph �Rei ��

�� Delaunay Graph

Der Delaunay Graph basiert auf der Delaunay Triangulation� dem dualen Diagrammzum Voronoi�Diagramm� F�ur einen zweidimensionalen� geometrischen Graphen stellt dasVoronoi�Diagramm eine Partitionierung der Ebene R� in Voronoi�Regionen

VR�v� �� fx � R� � d�x� v� � d�x� u� �u � V� u �� vg

dar� wobei d�x� y� eine metrische Funktion ist� In der Voronoi�Region eines Knotens v � V

sind also alle Punkte der Ebene enthalten� die n�aher an v als an irgendeinem anderenKnoten des Graphen liegen� Allgemein lautet die De�nition

De�nition �� Voronoi�Diagramm � Sei S � fP�� PNg eine endliche Teilmengeaus Rm und d � Rm�Rm �� R eine Metrik� Eine Voronoi Region VR�Pi� eines PunktesPi � S ist dann die Menge

VR�Pi� � fP � Rm � d�P�Pi� � d�P�Pj� �j � �� N� j �� ig�

Die Menge aller N Voronoi Regionen hei�t Voronoi Diagramm�

Kapitel � Bekannte L�osungsstrategien �

Abbildung �� Nearest�Neighbour Teilgraph auf Probleminstanz lin��

Die Delaunay�Triangulation ergibt sich aus dem Voronoi�Diagramm� indem man alle Kno�ten miteinander verbindet� deren Voronoi�Regionen aneinander grenzen�

De�nition �� Delaunay Triangulation � Gegeben sei das Voronoi Diagramm einerendlichen Teilmenge S � fP�� Png � R

m� Dann hei�t der ungerichtete Graph G ��S�D� mit

D � ffP�� P�g � VR�P�� VR�P�� g

Delaunay Triangulation�

Abbildung �� zeigt f�ur eine Menge von acht Punkten in R� das Voronoi�Diagramm und


Abbildung �� Das Voronoi�Diagramm f�ur eine Punktmenge aus acht Elemen�ten in R� �gestrichelte Linien� und die entsprechende Delaunay Triangulation�

die Delaunay Triangulation�

Mit Hilfe der Delaunay Triangulation erh�alt man eine gute Kandidatenmenge� indem manau�er den Kanten in D noch alle Kanten uw hinzuf�ugt� f�ur die es ein v � S gibt� so da�uv � D� vw � D� Diese Kandidatenmenge � sie soll Delaunay Graph hei�en � bietet sichbesonders f�ur stark geclustertete Graphen an� also Graphen bei denen an verschiedenenStellen H�aufungen von Knoten auftreten� Bei einer Nearest�Neighbour Kandidatenmen�ge entsteht dann das Problem� da� Kanten nur innerhalb dieser Cluster auftreten undwichtige Verbindungen zwischen den Clustern fehlen� In Abbildung � sieht man einesolche Kandidatenmenge� Der Graph ist sehr dicht und � was noch wichtiger ist � erist zusammenh�angend� Es ist sehr wahrscheinlich� da� eine optimale L�osung f�ur das ur�spr�ungliche Problem in diesem Teilgraphen zu �nden ist� Gute N�aherungsl�osungen �ndensich in jedem Fall� Um noch sicherer zu gehen� kann man die noch fehlenden Kanten auseinem Nearest�Neighbour Teilgraph hinzuf�ugen� Eine Kombination aus Delaunay Graphund ��Nearest�Neighbour Teilgraph zeigt Abbildung ��

Bereits angesprochen worden ist die M�oglichkeit� mit Hilfe der Delaunay Triangulationdie Berechnung der k�Nearest�Neighbour Kandidatenmenge f�ur geometrische Graphen zubeschleunigen� Dazu wird auf der Triangulation von jedem Knoten aus eine Breitensuchegestartet� die sich maximal k Schritte vom Startknoten entfernt� Es ist o�ensichtlich� da�sich alle k n�achsten Knoten unter den dabei besuchten be�nden� Zwar ist die worst�caseLaufzeit immer noch O�n�� jedoch sind in der Praxis lineare Abh�angigkeiten zu beobachten


Abbildung � � Delaunay Graph auf der Probleminstanz lin��

�Abb� �� Dabei gibt es allerdings gewisse Abh�angigkeiten von der Verteilung der Knotenin der Probleminstanz�

�� Konstruktive Heuristiken

Die Vorstellung der nun folgenden Verfahren dient nicht nur dazu� einen �Uberblick �uber dieForschung zu bekommen� Die Verfahren sollen sp�ater zum Vergleich mit der in dieser Ar�beit vorgestellten Heuristik herangezogen werden� Damit dieser Vergleich m�oglichst genau


Abbildung �� Vereinigung des Delaunay Graphs und des ��Nearest�Neighbour Teilgraphen auf lin��

ist� wurden alle Verfahren aus �Rei �� entnommen� Alle Ergebnisse� insbesondere dieQualit�aten der einzelnen Heuristiken� die in den folgenden Abschnitten angegeben werden�stammen aus dieser Quelle� Sie wurden unter identischen Bedingungen erzielt und k�onnensomit als Referenz herangezogen werden�


1000 1200 1400 1600 1800 200080060040020000

0.5

1.5

1

2

2.5

3

3.5

Zeit in Sekunden

Anzahl der Knoten

Abbildung �� Laufzeit f�ur die Berechnung eines ��Nearest�Neighbour Teil�graphen wenn die Delaunay�Triangulation bekannt ist�

�� Nearest�Neighbour Heuristik

Das wohl einfachste Verfahren zur L�osung des Traveling Salesman Problems ist die Nearest�Neighbour Heuristik� Hierbei wird mit einem beliebigen Knoten beginnend immer der je�weils n�achste� noch nicht in der Tour be�ndliche Knoten an ein Ende der Tour angeh�angt�

Algorithmus� Nearest�Neighbour Heuristik

�� W�ahle einen beliebigen Knoten j� setze l � j und T � f�� ng n fjg�

�� Solange T ��

i� Bestimme den Knoten j � T mit clj � minfcli � i � Tg�

ii� H�ange j an die Tour an und entferne j aus T �

iii� Setze l � j�

� Verbinde l mit dem Startknoten�

Der Aufwand f�ur dieses Verfahren betr�agt O�n�� da in jedem Schritt f�ur den Endknoten desbisherigen Pfades die Distanz zu allen anderen Knoten berechnet werden mu�� Nimmtmanjedoch eine geeignete Kandidatenmenge zu Hilfe� so sind in der Praxis lineare Rechenzeitenzu beobachten�

Theoretisch kann bei diesem Verfahren ein beliebig schlechtes Ergebnis erzielt werden� Mankann n�amlich beweisen� da� f�ur jedes r � � eine TSP�Instanz existiert� f�ur die die Nearest�Neighbour Heuristik eine Tour liefert� die mindestens r mal teurer als eine optimale Tour


ist �Ros �� Die schlechte Qualit�at der Touren ist leicht erkl�arbar� denn schon sehr fr�uhwerden die kurzen Kanten in die Tour eingef�ugt� ohne R�ucksicht auf andere Knoten inder N�ahe zu nehmen� Diese m�ussen dann sp�ater mit langen Kanten nachtr�aglich eingef�ugtwerden� Auf den Testinstanzen aus Tabelle �� erzielt die beste Variante des Verfahrenseine durchschnittliche Qualit�at von etwas �uber �� Dennoch wird die Nearest�NeighbourMethode h�au�g eingesetzt� besonders um gute Anfangsl�osungen f�ur iterative Verfahren zu�nden�

�� Insertion Heuristiken

Eine Insertion Heuristik beginnt mit einem Zyklus auf einem kleinen Teilgraphen� umdort nach und nach die anderen Knoten entsprechend festgelegter Kriterien einzuf�ugen�Beispielsweise w�ahle man den Knoten

� dessen Abstand zu einem Tourknoten am geringsten ist�

� dessen minimaler Abstand zu einem Tourknoten maximal ist�

� dessen Abstand zu einem Tourknoten maximal ist�

� dessen maximaler Abstand zu einem Tourknoten minimal ist�

� dessen Aufnahme in die Tour die Kosten am wenigsten erh�oht�

� zuf�allig�

� dessen Summe aller Abst�ande zu den Tourknoten maximal ist�

� dessen Summe aller Abst�ande zu den Tourknoten minimal ist�

Auch von diesen Kriterien gibt es noch Varianten� beispielsweise die unterschiedliche Wahldes Einf�ugepunktes� Laufzeit und Qualit�at der einzelnen Varianten sind sehr unterschied�lich� Bestenfalls erh�alt man einen Aufwand von O�n� log n� bei einer Qualit�at von etwa ��oder Laufzeiten in der Gr�o�enordnung O�n�� mit einer Qualit�at von etwa ��

Algorithmus� Insertion Heuristik

�� W�ahle eine Anfangstour durch k � Knoten v�� vk�

�� Setze W � V n fv�� vkg�

� Solange W ��


i� W�ahle einen Knoten j entsprechend einem bestimmten Kriterium�

ii� F�uge diesen Knoten an eine Position in der Tour ein�

iii� Reduziere W um j�

�Ahnlich wie bei der Nearest�Neighbour Heuristik lassen sich Kandidatenmengen heranzie�hen� um die Laufzeiten in der Praxis zu reduzieren� Anders als dort verschlechtert sich dieL�osungsqualit�at dadurch aber erheblich� Der Einsatz einer konvexen H�ulle als Anfangstourbei geometrischen Problemen ist erfolgreicher� da die Knoten der konvexen H�ulle auch ineiner optimalen Tour in der durch sie vorgegebenen Reihenfolge auftreten m�ussen �sonstg�abe es Kreuzungen in der Tour�� Weil sich eine konvexe H�ulle in O�n � log n� berechnenl�a�t �Rei �� erh�oht sich die Gesamtlaufzeit nur unwesentlich� der worst�case Aufwandgar nicht�

�� Doubletree�Heuristik

Erheblich schneller als die beiden bisher aufgef�uhrten Methoden� sind Verfahren� die aufMinimalen Spannb�aumen aufsetzen�

De�nition �� Minimaler Spannbaum � Gegeben sei ein Graph G � �V�E�� EinSpannbaum ist ein nicht�zyklischer� zusammenh�angender Teilgraph ST � �V� F � von G�F � E� Ein Minimaler Spannbaum ist ein Spannbaum MST � �V� T � mit T � E undc�T � minimal unter allen Spannb�aumen auf G�

Ein solcher Spannbaum l�a�t sich in O�n � log n� �geometrische Graphen� beziehungsweiseO�n�� allgemeine Graphen� berechnen �Rei �� Man verdoppelt nun alle Kanten desMinimalen Spannbaums� damit jeder Knoten geraden Grad besitzt� Dann kann man sichereine Euler�Tour �nden� also eine Tour� bei der jede Kante des Graphen genau einmalbesucht wird� Unter der Voraussetzung� da� der Graph die Dreiecksungleichung erf�ullt��ndet man eine Hamilton�Tour� die keinesfalls teurer ist� als die Eulersche Tour selbst� Diesgeschieht� indem man an einem beliebigen Knoten startend die Eulersche Tour traversiertund jeden Knoten� der dabei noch nicht besucht wurde� an den so entstehenden Hamilton�Weg anh�angt� Abbildung �� illustriert das Verfahren�

Algorithmus� Doubletree Heuristik

�� Berechne einen Minimalen Spannbaum�

�� Verdopple alle Kanten dieses Spannbaumes�

� Berechne eine Eulersche Tour auf diesem Graphen�


1

2

3 4

5

6 7

8 9

101112

A

B

E

C

D

G

F

Abbildung �� Ein Minimaler Spannbaum bei dem alle Kanten verdoppelt wor�den sind� Durchl�auft man nun die Eulersche�Tour die durch die Numerierungder Kanten gegeben ist erh�alt man eine Hamilton�Tour A�B�C�D�E�F�G�Aauf dem Graphen� Sie ist billiger als die Euler�Tour da von D nach E und vonG nach A

�Abk�urzungen� genommen werden�

� Ermittle aus dieser Tour eine Hamilton�Tour�

Die Laufzeit des Algorithmus wird bestimmt durch die Berechnung des minimalen Spann�baumes� alle anderen Schritte ben�otigen nur linearen Aufwand� Daher betr�agt der Gesamt�aufwand O�n�� f�ur allgemeine TSP�Instanzen und O�n � log n� f�ur euklidische Instanzen�

Die Laufzeiten f�ur dieses Verfahren sind sehr gering� die L�osungsqualit�at jedoch auch� Sieliegt bei beinahe �� Dennoch bietet sich das Verfahren an� um innerhalb kurzer Zeit eineAnfangsl�osung f�ur iterative Verfahren zu �nden� Da sich f�ur Graphen� die die Dreiecks�ungleichung erf�ullen� zudem beweisen l�a�t� da� mit diesem Verfahren ermittelte Tourenmaximal zweimal so lang sind� wie eine optimale Tour� bewegt man sich mit diesem Ver�fahren auch auf der sicheren Seite �Rei ��

�� Verfahren von Christo�des

Ein weiteres Verfahren basierend auf Minimalen Spannb�aumen wurde �� von N� Christo��des vorgeschlagen �Chr �� Dabei werden nicht alle Baumkanten verdoppelt� sondernauf den Knoten mit ungeradem Grad ein Minimum Weight Perfect Matching ermittelt�Auch dadurch haben alle Knoten geraden Grad� und man kann eine Eulersche Tour be�stimmen�

De�nition �� Perfect Matching � Ein Perfect Matching auf einem Graphen G ��V�E� mit jV j � �n ist eine Menge M � E von n Kanten� so da� jeder Knoten ge�


nau mit einer Kante dieser Menge inzidiert� Ein Minimum Weight Perfect Matching ist einPerfect Matching mit c�M� minimal�

Die Berechnung des Matchings kann in O�n�� geschehen �Edm �� Das Verfahren vonChristo�des hat damit kubischen Aufwand� da in einem Spannbaum alle Knoten ungeradenGrad haben k�onnen� Daher sucht man nicht immer das Minimum aller Perfect Matchings�sondern gibt sich mit einer guten N�aherung zufrieden� Der Aufwand zur Suche des Mat�chings und damit auch der Gesamtaufwand reduziert sich dadurch auf O�n�� In der Praxisist die Laufzeit abh�angig vom konkreten Problem� da die Anzahl der ungeraden Knotenstark variiert� Christo�des konnte zwar beweisen� da� bei Graphen� die die Dreiecksunglei�chung erf�ullen� die Kosten einer durch dieses Verfahren gewonnenen Tour niemals gr�o�erals das eineinhalbfache einer optimalen Tour sind� doch ist die durchschnittlich erzielteQualit�at auf den Testinstanzen mit knapp �� noch recht niedrig�

�� Savings Heuristik

Eine weitere M�oglichkeit� gute N�aherungsl�osungen f�ur das TSP zu �nden� ist das Verbin�den mehrerer Touren zu einer einzigen Tour� Dieses Vorgehen �ndet man bei der SavingsHeuristik�

Algorithmus� Savings Heuristik

�� W�ahle einen Basisknoten b � V und lege n� � Touren �b� v� �v � V n fbg fest�

�� Solange noch mehr als eine Tour existiert�

i� F�ur jedes Tourenpaar T�� T� berechne die Reduktion der Gesamtkosten� falls dieTouren verbunden werden� indem je eine Kante zum Basisknoten entfernt wirdund die so entstandenen o�enen Enden der Touren verbunden werden �sieheAbb� ��

ii� Verbinde die beiden Touren� bei denen die Kostenreduktion maximal ist�

Urspr�unglich wurde dieses Verfahren f�ur das Vehicle Routing Problem entwickelt�Wie aberbereits in Abschnitt �� angesprochen� ist das TSP nur ein Spezialfall� Es kann daher mitdem Verfahren gel�ost werden�

Der Aufwand f�ur das Verfahren betr�agt im worst case O�n� log n�� Damit ist es den anderenVerfahren in der Geschwindigkeit unterlegen� Geeignete Datenstrukturen� die es erlauben�nur die Information neu zu berechnen� die sich auch tats�achlich nach der Verbindung zweier


b

j

i T

T

2

1

Abbildung �� Savings Heuristik� Touren T� und T� werden an den Knoten i� jverbunden die Kostenersparnis betr�agt cib � cjb � cij�

Touren ge�andert hat� halten die durch die O�Notation versteckten Konstanten jedoch soklein� da� dennoch gute Laufzeiten erzielt werden�

Die gelieferten L�osungen sind von guter Qualit�at� Im Durchschnitt liegen sie nur etwa�� uber den Kosten einer optimalen L�osung�

�� Greedy Algorithmus

Der Greedy Algorithmus stellt eine allgemeinere Form der Nearest�Neighbour Heuristikdar� W�ahrend bei letzterer immer nur der n�achste Knoten eines bestimmten Knotensbetrachtet wurde� wird nun der n�achste Knoten jedes anderen Knoten gesucht�

Algorithmus� Greedy

�� Sortiere En � fe�� emg� so da� ce� � ce� � � � � � cem �

�� Setze T � ��

� F�ur alle Kanten e � E�

i� Wenn T �feg zu einer Hamilton�Tour ausgebaut werden kann �oder bereits eineHamilton�Tour ist�� dann setze T � T � feg�


Der Test� ob sich T � � T � feg zu einer Hamilton�Tour ausbauen l�a�t� ist bei geeignetgew�ahlten Datenstrukturen in konstanter Zeit machbar� Damit wird die Laufzeit des Ver�fahrens durch das Sortieren der Kanten bestimmt� betr�agt also O�m � logm�� Die Qualit�atder L�osungen dieses Verfahrens ist nur wenig schlechter als die der Savings Heuristik�

�� Iterative Verfahren

Neben den konstruktiven Verfahren� deren Ziel es ist� eine gute L�osung zu erzeugen� gibtes iterative Verfahren� die eine bereits vorhandene L�osung verbessern� Die wichtigsten undbekanntesten Vertreter sollen hier vorgestellt werden�

�� Node und Edge Insertion

Bei der Node beziehungsweise Edge Insertion Heuristik werden immerwieder Knoten �Kan�ten� aus einer bestehenden Tour entfernt und an einer g�unstigeren Stelle eingef�ugt� Diesgeschieht� bis dadurch keine Verbesserung der L�osung mehr gefunden werden kann�

Algorithmus� Node �Edge Insertion

�� Gegeben sei eine Tour T �

�� Wiederhole�

i� Pr�ufe f�ur jeden Knoten v �die Kante von Knoten v zu seinem Nachfolger� obdas Einf�ugen dieses Knotens �dieser Kante� an einer anderen Stelle in der Tourdie Kosten reduziert�

ii� Gibt es mindestens einen solchen Knoten �eine solche Kante�� so nehme denbesten �die beste� von diesen und f�uge ihn �sie� an der entsprechenden Stelleein�

bis keine Kostenreduktion mehr m�oglich ist�

Abbildung � illustriert die Vorgehensweise� Das Verfahren ist im worst�case nicht poly�nomiell� denn in diesem Fall w�urde jeder einzelne Schritt die Kosten der Tour nur um eineEinheit verringern� weshalb die Laufzeit abh�angig von den Tourkosten ist�

Ein Nachteil dieses Verfahrens ist� da� die L�osungsqualit�at in erheblichen Ma�e davonabh�angt� wie gut die Anfangsl�osung ist� Um gute Ergebnisse zu erzielen� mu� man also


Abbildung �� Ein Schritt beim Node �oben� und Edge �unten� Insertion Verfahren�

schon viel Aufwand in die Bestimmung der initialen Tour legen� Bei einer zuf�alligen An�fangsl�osung werden beispielsweise Qualit�aten von etwa �� erzielt� Eine L�osung� die voneiner Nearest�Neighbour Heuristik geliefert wurde� wird auf etwa �� verbessert� L�osungendes Savings�Verfahrens werden auf eine Qualit�at von etwa � gesteigert�

�� Opt Verfahren

Man kann sich f�ur geometrische Graphen leicht �uberlegen� da� eine Tour� die Kreuzungenvon Kanten enth�alt� nicht optimal sein kann� Kreuzen sich beispielsweise wie in Abbildung �� links� zwei Kanten ab und cd� so ist es besser� statt dessen die Kanten ac und bd in dieTour aufzunehmen� Auf der rechten Seite der Abbildung sieht man zwei Kanten� die sichnicht kreuzen� bei denen aber der gleiche Schritt auch zu einer Verbesserung der L�osungf�uhrt� Ein ��Opt Schritt besteht daher aus dem Entfernen zweier Kanten und dem erneutenEinf�ugen dieser Kanten auf die einzig andere Weise�

Algorithmus� ��Opt Verfahren

�� Gegeben sei eine Tour T �


i� Pr�ufe f�ur jeden Knoten v alle m�oglichen ��Opt Schritte� an denen die Kantezwischen v und seinem Nachfolger beteiligt ist�


d

ca

bc

d

b

a

Abbildung �� Zwei Situationen f�ur die Anwendung eines ��Opt Schrittes�

ii� Gibt es mindestens einen ��Opt Schritt� der die Tourkosten reduziert� so f�uhreden besten unter ihnen aus�

bis kein verbessernder ��Opt Schritt gefunden wird�

Auch dieses Verfahren ist aus den gleichen Gr�unden wie oben nicht polynomiell� DieL�osungsqualit�at dagegen ist kaum noch von der Qualit�at der initialen L�osung abh�angig�so da� ein einfaches Verfahren zur Erzeugung der Startl�osung gen�ugt� DurchschnittlicheWerte liegen bei etwa � � �uber dem Optimum�

Das Verfahren kann durch Einsatz einer Kandidatenmenge beschleunigt werden� doch sinddabei deutliche Qualit�atseinbu�en zu registrieren� Eine Kombination mit dem Node Inser�tion Verfahren dagegen kann die L�osungsqualit�at noch einmal steigern�

Weitere Verbesserungen der L�osungsqualit�at erh�alt man durch k�Opt Schritte� Bei diesenwird die Tour nicht in zwei� sondern in k Teile aufgesplittet und anschlie�end neu zusam�mengesetzt� Der zeitliche Aufwand f�ur dieses Verfahren ist erheblich� da es alleine einenAufwand von O�nk� erfordert� den besten k�Opt Schritt zu �nden� Zudem gibt es nicht� wie im ��Opt Verfahren � nur eine M�oglichkeit� die einzelnen Teile des Graphen neuzusammenzuf�ugen�

�� Lin�Kernighan�Heuristiken

Wie im letzten Abschnitt angedeutet� erm�oglichen komplexere Schritte im allgemeinen bes�sere L�osungen� Au�erdem bleiben die Verfahren mit einfachen Schritten schnell in lokalenOptima des L�osungsraumes stecken�

Lin und Kernighan �Lin �� schlugen �� vor� jeden Verbesserungsschritt aus kleinenTeilschritten zusammenzusetzen� die jeder f�ur sich nicht unbedingt die Tour verk�urzen


m�ussen� Seitdem sind viele Varianten dieser Heuristik ver�o�entlicht worden �Mak ��

71 2 3 4 5 6 8 9 10

71 2 3 4 5 6 8 9 10

71 2 3 4 5 6 8 9 10

71 2 3 4 5 6 8 9 10

Abbildung �� Illustration eines Lin�Kernighan Schrittes�

Auch hier soll jedoch die Variante aus �Rei �� vorgestellt werden�

In Abbildung �� ist ein Lin�Kernighan Schritt dieser Variante dargestellt� Die initialeTour sei �� Nun wird durch einen ��Opt Schritt die Tour in die beiden Wege�� und �� aufgetrennt� die wiederum durch die Kante �� verbundenwerden� Eine Kante �� w�urde den entstehendenWeg wieder zu einer Tour werden lassen�vorausgesetzt� die Richtungen in allen Teilpfaden sind richtig gesetzt� Statt dessen wirddiese �ktive Tour jedoch noch einmal durch einen ��Opt Schritt modi�ziert� Die Kante� � � wird entfernt und daf�ur die Kante � � �� eingef�ugt� Die Kante �� h�atte wieder einezul�assige L�osung zur Folge� Doch auch diese Tour bleibt �ktiv! der Knoten wird durcheinen Node Insertion Schritt zwischen die Knoten � und eingesetzt�

In der vorgestellten Variante sind alle Teilschritte entweder ��Opt Schritte oder Node In�sertions� Sie werden nach einem bestimmten Kriterium ausgew�ahlt� das die gr�o�te Verbes�serung verspricht �beziehungsweise die geringste Verschlechterung bedeutet�� Au�erdem


wurde die Zahl der Teilschritte in einem Lin�Kernighan Schritt begrenzt und eine Kandi�datenmenge eingesetzt�

O�ensichtlich gibt es eine Menge von M�oglichkeiten� Parameter zu w�ahlen� Die Qualit�atder Ergebnisse liegt je nach Wahl der Parameter zwischen � und � Die besten Ergebnissewurden mit Anfangstouren erzielt� die durch die Heuristik von Christo�des errechnet wur�den� Die Abweichungen bei anderen Anfangstouren sind jedoch gering� sowohl die Laufzeitals auch die Qualit�at der L�osungen betre�end�

�� Simulated Annealing Genetische Algorithmen

Neben den vorgestellten��klassischen� Verfahren existieren seit geraumer Zeit neuere

Ans�atze zur Bew�altigung des TSP� Diese entstanden zum Teil aus der Beobachtung derNatur�

Eines dieser Verfahren ist das Simulated Annealing� Bei diesem Verfahren wird der physika�lische Vorgang bei der Gerinnung von Fl�ussigkeiten simuliert� Man kann dort beobachten�da� eine Substanz besonders gleichm�a�ig geordnete Kristalle bildet� wenn ihre Temperatursehr langsam gesenkt wird� also die Schwingungsfrequenz der Molek�ule langsam reduziertwird� Beim Traveling Salesman Problem wird analog zun�achst eine relativ schlechte Aus�gangstour gew�ahlt� Diese wird zuf�allig ge�andert� Eine solche �Anderung wird akzeptiert�wenn sich entweder die Tour dadurch verbessert oder nur um einen bestimmten Prozent�satz verschlechtert� Dieser Prozentsatz entspricht quasi der Temperatur beim physikali�schen Versuch� W�ahrend also zu Beginn des Verfahrens auch deutliche Verschlechterungenakzeptiert werden� werden am Ende beinahe nur noch Verbesserungen angenommen� DieseSchritte werden wiederholt� bis ein festgelegtes Stop�Kriterium erf�ullt ist�

Die Ergebnisse dieses Verfahrens sind umso besser� je l�anger das Verfahren l�auft� Beson�ders entscheidend dabei ist die �Anderung der

�Temperatur�� Ein zu schnelles Abk�uhlen

beschr�ankt die Suche der L�osung auf eine kleine Teilmenge des L�osungsraumes� wodurchdie Gefahr w�achst� da� nur ein relativ schlechtes lokales Optimum gefunden wird�

Ebenfalls der Natur abgeschaut sindGenetische Algorithmen� Hier erzeugt man zuf�allig eineMenge von L�osungen �

�Population�� aus deren Elementen �

�Individuen�� durch Modi��

kation ��Mutation�� und Kombination �

�Kreuzung�� neue Individuen gescha�en werden�

Aus der alten Population und deren Nachfahren werden entsprechend bestimmter Kriteri�en Individuen ausgew�ahlt� die die Population im n�achsten Iterationsschritt �

�Generation��

darstellen�

Die Qualit�at der L�osungen dieses Verfahrens wird von der Leistungsf�ahigkeit derMutations� und Kreuzungs�Operatoren� sowie der Art der Selektion bestimmt� Es ist beigeeigneter Wahl meistens m�oglich� optimale L�osungen zu �nden� Daf�ur werden allerdings

Kapitel � Bekannte L�osungsstrategien

dann auch sehr gro�e Laufzeiten ben�otigt� Ein Einsatz an Stelle der in den Abschnitten ��und � vorgestellten Methoden bietet sich nicht an� da f�ur die Suche vergleichbar guterN�aherungsl�osungen mehr Zeit n�otig ist�

Kapitel �

Eine Heuristik mit iteriertem

Matching

In dieser Arbeit wird eine neue Heuristik f�ur das TSP besprochen� Sie basiert auf Iterier�tem Matching� einem Verfahren� das bereits in der Verschnittoptimierung �Fri �� guteErgebnisse geliefert hat�

Als erstes soll eine grobe �Ubersicht �uber den gew�ahlten Algorithmus gegeben werden� Dieeinzelnen Schritte dieses Algorithmus werden dann in den folgenden Abschnitten detail�lierter besprochen� Zun�achst m�ussen allerdings wichtige Begri�e eingef�uhrt und erl�autertwerden�

�� Begrisdenitionen

Ein Matching auf einem Graphen ist eine Verbindung je zweier seiner Knoten zu ei�nem Paar� Welche Knoten dabei gepaart werden� h�angt von verschiedenen Kriterien ab�W�ahrend das maximale Matching das Ziel hat� m�oglichst viele Knoten zu paaren� wirdbei einem Maximum Weight Matching die Summe aller Kantengewichte der Knotenpaaremaximiert� Eine weitere Variante ist das Minimum Weight Perfect Matching� das bereitsin �� vorgestellt wurde�

De�nition �� Matching � Ein Matching auf einem Graphen G � �V�E� ist eine Men�ge von Kanten M � so da� jeder Knoten mit maximal einer Kante aus M inzidiert�

De�nition �� Maximales Matching � Ein Maximales Matching ist ein Matching Mauf einem Graphen G � �V�E� mit jM j maximal�

De�nition �� Maximum Weight Matching � Ein Maximum Weight Matching istein Matching M mit c�M� maximal�

Kapitel Eine Heuristik mit iteriertem Matching �

128

10

100

0

5 6

10

25 15

128

10

100

0

5 6

10

25 15100100

Abbildung �� Maximales �links� und Maximum Weight Matching �rechts��

Einen Vergleich zwischen einem maximalen Matching und einem Maximum Weight Mat�ching zeigt Abbildung ��

Zur Berechnung des MaximumWeight Matchings wurde in dieser Arbeit ein Programm vonEd Rothberg verwandt� Es basiert auf dem �� von H� Gabow vorgestelltem

�N�cubed

weighted matching� �Gab �� Die Laufzeit des Programms ist im worst case kubischabh�angig von der Anzahl der Knoten�

Eine Verbindung aus zwei Knoten wird von nun an Cluster genannt� Beim iterierten Mat�ching wird auf dem zugrundeliegenden Graphen ein Matching durchgef�uhrt� mit den ent�standenen Clustern ein neuer Clustergraph aufgebaut und das Verfahren wiederholt� Eswerden so viele Iterationen durchgef�uhrt� bis die Anzahl an Clustern einen vorher festge�legten Wert erreicht�

De�nition �� Cluster � Gegeben sei ein Graph G � �V�E�� G� � �V �� E�� sei einTeilgraph von G� Au�erdem sei Hk � fT�� Tkg eine Menge verschiedener Hamilton�Touren auf dem Graphen G�� Dann hei�t das Tupel C � �V ��Hk� Cluster�

De�nition �� Clustergraph � Gegeben sei ein Graph G � �V�E�� Sei " �fC�� Cng� Ci � �Vi�H

iki� eine Menge von Clustern aus G und

# � f�Ci� Cj�� i �� j � ��v�� v�� H i� und �u�� u�� H

j

� mit �v�� u�� E und �u�� v�� Eg

eine Menge von Kanten zwischen den Clustern� Dann hei�t der Graph �"�#� Clustergraph�

Die Begri�e�Cluster� und

�Knoten� sollen im folgenden synonym verwandt werden� Dieses

macht Sinn� da ein Cluster nur ein verallgemeinerter Knoten ist �das Tupel �v� �v�� mit ei�nemKnoten und der einzigen Hamilton�Tour darauf ist nach De�nition � ein Cluster� undein Clustergraph dementsprechend ein Graph auf verallgemeinerten Knoten� Ein Knotenin der urspr�unglichen De�nition wird von nun an als Elementarknoten bezeichnet� Beziehtsich eine Aussage ausschlie�lich auf ein Cluster mit mindestens zwei Elementarknoten� wirdvon einem echten Cluster gesprochen�


In der De�niton �� des Clustergraphen wurde nicht darauf eingegangen� wie die Kantenzwischen zwei Clustern gewichtet werden� Dort wurde nur gesagt� da� eine Kante zweiCluster verbindet� wenn es zwischen je einem Elementarknoten der beiden Cluster eineKante in der Menge E des Graphen G gibt� Die Kantengewichte sollen dagegen die spezielleStruktur der echten Cluster mit ihren Hamilton�Touren ber�ucksichtigen� Sie werden daherdurch eine Bene�tfunktion bestimmt� die genau das leistet� Die Kantengewichte zwischenzwei Clustern werden daher auch Bene�t genannt�

De�nition �� Bene�t� Bene�tfunktion � Seien C�� C� zwei Cluster eines GraphenG � �V�E� und e � �C�� C�� eine Kante zwischen diesen Clustern� Das Gewicht dieserKante wird bestimmt durch eine Bene�tfunktion f�C�� C�� E�� die abh�angig von den Clu�stern und der zugrundeliegenden Kantenmenge ist� Man nennt das Gewicht dieser Kanteauch Bene�t�

�� Skizze des L�osungsalgorithmus

In dieser Arbeit wird das iterierte Matching auf das TSP angewandt� Im ersten Schrittwerden dazu Elementarknoten mit Hilfe eines Maximum Weight Matchings gepaart undmiteinander verbunden� Die entstandenen Cluster stellen gemeinsammit den zwischen denClustern existierenden Kanten ein reduziertes Problem dar� auf das das gleiche Verfahrenangewandt werden kann� Sind nur noch zwei Cluster �ubrig� stellen die auf diese Weiseausgew�ahlten Kanten im einfachsten Fall zwei Hamilton�Wege auf den Elementarknotender Cluster dar� Werden diese beiden optimal verbunden� hat man eine Hamilton�Tour imUrsprungsgraphen�

Algorithmus� Iteriertes Matching


i� Finde ein Maximum Weight Matching auf Graphen�

ii� Verkn�upfe gepaarte Knoten zu Clustern�

bis nur noch zwei Cluster �ubrig sind�

�� Verbinde die letzten beiden Cluster optimal�

Schon angesprochen wurde� da� die Kantengewichte zwischen den Clustern durch eineBene�tfunktion bestimmt werden� Die Wahl dieser Funktion hat entscheidenden Ein�u�auf das Gesamtergebnis� Sie mu� au�erdem f�ur die Umwandlung billiger Kanten in gro�eGewichte sorgen �da das Matching ja Kanten mit besonders gro�en Gewichten bevorzugt��


Ist an einer Paarung zweier Cluster mindestens ein echtes beteiligt� gibt es mehrereHamilton�Touren auf der Vereinigung der beiden Elementarknotenmengen� Nur die bestezu speichern� ist nicht sinnvoll� denn dadurch werden vorzeitig gute L�osungsalternativenausgeschlossen� wie in Abbildung �� zu sehen ist� Das Problem besteht darin� geeigneteTouren zu konstruieren und auszuw�ahlen�

Abbildung �� Paarung zweier Cluster� Oben wurden nur die lokal besten Tou�ren gespeichert unten auch teurere�

Ein weiteres Problem beim Einsatz des iterierten Matchings ist die Laufzeit des Matchings�Ein MaximumWeight Matching ist bestenfalls in O�n�� machbar �Edm �� Eine Reduk�tion der zu untersuchenden Kanten sorgt jedoch f�ur eine merkliche Senkung der durch dieO�Notation verborgenen Konstanten� Hier macht sich der Einsatz einer Kandidatenmengebezahlt�

In d�unn besetzten Graphen besteht allerdings ein besonderes Problem� Hier existiert nichtimmer eine Hamilton�Tour� Selbst wenn man voraussetzt� da� eine solche existiert� so kannes immer noch Kanten geben� die in keiner Hamilton�Tour vorkommen� Enth�alt ein Mat�ching eine solche Kante� so werden Zyklen konstruiert� die nicht zu einer zul�assigen L�osung

Kapitel Eine Heuristik mit iteriertem Matching

f�uhren� Diese Kanten m�ussen also von vornherein ausgeschlossen werden� Die gestrichelteKante in Abbildung � stellt eine solche Kante dar�

Abbildung � ��Verbotene� Kante bei der Suche nach einer Hamilton�Tour�

�� Darstellung einer L�osung

Der wichtigste Punkt ist aber wohl die Darstellung einer L�osung an sich� Das Verfahrendr�angt die �f�ur das TSP untypische� Darstellung als Baum auf� denn in jedem Schrittwerden je zwei

�kleine� Cluster zu einem

�gr�o�eren� zusammengefa�t� In jedem Cluster

765431 82

LRRL

R R

Abbildung ��Darstellung der L�osung als Baum�Die abgebildete L�osung lautet� � ��

mu� also gespeichert werden� aus welchen Knoten es entstanden ist� Au�erdem m�ussen


Informationen dar�uber vorhanden sein� wie die Elementarknoten der Cluster durchlaufenwerden� Im einfachsten Fall wird in jedem Cluster nur eine Tour gespeichert� Eine neueTour entsteht dann dadurch� da� beide Teiltouren aus den S�ohnen dieses Clusters imL�osungsbaum nacheinander durchlaufen werden� wobei festgelegt werden kann� welchervon beiden als erstes genommen wird �siehe Abb� ��

�� Speichern mehrerer Wege

Durch Abbildung �� wurde klar� da� es nicht sinnvoll ist� bei der Verbindung zweierCluster nur die lokal beste Hamilton�Tour zu speichern� Dieses w�urde die Qualit�at derN�aherungsl�osung am Ende erheblich einschr�anken�

Es ist aber nicht m�oglich� alle Touren zu berechnen� die auf den Elementarknoten einesClusters entstehen k�onnen� Das hie�e� alle Permutationen auf den Elementarknoten zubestimmen� und w�are mit der Suche nach der optimalen L�osung identisch� Ziel ist es aber�mit vergleichbar geringemAufwand eine Menge guter �suboptimaler� Touren zu �nden� Daskann geschehen� indem bei der Paarung zweier Cluster neue Touren dadurch konstruiertwerden� da� aus jedem Cluster eine Tour hergenommen wird� an einer Stelle aufgebrochenund mit der anderen Tour verbunden wird� Dabei besteht in symmetrischen Graphen dieM�oglichkeit� eine Tour sowohl vorw�arts als auch r�uckw�arts zu durchlaufen� Eine Touraufzubrechen bedeutet� da� eine Kante aus der Tour entfernt wird� Man erh�alt dadurcheinen Hamilton�Weg� Im folgenden soll kein Unterschied zwischen den Begri�en

�Weg� und

�Tour� gemacht werden�

Speicherplatzbedarf und Laufzeitverhalten sprechen dagegen� die Touren als Elementar�knotenfolge zu speichern� Eine M�oglichkeit� die neu entstandenen Zyklen eindeutig zu be�schreiben� ist das Zur�uckgreifen auf bereits vorhandene Informationen in den S�ohnen einesClusters� Seien also C� und C� zu paarende Cluster� v�� vp die Elementarknoten in C�

und u�� uq die Elementarknoten in C�� Weiter bezeichne vi�j die Folge �vivi�� vj� und�vi�j die Folge �vivi�� vj� �entsprechend f�ur u�� wobei vi�j � �� wenn i � j und �vi�j � ��wenn i � j� Die Menge der m�oglichen Touren f�ur die Kombination der Wege v��p aus C�

und u��q aus C� lautet dann

W � f�v��iuj�qu��j��vi��p�� v��i�uj��uq�j��vi��p� �i � �� p� j � �� qg�

Tabelle �� zeigt ein erl�auterndes Beispiel�

Jede Tour in einem Cluster mu� eindeutig beschrieben werden� Sei nun ein Cluster C ��V�Hk� aus den beiden Clustern C� � �V��H�

k�� und C� � �V��H�

k�� entstanden� Die Tour

T � Hk bestehe dabei aus den Touren T� � v��p � H�k�und T� � u��q � H�

k�� Die

Menge W sei die Menge der m�oglichen Tourkombinationen aus T� und T�� Die Tour Tist dann eindeutig beschrieben durch die Indizes � und der Touren aus H�

k�und H�

k��


i j neue Touren� � ��

Tabelle �� Die Tabelle zeigt verschiedene M�oglichkeiten zwei Touren v�� und u�� zu kombinieren� In der dritten Spalte stehtjeweils die Tour die entsteht wenn man die Tour u�� vorw�arts durchl�auft inder vierten Spalten wird u�� r�uckw�arts durchlaufen�

den Werten i � �� p und j � �� q� die das Element aus W beschreiben� sowie �in symmetrischen Graphen � die Richtung der Tour T�� Der Elementarknoten vi hei�tdann Austrittspunkt aus der Tour T�� der Elementarknoten uj hei�t Eintrittspunkt indie Tour T�� Da es sich bei T um einen Zyklus handelt� ist die Festlegung von v� als

�Anfangsknoten� keine Einschr�ankung� Schlie�lich ist der Zyklus �va�p� v��a�� va�� a � �mit dem Zyklus �v��p� v�� identisch� Auch die Tatsache� da� nur bei dem rechten Sohn eineRichtung vorgegeben werden kann ist in symmetrischen Graphen keine Einschr�ankung�denn f�ur jeden Zyklus �v��p� v�� existiert eine Darstellung ��vp�� vp�� die den gleichen Zyklusbeschreibt�

Bei der Berechnung der Menge W ist zu beachten� da� es Sonderf�alle gibt� in denen zweiverschiedene Beschreibungen der vorgestellten Form das gleiche Element darstellen� DieserFall tritt dann auf� wenn das Cluster im rechten Sohn h�ochstens zwei Elementarknotenenth�alt� Sind es genau zwei Elementarknoten gilt n�amlich �u��q u�� uq�� u�� im Falleeines einzelnen Elementarknotens gilt u�� u�� In diesem Fall darf der rechte Sohn nurin einer Richtung durchlaufen werden� Ein L�osungsbaum auf acht Elementarknoten ist inAbbildung �� skizziert�

�� Wahl der Benetfunktion

Eine zentrale Rolle des gesamten Verfahrens spielt die Wahl der Bene�tfunktion� also dieArt und Weise� in der einem potentiellen Paar von Clustern eine Qualit�at zugeordnet wird�Diese Qualit�at entspricht dem Gewicht der Kanten im Clustergraphen bei der Berechnungdes Matchings� Bei der Bestimmung der Qualit�at einer Kante kann ist es sinnvoll� nicht nurihr Gewicht zu betrachten� sondern auch die Kosten der Wege innerhalb der Cluster� Der


7654 831 2

1,1/5,6/F1,1/3,4/F1,1/1,2/F

1,1/2,3/F1,1/6,8/F1,1/5,7/F

1,1/7,8/F

2,2/3,8/F1,2/4,5/B

1,1/1,3/F

Abbildung �� Ein L�osungsbaum mit maximal zwei gespeichertern Wegen proCluster� Die ersten Informationen in einem Cluster stellen die Indizes der We�ge die aus den S�ohnen gew�ahlt wurden dar� Darauf folgt der Aus� und Ein�trittspunkt beider gew�ahlter Wege� Schlie�lich folgt die Festlegung der Rich�tung des rechten Sohnes� In der Wurzel sind die Wege �� und�� gespeichert�

Einfachheit halber bietet es sich an� als Bewertungsgrundlage die Kosten der entstehen�den Touren in den neuen Knoten heranzuziehen� Durch diese Ma�nahme wird verhindert�da� zwei Cluster miteinander gepaart werden� die zwar nahe beieinander liegen� derenVerbindung aber schlechte Teiltouren hervorrufen w�urde �siehe Abb� ��

2 3

4

1

Abbildung �� Obwohl Cluster � und � Knoten haben die sehr dicht beieinan�derliegen �grau unterlegt� ist die Verbindung von � und � g�unstiger�


Da ein MaximumWeight Matching angewandt wird� um g�unstige Verbindungen zu �nden�m�ussen gute Kanten im Clustergraphen � solche� die Cluster so miteinander verbinden�da� gute Teiltouren entstehen�mit hohen Gewichten versehen werden� Hier bietet sich dieSkalierung der Bene�ts auf ganzzahlige Werte zwischen � und �� an� Wie diese Skalierungvor sich geht� wird im folgenden aufgezeigt�

Eine Kante soll einen gro�en Bene�t haben� wenn ihre Aufnahme in eine Tour die Kostenm�oglichst wenig erh�oht� Beispielsweise k�onnte man der Kante den Bene�t �� zuordnen�deren Gewicht das kleinste im gesamten Graphen ist� Ist das Gewicht einer anderen Kantedann x�mal so gro� erh�alt sie den Bene�t �

x� �� Eine andere M�oglichkeit besteht darin�

einer Kante �i� j� den Bene�t �� zuzuordnen� wenn diese sowohl von i als auch von j ausdiejenige mit den geringsten Kosten ist� wenn also gilt

cij � civ und cij � cvj �v�

Auch hier erhalten die anderen Kanten dann einen Bene�t relativ zum bestm�oglichenWert�Schlie�lich kann auch die Kombination dieser beiden Varianten eine sinnvolle Gewichtungergeben�

Der Bene�t einer Kante ist in den drei F�allen nicht allein von ihr selbst abh�angig� Au�er�dem m�ussen bei der Gewichtung von Kanten zwischen zwei echten Clustern die in diesengespeicherten Touren ber�ucksichtigt werden� Daher macht es Sinn� zuerst f�ur jedes Kno�tenpaar einen Pre�Bene�t zu berechnen� Bei diesem handelt es sich um einen Wert� derumso kleiner ist� je besser ein Knotenpaar zun�achst scheint� Es gibt mehrere M�oglichkeiten�diesen Pre�Bene�t zu errechnen�

� Es werden die Kosten aller Touren berechnet� die aus der Verbindung aller Teiltourenin den beiden Knoten entstehen k�onnen und

� die Kosten der besten

� die Kosten der schlechtesten

� der Durchschnitt der Kosten

dieser Touren als Pre�Bene�t genommen�

� Es werden die Kosten aller Touren berechnet� die aus der Verbindung der besten kTeiltouren in den beiden Knoten entstehen k�onnen und

� die Kosten der besten

� die Kosten der schlechtesten

� der Durchschnitt der Kosten

dieser Touren als Pre�Bene�t genommen�


� In geometrischen Problemen wird der Abstand der Schwerpunkte voneinander alsPre�Bene�t genommen�

F�ur jeden Knoten i wird der beste Pre�Bene�t bi gespeichert� an dem er beteiligt ist�Au�erdem wird der global beste Pre�Bene�t bmin � mini� ��n bi gespeichert� Der Bene�tberechnet sich jetzt aus der Formel

bene�t�i� j� �

��

jlmax�prebene�t�i�j�

lmax�bmin

kwenn lmax prebene�t�i� j�

� sonst

Dabei stellt lmax den maximal zul�assigen Pre�Bene�t dar� Er wird auch Referenzwert ge�nannt� Jede Verbindung mit gr�o�erem Pre�Bene�t erh�alt automatisch das Kantengewicht��

Der Referenzwert lmax selbst kann indirekt manipuliert werden� Er ergibt sich aus derFormel

lmax �

�fref�qmin

��qmin� bmin f�ur qmin � �

fref � bmin f�ur qmin � ��

Dabei ist qmin die Mindestqualit�at� die von einer Kante gefordert wird� Mit dem Referenz�faktor fref erh�alt man den Pre�Bene�t� der dieser Mindestquali�at entspricht� indem manfref � bmin berechnet� Eine Kante mit dem Pre�Bene�t fref � bmin erh�alt dementsprechenddie Qualit�at qmin� Es gilt � � qmin � � und fref ��

Der Grund f�ur den Einsatz einer Mindestqualit�at liegt in der�Gier� des Matchings be�

gr�undet� In Abbildung �� w�urde sich ein gutes Matching beispielsweise aus der Verbindungje zweier Knoten auf dem Kreis ergeben� Die Kante zwischen A und B erh�oht zwar dieSumme der Kantengewichte� doch ihr Erscheinen im Matching macht wenig Sinn� da sie si�cherlich nicht in der optimalen L�osung des Problems auftritt� Bewertet man die Kante mit�� weil sie einer gewissen Mindestqualit�at nicht gen�ugt� so erh�oht sie die Summe der Kan�tengewichte nicht und wird dementsprechend vom Matchingalgorithmus nicht ausgew�ahlt�Die Knoten A und B k�onnen dadurch sp�ater besser in den Kreis integriert werden�

Durch den Referenzfaktor fref kann beein�u�t werden� wie genau die Bewertung einer Kan�te ist� Zwei Kanten gleicher Qualit�at m�ussen nicht zwangsl�au�g den gleichen Pre�Bene�thaben� Dieser mu� nur im gleichen Intervall �b�� b�� liegen� Die Grenzen dieses Intervalls sindgegeben durch den kleinsten und den gr�o�ten Pre�Bene�t� f�ur den die verlangte Qualit�aterzielt wird� Die L�ange des Intervalls wird daher durch fref festgelegt�

Bei der Bestimmung des Bene�ts wird nicht wirklich lmax verwendet� sondern ein Wert� dernoch von der Kante �i� j� abh�angt� Der Bene�t ist dadurch nicht nur von globalen Gege�benheiten abh�angig� sondern kann auch lokale Besonderheiten ber�ucksichtigen� Abbildung� zeigt einen Graphen� bei dem eine Teilmenge der Knoten sehr dicht beieinander liegt


B

A

Abbildung �� Eine Kante zwischen A und B w�urde die Summe der Kanten�gewichte bei einem Maximum Weight Matching zwar erh�ohen jedoch erg�abesich wird sie mit bewertet auf den anderen Kanten die gleiche Auswahl�

�rechts� und der Rest der Knoten durch gr�o�ere Distanzen getrennt ist �links�� Eine Be�wertung der Kanten nur nach der k�urzesten Kante im Graphen ist nicht sinnvoll� da derTeilgraph links praktisch unabh�angig vom Rest behandelt werden kann� Die Formel f�ur

Abbildung �� Bei geclustertenGraphen ist es sinnvoll die Qualit�at einer Kanteauch von lokalen Gesichtspunkten abh�angig zu machen�

den Referenzwert der Bene�tfunktion lmax�i� j� lautet daher

lmax�i� j� �

�fref�qmin

��qmin� bbase�i� j� f�ur qmin � �

fref � bbase�i� j� f�ur qmin � ��

mit bbase�i� j� � �� g� bi�bj� � g � bmin� wobei � � g � � den globalen Einu� bei derBerechnung festlegt� Durch g kann man also bestimmen� welchen Ein�u� der global bestePre�Bene�t auf die Bewertung einer Kante hat� Entsprechend lautet also der Bene�t f�ur


eine Kante �i� j�

bene�t�i� j� �

��

jlmax�i�j��prebene�t�i�j�

lmax�i�j��bbase�i�j�

kfalls prebene�t�i� j� � lmax�i� j�

� sonst

Die Aussagen der letzten Abs�atze sollen anhand einer Abbildung verdeutlicht werden �Abb�� Oben links in der Abbildung ist der Graph gemeinsam mit den Pre�Bene�ts derKanten zu sehen� Oben rechts werden die Bene�ts ganz ohne globalen Ein�u� berechnet�

14

23

17 20

18

37

36

26

29

30

E

CBA

D

FE

CBA

D

F

32

100

100

100

Pre-Benefits:

0

0

0

0

0

0

0

Benefits bei g=0.0, f=1.05, q=0.8:

43

E

CBA

F

D

E

CBA

F

D

100

48

100

E

CBA

F

D

E

CBA

F

D

100 100

100

6

52

85

17

32

13 100

0

0


0

16

0

0 0

0


95

48

72

87

48

62

52 94

27

30


14 0

0

0

0

0 0

00

0


85 60

81

Abbildung �� Ein Graph mit den gegebenen Pre�Bene�ts und den darausresultierenden Bene�ts f�ur verschiedene Parameter�

Da es an den Knoten A und B keine Kante mit besserem Pre�Bene�t als �� gibt� erh�alt


die Kante zwischen ihnen den Bene�t �� Entsprechendes gilt f�ur die Kanten �C�D�und �E�F �� Es gilt n�amlich in allen genannten F�allen bbase�i� j� � prebene�t�i� j�� F�urdie Kante �B�C� gilt dagegen beispielsweise bbase�B�C� �

bB�bC�

� � ��

� �� Mitdem Referenzfaktor fref � �� und der Mindestqualit�at qmin � �� ergibt sich daher f�urlmax�B�C� �

��

� �� und schlie�lich bene�t�B�C� � ��

� � F�urdas Matching wird die Kante den Wert � erhalten� da sie nicht die Mindestqualit�at von�� hat�

In der Mitte links ist der Referenzfaktor auf fref � �� erh�oht� Dadurch erh�oht sich auchder Bene�t der Kante �B�C� auf � wodurch sie f�ur die Berechnung des Matchings relevantwird�

Rechts daneben in der Abbildung wurde ein �� prozentiger globaler Ein�u� eingestellt�Daher hat nur die Kante �F�E� den Bene�t �� F�ur �A�B� gilt n�amlich bbase�A�B� �� Es folgt lmax�A�B� � �� und bene�t�A�B� � ��

Bei ausschlie�lich globalem Ein�u� �unten rechts� ergibt sich f�ur die Kante �A�B� mitbbase�A�B� � �� lmax�A�B� � �� sogar bene�t�A�B� � �� Es werden daher nur wenigeKanten in das Matching aufgenommen werden� Das f�uhrt dazu� da� sehr viele Matchingsberechnet werden m�ussen� da sich die Anzahl von Clustern pro Iterationsschritt nur ge�ringf�ugig reduziert�

Abschlie�end soll bemerkt werden� da� das Greedy�Verfahren simuliertwerden kann� indemg � qmin � fref � �� gew�ahlt wird� Allerdings ist diese Simulation durch den Einsatz desMatchings deutlich langsamer� Positiv dagegen ist die Tatsache� da� im Gegensatz zumOriginal so viele gleichteure Kanten wie m�oglich auf einmal ausgew�ahlt werden�

�� Einsatz von Kandidatenmengen

Bereits erw�ahnt wurde die Tatsache� da� das Matching auf n Knoten in O�n�� berechnetwird� Allerdings l�a�t sich die tats�achliche Laufzeit um in der O�Notation untergehendeFaktoren beschleunigen� Dies erreicht man� indem man die Anzahl der zu untersuchendenKanten im Graphen deutlich einschr�ankt� Diese Einschr�ankung f�uhrt nicht zwangsl�au�gzu einer schlechteren L�osung� Viele Kanten in vollst�andigen Graphen sind sicher nicht ineiner optimalen Tour enthalten �siehe Abb� �� Diese k�onnen von vornherein entferntwerden�

Bereits in Abschnitt �� wurde auf Kandidatenmengen eingegangen� Diese lassen sich auchbeim iterierten Matching sinnvoll einsetzen� wie ein Vergleich der Laufzeiten zeigt �Abb�� Auf einem vollst�andigen Graphen mit �� Knoten dauert die Berechnung des Mat�ching bereits deutlich l�anger� als bei einem d�unn besetzten Graphen mit der gleichenAnzahlan Knoten� Daher wird das Matching nur auf einem d�unn besetzten Graphen durchgef�uhrt�


1

2

Abbildung �� Die Kante von � nach � wird sicher nicht in der optimalenTour erscheinen�

der aus allen Knoten und aus den durch die Kandidatenmengen ausgew�ahlten Kanten be�steht� Im geographischen Fall bietet es sich an� eine Kombination aus N�achsten Nachbarnund Delaunay Graph als Kandidatenmenge zu w�ahlen� In den meisten F�allen werden op�timale Touren ausschlie�lich �uber Kanten dieser Menge f�uhren�

ohne Kandidatenmenge

mit Kandidatenmenge

80070060050040030020010000

50

100

150

200

250

300

350

400

450

500

Zeit in Sekunden

Anzahl der Knoten

Abbildung �� Vergleich der Laufzeiten eines Matchings mit und ohne Einsatzeiner Kandidatenmenge� Bei einem vollst�andigen Graphen nimmt die Laufzeitkubisch mit der Anzahl der Knoten zu �zum Vergleich ist die Funktion c �x� abgetragen�� Bei Einsatz der Kombination von Delaunay Graph und ��Nearest�Neighbour Subgraph ist diese Zunahme nur noch quadratisch�

Die Kandidatenmenge wird solange eingesetzt� bis die Anzahl der Cluster die Schwellencand unterschreitet� F�ur kleinere Clustergraphen wird das Matching auf dem vollst�andigenGraphen durchgef�uhrt� Durch diese Ma�nahme wird erreicht� da� auch bei schlechter Wahlder Kandidatenmenge� beispielsweise� wenn diese nicht zusammenh�angend ist � dennochL�osungen akzeptabler Qualit�at gefunden werden�

Zur Berechnung der Delaunay Triangulation wird eine Implementation des Sweepline Algo�rithmus von Steve J� Fortune verwendet� Dieser wurde �� in �For �� vorgestellt� Leider


ben�otigt dieser sehr viel Speicher� weshalb sich die Untersuchungen auf Probleminstanzenmit weniger als � �� Knoten beschr�anken mu�ten�

�� Zusammenfassen zweier Knoten

Nachdem durch das Matching festgelegt wurde� welche Knoten gut zueinander�passen��

mu� aus je zwei gepaarten Knoten ein neuer erzeugt werden� n�amlich deren Vater imL�osungsbaum� Die bereits in den S�ohnen gespeicherten Informationen sollten nach M�oglich�keit nur vom Vater referenziert und nicht erneut abgespeichert werden�

Beispielsweise sollen die Cluster C� � �V��H�h�� und C� � �V��H�

h�� zusammengefa�t wer�

den� Es seien jV�j � p und jV�j � q� Aus der Kombination zweier einzelner Touren ergebensich �pq neue m�ogliche Touren �siehe Abschnitt �� Insgesamt k�onnen also �h�h�pq neueWege entstehen� Eine solche Menge ist bereits f�ur kleine Cluster nicht mehr zu verwalten�Es mu� also eine Selektion unter allen m�oglichen Wegen durchgef�uhrt werden�

Diese Selektion ist auf zweierlei Art denkbar� Einerseits kann man eine feste Zahl t vorge�ben� die die maximale Anzahl zu speichernder Wege darstellt �Absolute Selektion�� Ande�rerseits kann man fordern� da� kein gespeicherter Weg mehr als p Prozent teurer als derbeste Weg ist �Relative Selektion�� Um sich in kleinen Clustern m�oglichst viele Optioneno�enzuhalten� kann es sinnvoll sein� zu Beginn des Verfahrens sehr viele Wege auszuw�ahlen�jedoch zum Ende hin nur noch wenige der besten� Dazu kann man einen Abnahmefaktor� � d � � einstellen� mit der die Selektionsrate t beziehungsweise p nach jedem Iterati�onsschritt multipliziert wird� Das ist auch insofern sinnvoll� als da� bei kurzen Touren eingro�er Kostenunterschied eine sehr kleine Rolle in der endg�ultigen L�osung spielt� er jedochdie M�oglichkeit neuer� besserer Kombinationen in den n�achstgr�o�eren Clustern bietet�

Auch die Anzahl der Touren� die aus der Kombination zweier Zyklen der zugrunde lie�genden Cluster entstehen k�onnen� sollte eingeschr�ankt werden� Es macht sicherlich Sinn�hier nur eine bestimmte Anzahl guter Wege zuzulassen� Allerdings werden alleine f�ur dieBerechnung aller Tourkosten p � q Schritte ben�otigt� Daher soll die Menge der Elementar�knotenpaare� die �uberhaupt als Verbindungsknoten in Frage kommen� reduziert werden�In geometrischen Graphen bietet sich folgende Vorgehensweise an �Abb� �� Von beidenClustern werden die n�achsten Elementarknoten zum Schwerpunkt des jeweils anderen Clu�sters bestimmt� Mit diesem werden dann alle die Touren berechnet� die mindestens einendieser Elementarknoten enthalten� Die besten k so entstehenden Touren werden dann f�urdie weitere Selektion herangezogen�

Leider l�a�t sich die Menge der zu untersuchenden Kombinationsm�oglichkeiten nicht ein�schr�anken� Bei einem geometrischen TSP seien bereits k Wegekombinationen in einemCluster gespeichert� wobei k gleichzeitig die maximale Anzahl zu speichernder Wege dar�stelle �die Selektionsrate bei absoluter Selektion�� Die Kosten des k�ten Weges seien c�


B

C

A

S1

S2

Cluster C

Cluster C

1

2

Abbildung �� Sollen zwei Cluster C� und C� eines geometrischen Graphenverbunden werden so werden �uber ihre Schwerpunkte �S� und S�� gute Verbin�dungsknoten bestimmt�Aus der Sicht von Cluster C� liegt der ElementarknotenA aus C� besonders g�unstig f�ur C� liegen B und C sehr gut� F�ur jeden so be�stimmten Elementarknoten eines Clusters werden alle m�oglichen Verbindungenmit den Elementarknoten des anderen Clusters berechnet�

Man k�onnte nun annehmen� da� bei der Kombination zweier Wege aus den S�ohnen mitden Kosten c� und c�� mit c�� c� c keinesfalls ein Weg entstehen k�onnte� dessen Kostenkleiner als c ist� Sind die Wege in aufsteigenden Reihenfolge in den Knoten gespeichert�so m�u�te dann keine der Folgekombinationen mehr berechnet werden� Die Aussage tri�taber nicht zu� wie Abbildung �� zeigt� Daher m�ussen f�ur jede m�ogliche Kombination dieKosten der entstehenden Touren ausgerechnet werden�

Trotz allem bietet es sich an� die Wege in sortierter Folge zu speichern� nicht zuletzt� weileinige Bene�tfunktionen nur einige der besten gespeicherten Wege als Berechnungsgrund�lage heranziehen� Au�erdem m�ussen dann nicht alle m�oglichen Kombinationen gespeichertwerden� bevor die Selektion einige von ihnen wieder verwirft� Stellt sich bei der Kom�bination zweier Zyklen heraus� da� die Kosten der daraus entstehenden Tour nicht denSelektionskriterien gen�ugt� braucht sie gar nicht erst gespeichert zu werden�

Zur Sortierung der Wege wird eine Variante des bin�aren Suchbaumes eingesetzt� Ne�ben den �ublichen Informationen wird in jedem Teilbaum die Anzahl der Knoten festge�halten� die in diesem enthalten sind� Auf diese Weise kann� ohne den Baum traversie�

Kapitel Eine Heuristik mit iteriertem Matching ��

8

4

6

3

10

6

6

5

6

Abbildung �� Die Kosten der bei der Kombination der beiden Wege entste�henden Tour sind mit �� Einheiten kleiner als die Summe der Kosten beiderTeilwege �� Einheiten�� Die an den Kanten angegebenen Kosten entsprechenbis auf Runden den Abst�anden der Knoten voneinander�

ren zu m�ussen� jeder beliebigen Knoten anhand seiner Position in der sortierten Folgein O�log n� angesteuert werden� In Abbildung �� ist beispielsweise in einem �ublichen

1 1 1 1 1

323

6 5

1

12

Abbildung �� Erweiterter bin�arer Suchbaum� Die in den Knoten geschrie�benen Zahlen stellen die Anzahl der Elemente in dem entsprechenden �Teil��Baum dar� Die durchgezogene Linie f�uhrt zum elften Element in der sortiertenFolge der Elemente� Die sortierten Elemente sind selbst nicht dargestellt�

Bin�arbaum � der linke Sohn enth�alt Elemente� die kleiner sind als das der Wurzel� derrechte Sohn gr�o�ere � der Weg zum elften Knoten als durchgezogene Linie dargestellt�Von der Wurzel ausgehend �ndet man den Weg mit folgendem rekursiven Algorithmus�


Algorithmus� Suche i�ten Knoten im bin�aren Suchbaum

�� Sei nl die Anzahl der Elemente im linken Teilbaum�

�� Wenn i � nl� Suche den i�ten Knoten im linken Teilbaum�

� Wenn i � nl � �� Wurzel ist der gesuchte Knoten�

� Wenn i � nl � �� Suche �i� nl � ��ten Knoten im rechten Teilbaum�

Im konkreten Beispiel erkennt man also an der Wurzel� da� der elfte Knoten sich im rechtenTeilbaum be�nden mu� und dort an vierter Stelle steht� Dort be�ndet er sich im rechtenTeilbaum� da sich im linken Teilbaum nur ein Element be�ndet� Der gesuchte Knoten isthier an zweiter Position zu �nden� Dies ist aber die Wurzel des Teilbaumes selbst� da sichim linken Teilbaum wiederum nur ein Element be�ndet�

Zun�achst soll das Speichern eines Weges bei absoluter Selektion beschrieben werden� Dabeiwerden die soeben berechneten Kosten c einer Wegekombination mit den Kosten cr desr�ten gespeicherten Weg im Baum verglichen� wobei r die Selektionsrate ist� Ist c � cr mu�die neue Kombination in den Baum aufgenommen werden� ansonsten kann sie verworfenwerden�

Bei relativer Selektion werden die Kosten c der neuen Kombination mit den Kosten c�der in der Wurzel gespeicherten Kombination verglichen� Gilt c � �� r

�� c mit derSelektionsrate r� so wird die neue Kombination aufgenommen�

Nachdem alle Kombinationen durchgerechnet wurden� wird eine Inorder�Traversierung desBaumes durchgef�uhrt� Bei absoluter Selektion werden die ersten r Kombinationen im neu�en Cluster gespeichert� bei relativer Selektion alle Wege� die nicht mehr als r Prozent teurersind als der billigste� Dieser Schritt ist notwendig� da bei der oben beschriebenen Voraus�wahl ja nur mit den zum aktuellen Zeitpunkt besten Wegen verglichen wurde� Da neueKombinationen aber bessere Wege ergeben k�onnen� sind unter Umst�anden Wege im Baumgespeichert� die die Selektionskriterien nicht mehr erf�ullen� Die Zahl dieser Wege wird abernicht allzu gro� sein� weil bei der Vorauswahl mit Kombinationen guter Wege begonnenwird� die voraussichtlich auch gute neue Kombinationen liefern�

�� Vor� und Nachbereitung des Matchings

Damit das Matching e�ektiv durchgef�uhrt werden kann� werden einige Vorbereitungen ge�tro�en� Bei der Besprechung der Bene�tfunktionen in Abschnitt �� wurde bereits erw�ahnt�da� ein Bene�t aus zuvor bestimmten Pre�Bene�ts berechnet wird� Diese werden mit Hilfeder Gewichte der Kanten zwischen den Elementarknoten ermittelt�


Wurde eine Kandidatenmenge eingesetzt� so mu� diese nat�urlich auch auf jeden Clustergra�phen �ubertragen werden� Die Kanten des urspr�unglichen Graphen m�ussen also auf Kantenjedes neuen Graphen �ubertragen werden� Auch hierf�ur wird auf die Elementarknoten derCluster zur�uckgegri�en�

�� Berechnung des Pre�Bene�ts

Beim Pre�Bene�t einer Kante zwischen zwei Elementarknoten handelt es sich immer umdas Gewicht dieser Kante� Inzidiert dagegen mindestens ein echtes Cluster mit der Kante�so gibt es mehrere M�oglichkeiten� den Pre�Bene�t zu berechnen� Auch dieses wurde bereitsin Abschnitt �� angesprochen� Dort wurde aber noch nicht konkret ausgef�uhrt� wie dieserPre�Bene�t ermittelt wird� Das soll an dieser Stelle nachgeholt werden�

Im letzten Abschnitt wurde schon das Problem angesprochen� da� es beim Verbindenzweier Zyklen �v�� vp� und �u�� uq� p � q verschiedene Kombinationsm�oglichkeitengibt� Auch bei der Berechnung des Pre�Bene�ts ist das Berechnen all dieser Kombinationennicht sinnvoll� Daher wird die gleiche Auswahl an Wegkombinationen getro�en� die auchdort besprochen wurde� unabh�angig davon� welche Bene�tfunktion ausgew�ahlt wurde�

Beim Zusammenfassen zweier Cluster wurde eine Selektion �uber alle dann noch m�oglichenWegkombination durchgef�uhrt� da nicht alle gespeichert werden konnten� Das mu� bei derBerechnung des Pre�Bene�ts nicht unbedingt geschehen� da hier nur die Kosten der Wegeeine Rolle spielen� Diese werden aber ohnehin berechnet�

Bestm�ogliche Kombination

Bei der Auswahl der bestm�oglichen Kombination als Bene�t werden alle Wege der beidenbeteiligten Cluster miteinander verbunden und die Kosten der besten dabei entstehendenTour als Pre�Bene�t zur�uckgeliefert�

Alternativ kann die Anzahl der Wege� die aus den beiden Clustern herangezogen werden aufeine kleine Zahl eingeschr�ankt werden� Dann werden nur die ersten k Wege beider Clusterkombiniert� Der dabei ermittelte Wert kann als N�aherung f�ur die tats�achlich bestm�oglicheKombination aufgefa�t werden�

Durchschnitt aller Kombinationen

Wird die bestm�ogliche Kombination als Bene�tfunktion gew�ahlt� kann es passieren� da�die Verbindung zweier Cluster als gut bewertet wird� obwohl es nur eine wirklich gute


Verbindungsm�oglichkeit zwischen ihnen gibt� Die Verbindung eines dieser beiden Clustermit einem anderen h�atte zwar einen schlechteren besten Weg zur Folge� w�urde jedoch nocheine Reihe weiterer guter Wege liefern�

Statt der bestm�oglichen Kombination k�onnte also der Durchschnitt aller Kombinationenbessere Resultate liefern� Daher steht auch eine Bene�tfunktion zur Verf�ugung� die unterallen m�oglichen Kombinationen von Touren den Durchschnitt der Kosten bildet und alsPre�Bene�t liefert�

Auch hier kann die Anzahl der Wege� die f�ur die Berechnung herangezogen werden� aufeine kleine Zahl k gesetzt werden� Dann werden nur die besten k Wege jedes Clusters f�urden Pre�Bene�t ausgewertet�

Schlechteste Kombinationsm�oglichkeit

Eine weitere �Uberlegung f�uhrt dazu� bei der Kombination der Cluster die Kosten derteuersten entstehenden Tour als Pre�Bene�t zu nehmen� Schlie�lich d�urfte ein Clusterpaar�dessen Tourkombination selbst im schlechtesten Fall noch relativ gute Ergebnisse liefert�besonders gut zueinander passen�

Wie in den beiden zuvor geschilderten F�allen� ist auch hier eine N�aherung �uber die Auswahlvon k besten Wegen in beiden Clustern eines m�oglichen Paares vorgesehen�

Abstand der Schwerpunkte

In geometrischen Graphen gibt es eine besondere M�oglichkeit� einen Pre�Bene�t zu er�halten� Man f�uhrt einfach f�ur jedes Cluster den Schwerpunkt aller Elementarknoten mitund betrachtet dann den Abstand zweier Schwerpunkte als Pre�Bene�t� Das hat den Vor�teil� da� unabh�angig von den gespeicherten Wegen ein Wert ermittelt werden kann� wof�urselbstverst�andlich erheblich weniger Zeit ben�otigt wird als bei den oben genannten Bene��tfunktionen�

Beim Berechnen des Pre�Bene�ts wird f�ur jedes Cluster sein n�achster Nachbar �bez�uglichdes Pre�Bene�ts� und der global beste Pre�Bene�t gespeichert� Damit kann dann der Be�ne�t bei der Berechnung des Matchings in konstanter Zeit ermittelt werden�

�� Kandidatenmengen auf echten Clustergraphen

Nachdem nach einem Matching die Cluster verbunden worden sind� m�ussen� sofern ei�ne Kandidatenmenge eingesetzt wird� auch wieder Kanten zwischen den neuen Clustern


eingef�ugt werden� Dazu l�auft das Programm �uber alle Kanten der urspr�unglichen Kan�didatenmenge und pr�uft� ob sich die beiden Elementarknoten am Ende dieser Kante inunterschiedlichen Clustern be�nden� In diesem Fall werden die beiden Cluster durch eineneue Kante verbunden� Der Wert dieser Kante ist der Pre�Bene�t� wie er sich durch dieoben erl�auterte Vorgehensweise ergibt�

Abbildung �� Nachdem beim Matching die grau unterlegten Elementar�knoten gematcht wurden wird die Kandidatenmenge ��Nearest�Neighbour�Subgraph schwarze Linien� auf die neuen Cluster �ubertragen �graue Linien��

�� Artikulationskanten

In d�unn besetzten Graphen entsteht das Problem� da� bestimmte Kanten nicht in einerHamilton�Tour vorkommen� In Abschnitt �� wurde zwar gezeigt� wie ein d�unn besetzterGraph G auf einen vollst�andigen Graphen Kn abgebildet werden kann� so da� eine optimaleL�osung auf Kn auch gleichzeitig eine optimale L�osung in G darstellt� Heuristiken liefernaber nur N�aherungsl�osungen� die unter Umst�anden auf dem urspr�unglichen Graphen keinenHamilton�Zyklus darstellen�

Enth�alt das Matching eine Kante� die in keiner Hamilton�Tour vorkommt� besteht dieGefahr� da� keine zul�assige L�osung gefunden wird� Man ben�otigt also ein Verfahren� mitdem die Aufnahme solcher Kanten in das Matching verhindert werden kann� Diese Kantensind durch folgende De�nition charakterisiert�


De�nition �� Artikulationskante � Gegeben sei ein Graph G � �V�E�� Eine Kanteuv � E hei�t Artikulationskante� wenn sich durch Entfernen der Knoten u und v inklusivealler inzidierender Kanten die Anzahl der Zusammenhangskomponenten in G erh�oht�

Die De�nition ist analog zur bekannten De�nition eines Artikulationspunktes�

Artikulationskanten m�ussen von vornherein aus dem Graphen entfernt werden� Der Al�gorithmus zur Suche aller Artikulationskanten entspricht in etwa dem f�ur die Artikulati�onspunkte� Zun�achst wird von einem ausgesuchten Knoten aus eine Tiefensuche auf demGraphen durchgef�uhrt� In dem entstehenden Baum werden auch sogenannte R�uckw�arts�kanten eingef�ugt� Dieses sind Kanten� die zur�uck in Richtung Wurzel f�uhren� Auf diesemBaum werden gem�a� Satz �� alle Artikulationskanten bestimmt�

Bezeichnung �� Sei G � �V�E� ein Graph� i� j � V � A�B � V �

TG bezeichne einen durch Tiefensuche auf G enstandenen Baum inklusive der R�uckw�arts�kanten�

i� j bedeute� da� es einenWeg in TG von i nach j gibt� der ausschlie�lich Vorw�artskantenenth�alt�

N�i� bezeichne die Menge aller Knoten in TG� die Nachfolger von i sind� inklusive i selbst!N�i� � fj � V � i� jg

Nj�i� sei die Menge N�i� nN�j�

V �i� bezeichne die Menge aller Knoten in TG� die �uber Vorg�anger von i erreichbar sind�ohne da� R�uckw�artskanten benutzt werden! V �i� � fj � V� j �� i � �k � V mit k �i und k � jg�

Vj�i� sei die Menge V �i� n V �j��

A �� B bedeute� da� es keinen Weg aus der Knotenmenge A in die Knotenmenge B gibt�

F�ur diese Arbeit sind nur zusammenh�angende Graphen interessant� Dort gilt f�ur Artiku�lationskanten folgender Satz�

Satz �� Sei G � �V�E� ein zusammenh�angender Graph und TG ein dazugeh�origer� durchTiefensuche entstandener Baum� Eine Kante e � �i� j� � E ist genau dann eine Artikula�tionskante� wenn eine der folgenden Bedingungen zutri�t�

�� e ist Vorw�artskante in TG und


i� i ist Wurzel und

a� j hat mehr als einen direkten Sohn oder

b� i hat mehr als zwei direkte S�ohne oder

c� i hat genau zwei direkte S�ohne und j hat mindestens einen direkten Sohn�

ii� i ist nicht Wurzel und

a� j besitzt mindestens einen direkten Sohn k� so da� gilt N�k� �� V �i� oder

b� i besitzt mindestens einen direkten Sohn k �� j� so da� gilt N�k� �� V �i��

�� e ist R�uckw�artskante und

i� j ist Wurzel und

a� j hat mehr als einen direkten Sohn oder

b� es gibt mindestens einen direkten Sohn k von i� so da� gilt N�k� �� Vj�i��

ii� j ist nicht Wurzel und

a� Vj�i� �� V �j� und N�i� � fig oder

b� f�ur mindestens einen direkten Sohn k von i sind mindestens zwei der Aus�sagen Vj�i� �� V �j�� N�k� �� Vj�i�� N�k� �� V �j� wahr�

Der Beweis dieser Aussage ist o�ensichtlich� Bei dem Baum TG handelt es sich nur umeine andere Darstellungsweise des Graphen� Eine Kante e ist daher Artikulationskante�wenn der Baum in zwei Zusammenhangskomponenten getrennt wird� sobald diese Kanteentfernt wird� In den im Satz angef�uhrten F�allen werden entweder �Aste

�auseinanderge�

brochen� oder voneinander getrennt� Die Kante e ist also in jedem aufgez�ahlten Fall eineArtikulationskante� In jedem anderen Fall gilt dies nicht� Tri�t eine der Aussagen der FormA �� B nicht zu� hei�t das� da� ein Weg aus der einen in die andere Knotenmenge existiert�Die Knotenmengen bleiben also verbunden� Tre�en Aussagen der Form

�� hat direkten

Sohn � � �� nicht zu� werden die entsprechenden �Aste nicht voneinander getrennt� In jedemFall bleibt der Graph zusammenh�angend�

Abbildung �� soll den Sachverhalt an einem konkreten Beispiel verdeutlichen� Die Tiefen�suche starte bei Knoten � und werde immer mit dem Knoten fortgesetzt� dessen Index amkleinsten ist� Dann erh�alt man den rechts dargestellten Baum� Die Kante �� ist eine Ar�tikulationskante� weil Knoten als direkten Sohn Knoten � hat� von dem aus kein Knotenaus V �� f�g erreichbar ist� Eine weitere Artikulationskante ist die Kante �� dennes gilt N�� fg und es gibt keine Kante von V�� f�g nach V �� f�� g�


2

3

7

8

5

6

4

1

2

1

3

6

4

5

7

8

Abbildung �� Ein d�unn besetzter Graph und seine Darstellung als Baum mitR�uckw�artskanten �gestrichelte Linien��

�� Zusammenfassende Beschreibung des Algorith�

mus

Dieses Kapitel soll durch eine ausf�uhrliche Beschreibung des Algorithmus zusammenge�fa�t werden� Die einzelnen Schritte� die in den vorigen Abschnitten detailliert beschriebenwurden� werden zu einem vollst�andigen L�osungsverfahren zusammengestellt�


TSP mit Iteriertem Matching

�� Initialisiere globale Variablen und Datenstrukturen�

�� Berechne gegebenenfalls Kandidatenmenge�

� Berechne Pre�Bene�ts aller Kanten� speichere den Pre�Bene�t der besten inzidieren�den Kante f�ur jeden Elementarknoten und den global besten Pre�Bene�t�

� Wiederhole

i� Entferne Artikulationskanten�

ii� Bestimme Kantengewichte der Clusterkanten �cij � bene�t�i� j�� f�ur Kante�i� j�� Ist das Gewicht kleiner als qmin� setze cij � ��

iii� Berechne MaximumWeight Matching auf Clustergraphen�

iv� Erzeuge aus gepaarten Clustern neue� gr�o�ere Cluster�

v� Verbinde neue Cluster� Kantengewichte sind zun�achst die Pre�Bene�ts�

vi� Vermindere die Selektionsrate um dsel� � � dsel � �

bis nur noch zwei Cluster vorhanden�

�� Suche bestm�ogliche Verbindung der letzten beiden Cluster�

Das Initialisieren der globalen Variablen umfa�t in erster Linie das Setzen der Parameterf�ur die Vorbereitung des Programmablaufs sowie den Ablauf selbst� Hier werden festgelegt�

� Einsatz von Kandidatenmengen

� Mindestgr�o�e des Clustergraphen f�ur Einsatz einer Kandidatenmenge

� Selektion und Selektionsrate

� Abnahmefaktor f�ur die Selektionsrate

� Mindestqualit�at der Kanten

� Bene�tfunktion

� Referenzfaktor der Bene�tfunktion

� Globaler Ein�u� bei der Berechnung des Bene�ts

Bei der gra�schen Version des Programms werden au�erdem die Parameter f�ur die Dar�stellung gesetzt �siehe Kapitel ��


Nachfolgend m�ussen alle Kanten mit dem Pre�Bene�t versehen werden� Waren Kantenge�wichte explizit bei der Beschreibung der Probleminstanz gegeben� werden diese verwandt�Ansonsten mu� f�ur jede Kante eine Distanzfunktion ausgewertet werden� Diese ist durchdie Beschreibung der Instanz festgelegt� Zur schnellen Berechnung der Bene�ts wird zumeinen der beste aller Pre�Bene�ts gespeichert� zum anderen notiert man zu jedem Knotenden besten Pre�Bene�t aller inzidierenden Kanten�

F�ur das Matching werden dann die Pre�Bene�ts der Kanten in die tats�achlichen Kantenge�wichte� die Qualit�at beziehungsweise der Bene�t der Kante� transformiert� Dieses l�a�t sichmit der in Abschnitt �� aufgestellten Formel f�ur jede Kante in konstanter Zeit bew�altigen�Auf dem aktuellen Clustergraphen wird dann ein Maximum Weight Matching bestimmt�Alle Knoten� die nun durch eine Kante des Matchings verbunden sind� werden zu einemneuen� gr�o�eren Cluster zusammengefa�t� Dabei werden unter allen m�oglichen Tourkom�binationen diejenigen ausgew�ahlt� die die Selektionskriterien erf�ullen und mit dem Clusterabgespeichert�

Ist der Clustergraph noch so gro� da� weiterhin die Kandidatenmenge eingesetzt werdensoll� so werden die Kanten des Clustergraphen aus dem vorigen Iterationsschritt herge�nommen und auf den neuen Graphen �ubertragen� Die Kanten werden zun�achst mit denPre�Bene�ts gewichtet� die sich aus den m�oglichen Kombinationen der neuen Cluster erge�ben�

Ist eine Abnahme der Selektionsrate gew�unscht � beispielsweise um zu Beginn des Ver�fahrens auch schlechtere Touren zu speichern� am Ende aber nur noch die guten � sogeschieht dieses jetzt� bevor ein neuer Iterationsschritt mit der Berechnung der Bene�tseingeleitet wird�

Sind nach einer gewissen Anzahl Iterationen nur noch zwei Cluster �ubrig� werden die Tou�ren in diesen beiden hergenommen und alle m�oglichen Kombinationen durchgespielt� Diebestm�ogliche Kombination wird dann als N�aherungsl�osung geliefert�

Zur Aufwandsanalyse sollen zun�achst die einzelnen Schritte unabh�angig voneinanderbetrachtet werden� Das Berechnen der Kandidatenmenge ben�otigt einen Aufwand vonschlimmstenfalls O�n�� Die Ermittlung der ersten Pre�Bene�ts geschieht ebenfalls inO�n�� da jedes Knotenpaar genau einmal untersucht wird�

Die folgenden Schritte werden in einer Schleife durchgef�uhrt� Innerhalb dieser Schleifeverringert sich die f�ur den Aufwand ma�gebliche Zahl k an Clustern� Die Berechnung derBene�ts geschieht f�ur jede Kante in konstanter Zeit� Alle Bene�ts in einer Iteration werdenalso in O�k�� bestimmt� Das Matching�Verfahren hat einen Aufwand von O�k��

Der Aufwand f�ur das Erzeugen der neuen Cluster aus den Paarungen ist abh�angig vonder gew�ahlten Selektion� Bei relativer Selektion wird der Aufwand im schlimmsten Fallexponentiell� da je nach Einstellung der Parameter alle Tourkombinationen gespeichert


werden� Diese m�ussen im n�achsten Schritt wieder miteinander kombiniert werden� Beiabsoluter Selektion dagegen ist die Anzahl an Touren pro Cluster auf einen konstantenWert c beschr�ankt� Daher m�ussen in einem Iterationsschritt f�ur ein Clusterpaar maximal�c�bn

kc� Tourkombinationen berechnet werden� Daraus ergibt sich ein Gesamtaufwand f�ur

diesen Schritt von O�n�

k��

Die Verbindung der Cluster geschieht durch Analyse aller Kanten auf dem ursp�unglichenGraphen� ben�otigt also im schlimmsten Fall O�n�� Die Bewertung der Kanten durch diePre�Bene�ts h�angt allerdings von der Wahl der Bene�tfunktion ab� Die Funktion Abstandder Schwerpunkte ist unabh�angig von der Anzahl der gespeicherten Wege und Element�arknoten in einem Cluster� Daher kann die Bewertung f�ur jedes Paar in konstanter Zeitgeschehen� was einen Gesamtaufwand von O�k�� ergibt� Alle anderen Bene�tfunktionengreifen auf die gespeicherten Wege eines Clusters zur�uck� F�ur die Bewertung einer Kantem�ussen also alle gespeicherten Touren der inzidierenden Cluster miteinander kombiniertwerden� Wie bei der Konstruktion der Cluster bedeutet dieses also einen exponentiellenAufwand bei relativer Selektion und einen Aufwand von O�n�� bei der absoluten Selektion�

Die Schleife wird im schlimmsten Fall n mal durchlaufen� n�amlich dann� wenn bei jedemMatching nur zwei Knoten gepaart werden� F�ur die gesamte Schleife ist daher bei relativerSelektion exponentieller Aufwand n�otig� bei absoluter Selektion ein Aufwand von

O�Pn

k��k� � k� � n�

k� n� � k��

�� O�n�� bei Bene�tfunktion

�Abstand der Schwerpunkte�

O�Pn

k��k� � k� � n�

k� n� � n��

�� O�n�� sonst�

Der Aufwand f�ur den letzten Schritt� die Verbindung der beiden letzten Cluster ist nurabh�angig von der Anzahl der in den beiden Clustern gepeicherten Wege und Element�arknoten� Diese Verbindung l�auft genauso ab� wie die Verbindung zweier Cluster in deneinzelnen Iterationen� Daher gilt auch f�ur den Aufwand die gleiche Aussage�

Zusammenfassend hat das besprochene Verfahren also bei relativer Selektion im worstcase einen exponentiellen Aufwand� bei absoluter Selektion einen Aufwand von O�n�� Imwesentlichen tr�agt die Berechnung des Matchings zu diesem Aufwand bei� Diese ist aberbei Einsatz einer Kandidatenmenge sehr viel schneller� als es die aymptotische Laufzeitvon O�n�� erwarten l�a�t�

Kapitel �

Ergebnisse und Vergleich

Wie man im letzten Kapitel sehen konnte� sind eine Reihe von unterschiedlichen Parame�tereinstellungen f�ur die vorgestellte Heuristik m�oglich� Durch unterschiedliche Einstellun�gen werden sehr verschiedene Ergebnisse erzielt� Welchen Ein�u� die Parameter auf dieQualit�at und die Laufzeit des Verfahrens haben� soll nachfolgend untersucht werden�

Anschlie�end soll eine Einordnung des Verfahrens in die Reihe der in Kapitel vorgestell�ten� bisher bekannten Heuristiken vorgenommen werden�

Alle gemessenen Zeiten sind auf einer Sparc �� Workstation mit Hilfe der Funktiongetrusage�� ermittelt worden� Es wurden zum Teil Messungen wiederholt� um Me�fehlergering zu halten� Dabei ergaben sich Abweichungen der Ergebnisse um etwa � �

�� Ein�u� der Parameter auf die Ergebnisse

Die vorgestellte Heuristik wird durch eine Reihe von Parametern beein�u�t� Viele dieserParameter haben ein gro�es Spektrum an m�oglichen Werten� Es ist daher nicht m�oglich�eine Einstellung zu w�ahlen� mit der f�ur jede Instanz die bestm�ogliche N�aherungsl�osunggefunden wird�

�� Einsatz der Kandidatenmengen

Der Einsatz von Kandidatenmengen wurde in erster Linie mit einer zu erwartenden Verbes�serung der Laufzeit begr�undet� Dieses spiegelt sich in Abbildung �� wider� W�ahrend ohneKandidatenmengen die Laufzeit kubisch mit der Anzahl der Knoten w�achst� ist bei Ein�satz einer Kandidatenmenge �hier Delaunay Graph und ��Nearest�Neighbour Teilgraph�

��

Kapitel � Ergebnisse und Vergleich ��

nur ein lineares Wachstum zu beobachten� Der Grund liegt in der Anzahl der zu bewer�tenden Kanten� Bei einem vollst�andigen Graphen Kn gibt es n � �n � �� Kanten� Dagegenhat jeder Knoten in der hier eingesetzten Kandidatenmenge durchschnittlichen Grad ��Damit gibt es im gesamten Graphen nur rund ��n Kanten� Ein weiterer Grund f�ur die

1200100080060040020000

100

200

300

400

500

600

700

800Zeit in Sekunden

Anzahl der Knoten

mit Kandidatenmenge

ohne Kandidatenmenge

Abbildung �� Vergleich der Laufzeiten gleicher Instanzen mit und ohne Kan�didatenmenge bei identischer Wahl aller anderen Parameter

Kandidatenmengen ist die Tatsache� da� das eingesetzte Programm zur Berechnung desMatchings einen gro�en Speicherbedarf hat� Die Instanz rat�� war die gr�o�te� die auf demeingesetzten Rechner ohne Kandidatenmenge untersucht werden konnte�

Die L�osungsqualit�at sollte durch die Reduktion der Kantenzahl nicht zur�uckgehen� Auchdieses ist sichergestellt� wie Tabelle �� zeigt� Wie in Abschnitt �� erl�autert� wird bei ei�ner vorher festgelegten Gr�o�e des Clustergraphen die Kandidatenmenge

�abgeschaltet��

Dadurch ist es m�oglich� auch Instanzen zu l�osen� bei denen nur eine k�Nearest�NeighbourKandidatenmenge eingesetzt wurde� die einen nicht�zusammenh�angenden Graphen dar�stellt� Ein Test mit dem Delaunay Graph� einem ��Nearest�Neighbour Subgraph und derKombination beider lieferte f�ur unterschiedliche Probleminstanzen identische L�osungen�

Die Berechnung der Kandidatenmenge selbst� ist mit keinem gro�en Rechenaufwand ver�bunden� wie in Abbildung �� zu sehen ist�

�� Wahl der Bene�tfunktion

DieWahl der Bene�tfunktion beein�u�t nicht nur die Qualit�at der L�osung� sondern auch dieLaufzeit �siehe Abschnitt �� In geometrischen Graphen ist im Hinblick auf die Laufzeitdie Bene�tfunktion

�Abstand der Schwerpunkte� die beste Wahl� da dann der Bene�t

einer Kante in konstanter Zeit aus den Pre�Bene�ts ermittelt werden kann� Die Laufzeiten

Kapitel � Ergebnisse und Vergleich �

Anzahl Knoten mit ohneKandidatenmenge

��

Tabelle �� Vergleich der Qualit�at der L�osungen bei den Probleminstanzen ausAbbildung �� Der Einsatz der Kandidatenmenge erh�oht die Kosten der Tournur in einem Fall�

20001800160014001200100080060040020000

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Zeit in Sekunden

Anzahl der Knoten

Abbildung �� Laufzeit f�ur die Berechnung des Delaunay Graphen und des��Nearest�Neighbour Teilgraphen

der anderen Bene�tfunktionen sind abh�angig von der Anzahl der gespeicherten Tourenund�oder der Anzahl der Elementarknoten der beteiligten Cluster�

In Abbildung �� sieht man recht deutlich� da� die Berechnung des Bene�ts aufgrund derAbst�ande der Schwerpunkte zweier Cluster ein gute Wahl ist� Die L�osungsqualit�at ist beidieser Wahl grunds�atzlich hoch� Sie wird nur in Einzelf�allen geringf�ugig �ubertro�en� Dieanderen Bene�tfunktionen existieren in je zwei Varianten� Bei der einen Variante werdenalle Touren der beiden Endcluster einer Kante bei der Berechnung des Bene�ts ber�uck�sichtigt� bei der anderen nur eine feste Zahl k� Diese wurde in diesem Fall auf k �


417 KnotenLösungsqualität654 Knoten

198 Knoten

(Näh

erun

g)

Sch

wer

punk

te

Dur

chsc

hnitt

liche

r W

eg

Bes

ter

Weg

Dur

chsc

hnitt

liche

r W

eg

Sch

lech

test

er W

eg

Bes

ter

Weg

(Näh

erun

g)

Sch

lech

test

er W

eg(N

äher

ung)

Abs

tand

der

0

5

10

15

Abbildung �� Abh�angigkeit der L�osungsqualit�at von der Wahl der Bene�tfunktion

gesetzt� Die N�aherungsvarianten liefern dennoch etwas bessere L�osungen� In allgemeinenGraphen � in denen keine Schwerpunkte existieren und somit die Funktion

�Abstand

der Schwerpunkte�nicht eingesetzt werden kann � sollte also die N�aherungsvariante der

Bene�tfunktion�Bestm�ogliche Kombination� gew�ahlt werden�

Abbildung �� zeigt die Laufzeiten f�ur die verschiedenen Bene�tfunktionen� Diese wurdenermittelt f�ur die Probleminstanzen lin�� pcb� und p�� Es ist zu erkennen� da� dieLaufzeit nicht nur von der Anzahl der Knoten in einem Graphen abh�angig ist� So wird dieInstanz pcb� beispielsweise in drei von vier F�allen schneller abgearbeitet� als die Instanzlin��

Die schnellere Bearbeitung einer Instanz mit der Bene�tfunktion�Abstand der Schwer�

punkte� wird auch hier ersichtlich� W�ahrend f�ur die Instanz p�� bei Einsatz dieser Be�ne�tfunktion eine Gesamt�Laufzeit von etwa �� s gemessen wurde� ergaben sich bei denanderen Funktionen Laufzeiten von etwa �� s� Hierbei wurden nur die Varianten der Funk�tionen eingesetzt� die bei der Berechnung des Bene�ts auf die ersten drei Touren beiderCluster zur�uckgreifen� Werden alle Touren ber�ucksichtigt� sind noch erheblich h�ohere Lauf�zeiten zu beobachten�


(Näh

erun

g)

Sch

lech

test

er W

eg(N

äher

ung)

Sch

wer

punk

te

Bes

ter

Weg

(Näh

erun

g)

Abs

tand

der

Dur

chsc

hnitt

liche

r W

eg

Zeit/sec

654 Knoten442 Knoten318 Knoten

0

50

100

150

200

250

300

350

Abbildung �� Laufzeiten bei verschiedenen Bene�tfunktionen

�� Ein�u der Bene�t�Optionen

Gro�en Ein�u� auf die Bestimmung eines Matchings haben die Parameter� mit denen diegew�ahlte Bene�tfunktion eingestellt wird� Dieses sind im einzelnen die Mindestqualit�at derKanten qmin� der Referenzfaktor fref und der globale Ein�u� g der Pre�Bene�ts bei derBerechnung der Bene�ts�

Der globale Ein�u� sollte m�oglichst niedrig eingestellt sein� wie die Diagramme in Abbil�dung �� zeigen� Im Durchschnitt �uber alle Instanzen erh�alt man bei g � �� das besteErgebnis� Zwar ist in den Abbildungen zu erkennen� da� sich hier nicht immer ein absolutesMinimum einer Messung be�ndet� Es ist aber auch ersichtlich� da� an keiner anderen Stellef�ur alle Instanzen gleichzeitig ein besseres Ergebnis gefunden wird�

�Ahnliche Ergebnisse wie in diesen Abbildungen wurden auch f�ur andere Einstellungen derMindestqualit�at und des Referenzfaktors sowie f�ur andere Instanzen erzielt� Leider sind kei�ne Gemeinsamkeiten in den einzelnen Kurvenverl�aufen zu erkennen� so da� in Einzelf�alleneine sonst gute Wahl des Wertes g zu schlechten Ergebnissen f�uhren kann�

Die Diagramme in Abbildung �� zeigen die Abh�angigkeit der L�osungsqualit�at vom Refe�renzfaktor� In beiden Abbildungen ist zu sehen� da� gute Ergebnisse bei einem Referenz�faktor von fref � �� erzielt werden� In nur einem Fall gibt es eine bessere L�osung� diese


rat783

lin318u574

fl417

1008060402000

5

10

15

20

25

Lösungsqualität

Globaler Einfluß

rat783

lin318

u574

fl417

1008060402000

5

10

20

25

15

Globaler Einfluß

Lösungsqualität

Abbildung �� L�osungsqualit�at in Abh�angigkeit vom globalen Ein�u� des be�sten Pre�Bene�ts bei qmin � �� und fref � �� links� sowie qmin � �� undfref � �� rechts��

1.91.81.71.61.51.41.31.2

10

12

8

14

16

18

20

22Lösungsqualität

Referenzfaktor

c)

b)

a)

a)

b)

c)

1.91.81.71.61.51.41.31.210

11

12

13

14

15

16

Referenzfaktor

Lösungsqualität

Abbildung �� Abh�angigkeit der L�osungsqualit�at vom Referenzfaktor bei derProbleminstanz �� und a� qmin � �� g � �� b� qmin � �� g �� c� qmin � �� g � �� links� und der Probleminstanz lin � bei einerMindestqualit�at von qmin � �� und einem globalen Ein�u� von a� g � �� b� g � �� c� g � �� rechts�

wird allerdings mit globalem Ein�u� g � �� erzielt� Dieses ist aber� wie oben erl�autertkeine besonders g�unstige Wahl�

Der Verlauf der einzelnen Kurven ist hier sehr viel �ahnlicher als dies beim globalen Ein�u�der Fall war� Es ist daher davon auszugehen� da� mit fref � �� ! �� im allgemeinen f�uralle Instanzen gute Ergebnisse erzielt werden�


1008060402000

5

10

15

20

Lösungsqualität

Mindestqualität

u574

rat783

lin318fl417

1008060402000

5

10

15

20

25

Lösungsqualität

fl417

Mindestqualität

lin318rat783

u574

Abbildung �� Abh�angigkeit der L�osungsqualit�at von der Mindestqualit�at beifref � �� und g � �� links� sowie bei fref � �� und g � �� rechts��

Bei der Mindestqualit�at lassen sich weniger gut Aussagen �uber eine geeignete Wahl ma�chen� Die beiden Diagramme in Abbildung �� zeigen f�ur die dargestellten Instanzen einensehr �achen Kurvenverlauf mit leicht ansteigender Tendenz bei zunehmender Mindestqua�lit�at� Daher erscheint die Wahl von qmin � �� ! �� gute Resultate zu liefern� Wie beimglobalen Ein�u� kann es aber auch hier in Einzelf�allen zu schlechten L�osungen kommen�

�� Ein�u der Selektion

Ein ganz wesentlicher Punkt ist neben der Wahl der Bene�tfunktion auch die Art derSelektion und die Selektionsrate� Bei den Messungen stellte sich heraus� da� die relativeSelektion keine gute Wahl darstellt� Als Nachteile waren hier sehr viel gr�o�ere Laufzeitenund erheblicher Speicherbedarf festzustellen� Beispielsweise wurde bei der Probleminstanzd�� bei einer initialen Selektionsrate von �� und einem Abnahmefaktor von �� eineLaufzeit von � �� s gemessen� Bei absoluter Selektion �Selektionsrate �� wurden dage�gen nur knapp � s ben�otigt� Die Testinstanz lin�� mu�te abgebrochen werden� da nichtausreichend Speicherplatz zur Verf�ugung stand�

Die Messungen wurden daher durchweg bei absoluter Selektion durchgef�uhrt� Den Ein��u� der Selektionsrate auf die L�osungsqualit�at zeigt Abbildung �� Die L�osungsqualit�atnimmt f�ur alle Instanzen deutlich zu� wenn die Selektionsrate � also die Anzahl maximalgespeicherter Wege in einem Cluster � von � auf erh�oht wird� Eine weitere� allerdings ge�ringere Verbesserung ergibt sich� werden bis zu sieben Touren pro Cluster abgelegt� WeitereSteigerungen der Selektionsrate bringen im allgemeinen nur wenig� k�onnen in Einzelf�allenallerdings f�ur drastische Verbesserungen sorgen� wie am Beispiel der Instanz p�� zu se�hen ist� Interessant ist die Beobachtung� da� sich die Qualit�at einer L�osung verschlechternkann� wenn sich die Selektionsrate erh�oht�


141210864200

5

10

15

20

25

Selektionsrate

Lösungsqualität

d198

p654

u1060

pcb442

fl1400

lin318

rat783u574

Abbildung �� L�osungsqualit�at in Abh�angigkeit von der Selektionsrate

141210864200

50

100

150

200

250

300Zeit in Sekunden

Selektionsrate

d198

lin318

pcb442

u574

p654

rat783

u1060fl1400

Abbildung �� Laufzeit in Abh�angigkeit von der Selektionsrate

Abbildung �� zeigt� wie sich mit der Anzahl der gespeicherten Wege die Laufzeit erh�oht�Es ist zu sehen� da� die Selektionsrate die Laufzeit mehr beein�u�t� als die Gr�o�e derProbleminstanz �siehe auch Abbildung �� Sollen L�osungen also m�oglichst schnell geliefertwerden� sollte die Selektionsrate auf Werte zwischen � und � eingestellt werden� F�ur guteN�aherungsl�osungen sollten Werte zwischen �� und �� gegebenfalls auch h�oher eingestelltwerden�


�� Ergebnisse im Vergleich zu anderen Heuristiken

Um das vorgestellte Verfahren objektiv mit anderen Heuristiken vergleichen zu k�onnen�wurde die Savings�Heuristik implementiert� Anhand dieser Implementierung konnten dieLaufzeitmessungen aus �Rei �� uberpr�uft werden� Sie wurde gew�ahlt� weil ihr Verfahren�Ahnlichkeiten zum iteriertenMatching aufweist� Beide Verfahren geh�oren zu der Klasse derkonstruktiven Heuristiken� beide setzen aus Teiltouren immer gr�o�ere Touren zusammenund bei beiden bewertet eine Funktion die Qualit�at einer potentiellen Kombination�

2000180016001400120010008006004002000

100

200

300

400

500

600

700Zeit in Sekunden

Anzahl der Knoten

Savings Heuristik

Iteriertes Matching

Abbildung �� Vergleich der Laufzeiten der Savings�Heuristik und des Iterier�ten Matchings

Bei der Savings�Heuristik wurde auf den Einsatz einer Kandidatenmenge verzichtet� obwohldiese bei erheblich besserer Laufzeit keine Minderung der L�osungsqualit�at bedeutet h�atte�Rei �� Abbildung �� zeigt die Laufzeiten f�ur die Savings�Heuristik und das IterierteMatching� Die Savings�Heuristik ist hier �uberlegen� obwohl sie zu den langsamsten der inKapitel vorgestellten Verfahren geh�ort�

Die Tabelle �� gibt einen �Uberblick �uber die L�osungsqualit�at einzelner Probleminstan�zen bei ausgew�ahlten Verfahren� Waren bei einer Heuristik mehrere Varianten untersuchtworden� wurde die jeweils beste in die Tabelle aufgenommen� Es ist zu erkennen� da� dasVerfahren mit iteriertem Matching keine mit den Ergebnissen der Savings�Heuristik oderdes Greedy Algorithmus vergleichbaren Resultate liefert� Da die Laufzeit des Verfahrensh�oher ist als die der anderen Verfahren� ist es keine Alternative zu den bekannten Heuri�stiken�


Instanz N��Neighbour Insertion Christo�des Savings Greedy It� Matchingd�� lin � ��

pcb� � �� u�� p�� rat� �� pr�� u��

pcb�� d�� rl� � �� u� � �� d�� vm�� rl��

Durchschnitt ��

Tabelle �� Vergleich der Qualit�at des Verfahrens mit iteriertemMatching mitverschiedenen anderen konstruktiven Heuristiken� Die Ergebnisse wurden ab�gesehen von denen der Savings�Heuristik �Rei �� entnommen�

Kapitel �

Beschreibung der Benutzerober��ache

Wie in den vorangegangenen Kapiteln deutlich wurde� l�a�t sich das in dieser Arbeit vor�gestellte Verfahren durch eine Vielzahl von Parametern steuern� Eine �ubersichtliche Art�diese Parameter einzustellen� bietet eine graphische Benutzerober��ache� Sie erm�oglicht au��erdem� das Fortschreiten des Algorithmus zu beobachten� also eine Veranschaulichung desVerfahrens�

Neben einer rein textorientierten Fassung des Programms wurde daher eine Version f�urX�Windows implementiert� Beide Versionen nutzen den gleichen Kern� so da� nur die Kom�munikation mit dem Benutzer getrennt programmiert werden mu�te� Auf diese Weise istdie Anpassung an andere Umgebungen m�oglich� indem nur die wenigen Routinen der Be�nutzerschnittstelle angepa�t werden�

F�ur X�Windows wurde die Benutzerober��ache mit Hilfe von Tcl�Tk gestaltet� Umm�oglichst systemunabh�angig zu bleiben� wurde auf die Nutzung besonderer F�ahigkeitendieses Toolkits verzichtet� Im Ende�ekt l�ost jede Auswahl eines Men�upunktes nur denAufruf einer C�Funktion aus� Umgekehrt werden aus C�Funktionen heraus einfach Tcl�Tk�Kommandos aufgerufen� die beispielsweise das Zeichnen einer Linie erm�oglichen� Diese C�Funktionen sind die einzigen� die bei einer Anpassung an andere Systeme ge�andert werdenm�u�ten�

�� Men�uf�uhrung

Nach Aufruf des Programms erscheint eine Ober��ache wie in Abbildung �� dargestellt�Oben be�ndet sich die Hauptmen�uleiste� darunter die Darstellungs��ache und ganz untendie Zeile mit den Statusinformationen� Rechts neben der Darstellungs��ache sind Einstell�optionen zu �nden� mit denen die Darstellung des Graphen beein�u�t werden kann�

��

Kapitel � Beschreibung der Benutzerober��ache ��

Abbildung �� Die Benutzerober��ache

In der Men�uleiste erkennt man die Punkte Datei� Parameter und Start� Diese enthaltendie folgenden Unterpunkte�

Men�upunkt Datei�

�O�nen� zum Einlesen einer Problembeschreibung

Speichern� zum Speichern eines Ergebnisses

Screen Dump� speichert den Inhalt der Darstellungs��ache als Postscript Datei

Beenden� zum Beenden des Programms�

Kapitel � Beschreibung der Benutzerober��ache �

Men�upunkt Parameter�

Vorbereitung� Auswahl von Kandidatenmengen und der zugeh�origen Parameter

Programmablauf� Einstellen der den Programmablauf beein�ussenden Faktoren�Bene�t�Funktion� Selektion� Selektionsrate etc��

Statistik� Abfrage statistischer Informationen nach Ablauf des Programms�

Men�upunkt Start�

Berechne Kandidatenmenge� berechnet nur die Kandidatenmenge und wartet an�schlie�end auf weitere Instruktionen vom Benutzer

Starte Programm� startet die L�osungssuche auf dem geladenen Graphen via Iterier�tem Matching

Schrittweise� wie Starte Programm� jedoch wird nach jedem Matching die aktuelleClustermenge angezeigt und auf weitere Instruktionen des Benutzers gewartet

Vergleichsverfahren starten� berechnet eine L�osung mit Hilfe der Savings Heuristik

Veri�ziere� berechnet die Kosten der kanonischen Tour �� n� �� durcheinen Graphen� Dient zur Veri�kation der Distanzfunktionen�

Mit den Optionen am rechten Rand kann die Darstellung des Graphen und der L�osung be�ein�u�t werden� Mit dem Slider

�Matching�Tiefe� ganz oben kann � nachdem bereits eine

L�osung gefunden und dargestellt wurde � jede einzelne Ebene des L�osungsbaumes darge�stellt werden� Dabei erhalten entgegen der �ublichen Konvention die Bl�atter des Baumes dieTiefe �� die Wurzel entsprechend die Tiefe n� Dementsprechend wird bei der Einstellung kdes Sliders die Menge an Clustern dargestellt� die sich nach dem k�ten Matching ergab�

Wird die Option�Numeriere Knoten� eingeschaltet� wird zu jedem dargestellten Knoten

seine Nummer angezeigt� Dieses macht nur f�ur kleine Graphen oder gro�e Vergr�o�erungs�stufen �siehe unten� Sinn�

Ist die Option�Zeige alle Wege� aktiviert� wird in einem Cluster nicht nur der beste

gespeicherte Weg� sondern jeder in ihm notierte Weg angezeigt� Auch diese Option machtnur im Einzelfall Sinn� da die einzelnen Wege nicht unterschieden werden k�onnen�

Durch Anw�ahlen der Option�Zeige Cluster� kann jedes Cluster nach einem Matching�

schritt durch ein farbiges Polygon unterlegt werden� Das Polygon umschlie�t dazu dieVoronoi�Regionen aller im Cluster enthaltenen Elementarknoten� Im Regelfall stellen glei�che Farben auch gleiche Cluster dar� Stehen jedoch nicht ausreichend Farben zur Verf�ugung�werden auch unterschiedliche Cluster gleich gef�arbt� Diese sind aber immer noch durch dieangezeigten Wege voneinander unterscheidbar�

M�ochte man sich die Kandidatenmenge ansehen� auf der die L�osung bestimmt wurde� somu� der Punkt

�Zeige Kandidatenmenge� gew�ahlt werden�

Kapitel � Beschreibung der Benutzerober��ache �

Um einzelne Bereiche eines Graphen genauer betrachten zu k�onnen� steht eine Vergr�o�e�rungsfunktion zur Verf�ugung� Um diese zu aktivieren� mu� mit der Maus ein Rechteck�uber den Bereich gezogen werden� der vergr�o�ert dargestellt werden soll� Dieser Bereichwird dann auf die Gr�o�e der gesamten Darstellungs��ache ausgedehnt� Verzerrungen sinddabei zul�assig� Um den Bereich zu markieren� ist die Maus zum oberen linken Punkt desgew�unschten Bereiches zu bewegen� die linke Maustaste zu dr�ucken und bei gedr�uckterMaustaste der untere rechte Punkt des Rechtecks anzusteuern� Das Loslassen der Mausta�ste aktiviert die Vergr�o�erung� In jeder Vergr�o�erungsstufe f�uhrt ein Dr�ucken der rechtenMaustaste zur Darstellung des Graphen in Originalgr�o�e�

Wurde eine schrittweise Ausf�uhrung des Verfahrens gew�ahlt� so erscheinen nach jedemMat�ching in der unteren rechten Ecke des Fensters drei Schalt��achen mit den Titeln Schritt�Fortsetzen und Abbrechen� Der Benutzer mu� einen dieser Buttons anklicken� um ent�weder ein weiteres Matching durchzuf�uhren� die Ausf�uhrung ohne weitere Unterbrechungfortzusetzen oder g�anzlich abzubrechen�

In der untersten Zeile� der Statuszeile des Fensters �nden sich einige Informationen zumAblauf des Programms� Ganz links erscheint der Name der geladenen Probleminstanz�in der Mitte erscheinen Meldungen� welche Aktionen das Programm gerade ausf�uhrt undrechts steht die Anzahl der Cluster zum aktuellen Zeitpunkt�

�� Darstellung des Graphen und der L�osung

Ist der geladene Graph darstellbar� so wird er entsprechend der Gr�o�e des Fensters skaliertund angezeigt� Die einzelnen Knoten erscheinen als kleine schwarze Kreise� Kanten alsdurchgezogene Linien� Es werden nur die Kanten angezeigt� die zur L�osung des Problemsoder zu einer Kandidatenmenge � falls deren Ansicht eingeschaltet ist � geh�oren�

Jede Zusammenhangskomponente stellt ein Cluster dar� Diese k�onnen zus�atzlich farbig un�terlegt werden� indem die Option

�Cluster anzeigen� eingeschaltet wird� Wird die eng�ultige

L�osung angezeigt� so werden die beiden letzten Cluster� aus denen diese Tour entstandenist� farbig unterlegt�

Mit dem Slider�Matching�Tiefe� kann der L�osungsbaum nachtr�aglich betrachtet werden�

Wird der Slider ganz nach rechts bewegt� so wird die vollst�andige L�osung angezeigt� Ist derSlider ganz links� werden die Elementarknoten gezeigt� Mit jeder Bewegung nach rechts er�scheint eine weitere Ebene des L�osungsbaumes� also die Cluster� die in den entsprechendenIterationen entstanden sind�

Mit den Darstellungsoptionen k�onnen� wie oben beschrieben� zus�atzlich Darstellungsoptio�nen ein oder ausgeschaltet werden� Jede Auswahl wirkt sich unmittelbar auf die Darstellungaus�


�� Einstellung der Parameter

Abbildung �� Parametereinstellung bei der Gra�schen Benutzerober��ache

Die verschiedenen Parameter werden bei der gra�schen Version des Programms �uber eineneigenen Dialog eingestellt �Abb� �� Im oberen Abschnitt �nden sich sieben sogenannteRadiobuttons� die f�ur die entsprechende Anzahl an Bene�tfunktionen stehen� Darunterbe�ndet sich links ein Abschnitt� in dem die Parameter f�ur die Selektion eingestellt werdenk�onnen� Zwischen absoluter und relativer Selektion wird durch Radiobuttons entschieden�die Selektionsrate nebst ihres Abnahmefaktors wird in zwei Editierfeldern festgelegt�

Rechts daneben �nden sich weitere Editierfelder� in denen Angaben �uber die Kantenbe�wertungen und die Mindestgr�o�e des Clustergraphen f�ur die Kandidatenmenge gemachtwerden k�onnen� Im obersten Feld wird die Mindestqualit�at der Kanten eingegeben� darun�ter der entsprechende Referenzfaktor� also der Faktor� mit dem der k�urzeste Weg in einemCluster multipliziert werden mu� um genau die angegebene Mindestqualit�at zu erreichen�


Der Anteil des global besten Pre�Bene�ts eines Clustergraphen bei der Berechnung derKantenqualit�aten gibt man im dritten Feld ein� Der Wert im vierten Feld� der Anteil derlokalen Pre�Bene�ts� ergibt sich daraufhin automatisch� Die letzte Angabe legt fest� beiwelcher Gr�o�e der Einsatz der Kandidatenmenge beendet ist�

�Anderungen in diesem Dialog werden unmittelbar nach dem Best�atigen durch Klicken desOK�Buttons wirksam� Dadurch k�onnen bei schrittweiser Ausf�uhrung des Programms nochw�ahrend des Programmablaufes Parametereinstellungen modi�ziert werden�

Die Art der Kandidatenmenge wird mit einem eigenen Dialog bestimmt �Abb� �� Ganz

Abbildung �� Dialog zur Einstellung einer Kandidatenmenge

oben be�ndet sich ein Schalter� mit dem ausgew�ahlt werden kann� ob �uberhaupt eine Kan�didatenmenge erstellt werden soll� Wenn ja� kann mit den darunter stehenden Schaltern derDelaunay Graph sowie ein Nearest�Neighbour Subgraph eingeschaltet werden� Die Anzahlder n�achsten Nachbarn wird im Editierfeld darunter eingegeben� Eingaben sind hier nurm�oglich� wenn der Nearest�Neighbour Subgraph eingeschaltet ist�

Wird in den Dialogen mit der linken Maustaste auf den OK�Button unten links geklickt�werden die Einstellungen an das Programm �ubergeben� Das Klicken desAbbrechen�Buttonsunten rechts nimmt alle zuletzt vorgenommenen �Anderungen zur�uck und beendet denDialog� Wird in einem der Editierfelder die Enter�Taste gedr�uckt� entspricht dies einemKlick auf OK� das Bet�atigen der Escape�Taste bedeutet Abbrechen� Mit der Tabulator�Taste gelangt man durch die einzelnen Eingabefelder�

Die in der Abbildung angegebenen Werte sind die Voreinstellungen� Sie entsprechen in etwaden Werten� die nach den Ergebnissen� wie sie im letzten Abschnitt dargestellt wurden�sinnvoll erscheinen�


�� Abfrage statistischer Daten

Wurde L�osung ermittelt� k�onnen �uber den Men�upunkt Parameter�Statistik� � � Informatio�nen zum Programmablauf erfragt werden� Es erscheint ein Fenster �Abb� �� das nebenden Kosten der ermittelten L�osung auch die Laufzeit �uber f�ur einzelne Schritte der Heuri�stik enth�alt�

Abbildung �� Ausgabefenster f�ur statistische Daten

Die Zeitangaben beziehen sich grunds�atzlich auf alle Berechnungen� die w�ahrend des Pro�grammablaufes gemacht wurden� Zeiten� die f�ur Ausgaben auf den Bildschirm ben�otigtwurden sind nicht mit erfa�t�

Kapitel

Zusammenfassung und Ausblick

Mit dieser Arbeit wurde eine neue Heuristik f�ur das TSP vorgestellt� Bevor die Ideen dieserArbeit aufgezeigt wurden� sind zun�achst andere� bereits bekannte Verfahren dargestelltworden� Es folgte eine Skizze der Anforderungen an die Verfahren in der Praxis� Die hiereingef�uhrte Heuristik basiert auf iteriertem Matching� Dieses sorgt durch Paarung vonKnoten zu Clustern daf�ur� da� sich die Gr�o�e eines zu l�osenden Problems immer weiterreduziert� bis nur noch zwei Cluster miteinander verbunden werden m�ussen� Sie geh�ortdaher zu der Klasse der konstruktiven Heuristiken�

Eine wesentliche Idee bei der Konstruktion der Cluster ist das Speichern mehrererHamilton�Touren auf deren Elementarknoten� Es stellte sich heraus� da� die Ergebnisseder Heuristik sich mit zunehmender Zahl an gespeicherten Wegen zun�achst deutlich ver�bessern� Es konnte auch eine Obergrenze von �� f�ur diese Zahl angegeben werden� Wirddiese �uberschritten� ist das Verh�altnis von Qualit�atsverbesserung zur Erh�ohung der Lauf�zeit ung�unstig�

Wichtige Steuermechanismen f�ur die Berechnung eines Matchings stellen die Bene�tfunk�tionen dar� Sie bestimmen das Gewicht beziehungsweise den Bene�t einer Kante im Clu�stergraphen� Dieses ist abh�angig von den in den Endknoten gespeicherten Elementarknotenund Hamilton�Touren� von einem sogenannten Pre�Bene�t aller mit den Endknoten inzidie�renden Kanten und gegebenenfalls von den Pre�Bene�ts anderer Kanten des Graphen� DerPre�Bene�t einer Kante ist dabei ein Wert� der � abh�angig von der Wahl der Bene�tfunk�tion � in etwa den entstehenden Tourkosten bei Verbindung ihrer Endknoten entspricht�Die besten Ergebnisse auf geometrischen Probleminstanzen ergaben sich mit einer Funk�tion� die im wesentlichen vom Abstand der Schwerpunkte zweier Cluster abh�angt� Da sieunabh�angig von den gespeicherten Wegen ist� ergeben sich bei ihr die mit Abstand bestenLaufzeiten� Die L�osungsqualit�at ist dabei nicht nennenswert niedriger als bei Bene�tfunk�tionen� die auch die gespeicherten Wege zur Berechnung der Kantengewichte heranziehen�

Verschiedene Parameter haben Ein�u� auf die Ergebnisse einer Bene�tfunktion� Der Bene�

�

Kapitel � Zusammenfassung und Ausblick ��

�t einer Kante �u� v� kann abh�angig sein von den Pre�Bene�ts der Kanten� die mit u oder vinzidieren einerseits� von den Pre�Bene�ts aller anderen Kanten des Graphen andererseits�Im ersten Fall wird von lokalem Ein�u�� im zweiten Fall von globalem Ein�u� der Pre�Bene�ts untereinander gesprochen� Die besten Ergebnisse wurden bei geringem bis keinemglobalen Ein�u� erzielt� Ein weiterer Parameter f�ur die Bene�tfunktion ergibt sich aus ei�ner geforderten Mindestqualit�at� Eine Kante� die nicht mindestens diese Qualit�at aufweist�wird mit � gewichtet� Sie wird dadurch keinesfalls in ein Matching aufgenommen� Hier er�gaben sich gute Resultate bei der Forderung nach einer Mindestqualit�at von etwa �� Derletzte Parameter ist der sogenannte Referenzfaktor� Bei der Berechnung des Bene�ts einerKante �u� v� ergibt dieser Faktor multipliziert mit dem bestm�oglichen Pre�Bene�t aller mitu oder v inzidierenden Kanten den Pre�Bene�t� der der Mindestqualit�at entspricht� Einegute Wahl dieses Wertes liegt bei etwa ��

Abschlie�end folgte ein Vergleich mit anderen Heuristiken� speziell der Savings�Heuristik�Es ist festzustellen� da� die Savings�Heuristik in k�urzerer Laufzeit bessere Ergebnisse alsdas iterierte Matching erzielt� Das gleiche gilt f�ur den Greedy�Algorithmus� Das iterierteMatching ist daher in dieser Form keine Alternative zu den bekannten Verfahren� EinEinsatz emp�ehlt sich h�ochstens dann� wenn die Darstellung der L�osung als Baum f�ur eineNachoptimierung sinnvoll erscheint�

Zur Visualisierung der Arbeitsweise des Verfahrens sowie der gelieferten L�osungen desVerfahrens wurde eine gra�sche Ober��ache mit Hilfe von Tcl�Tk implementiert� Unterdieser sind alle beschriebenen Parameter einstellbar und die Suche nach einer L�osung kannSchritt f�ur Schritt verfolgt werden� W�ahrend der Implementation des Verfahrens diente sieunter anderem dazu� Schw�achen erster Ans�atze aufzudecken�

Diese Arbeit kann Ausgangspunkt sein f�ur weitere Arbeiten auf dem Gebiet des TravelingSalesman Problem� Beispielsweise k�onnte das Verfahren in einen Backtracking�Rahmen in�tegriert werden� Dabei w�urden berechnete Paarungen schrittweise r�uckg�angig gemacht wer�den� wenn sie sich im Laufe weiterer Iterationen als nicht geeignet erweisen� Dazu m�u�tenTeiltouren w�ahrend des Verfahrens beurteilt werden� Dies kann durch die Berechnung vonunteren Schranken f�ur eine L�osung auf gegebenen Clustergraphen geschehen�

Weiterhin bietet es sich an� das Verfahren zu parallelisieren� Dazu k�onnte der Graph ei�ner Probleminstanz in verschiedene Teilgraphen unterteilt werden� die dann auf die zurVerf�ugung stehenden Prozessoren verteilt werden� Dort werden auf den Teilgraphen N�ahe�rungsl�osungen berechnet� die schlie�lich miteinander verbunden werden� Denkbar w�areauch� die Berechnung des Matchings und das Erzeugen der Cluster als zeitlich aufwendig�ste Aktionen des Verfahrens zu parallelisieren� Die Vorgehensweise hier ist aber nicht soo�ensichtlich� wie im ersten Fall�

Eine andere M�oglichkeit� die Arbeit fortzusetzen� w�are eine Modi�kation f�ur das VehicleRouting Problem� beziehungsweise Spezialf�allen davon� Man w�urde dann nicht mehr for�dern� genau eine Hamilton�Tour zu �nden� Gesucht w�are dann eine Menge von maximal k

Kapitel � Zusammenfassung und Ausblick �

Touren� wobei k die Anzahl der zur Verf�ugung stehenden Fahrzeuge ist� Das vorgestellteVerfahren m�u�te dazu also nur fr�uher abbrechen� wobei sicherzustellen ist� da� jede berech�nete Tour auch eines einer gegebenen Menge an Depots enth�alt� von denen aus Ware verteiltwird� Mit Hilfe von Erg�anzungen bei den Bene�tfunktionen lie�en sich weitere Kostenfak�toren aus der Praxis modellieren� Ein praktischer Einsatz des Verfahrens beispielsweise beider Verwaltung eines Fuhrparks scheint daher m�oglich�

Literaturverzeichnis

�Bel �� M� Bellmore� S� Hong��Transformation of Multisalesmen Problem to the

Standard Traveling Salesman Problem�� Journal of the ACM �� S��

�Chr �� N� Christo�des��Worst Case Analysis of a New Heuristic for the Travelling

Salesman Problem�� Research Report� Carnegie�Mellon University� Pittsbur�gh� �� in� G� Reinelt�

�The Traveling Salesman�� Springer Verlag� Berlin

Heidelberg ��

�Cod �� B� Codenotti� L� Margara��E�cient Clustering Techniques for the Geome�

tric Traveling Salesman Problem�� International Computer Science Institute�Berkeley and Consiglio Nazionale dell Richerche� Pisa� Juni ��

�Ebe �� J� Ebert��E�ziente Graphenalgorithmen�� Akademische Verlagsgesellschaft�

Wiesbaden� ��

�Edm �� J� Edmonds��MaximumMatching and a Polyhedron with ��Vertices�� Jour�

nal of Research of the National Bureau of Standards B �� S� ��

�Fri �� Andreas Fritsch��Verschnittoptimierung durch iteriertes Matching�� Diplom�

arbeit� Universit�at Osnabr�uck� Januar ��

�For �� Steve J� Fortune��A Sweepline Algorithm for Voronoi Diagrams�� Algorith�

mica �� S� ��

�Gab �� H� Gabow��Implementation of Algorithms for Maximum Matching on Non�

bibartite Graphs�� Ph�D� Thesis� Stanford University� ��

�Gar �� R�S� Gar�nkel��Minimizing wallpaper waste� part I� a class of traveling sa�

lesman problems�� Operations Research �� S� ��

�Joh �� D�S� Johnson� C�H� Papadimitriou��Computational Complexity�� in� E�L�

Lawler� J�K� Lenstra� A�H�G� Rinnooy Kan� D�B� Shmoys��The Traveling

Salesman Problem�� Wiley�Interscience� Chichester� �� S� ��

�

Literaturverzeichnis �

�Kop �� H� Kopka��LATEX � Band �� Einf�uhrung�� Addison�Wesley� Bonn� ��

�Kop �� H� Kopka��LATEX � Band �� Erg�anzungen�� Addison�Wesley� Bonn� ��

�Law �� Eugene L� Lawler� J�K� Lenstra� A�H�G� Rinnooy Kan� D�B� Shmoys��The

Travling Salesman Problem�� Wiley�Interscience� Chichester� ��

�Lin �� S� Lin� Brian W� Kernighan��An E�ective Heuristic Algorithm for the Tra�

velling Salesman Problem�� Operations Research �� S� ��

�Mak �� K��T� Mak� A�J� Morton��A Modi�ed Lin�Kernighan Traveling Salesman

Heuristic�� Operations Research Letters � � �� S� ��

�Ous �� John K� Ousterhout��Tcl and the Tk toolkit�� Addison Wesley� Reading�

Massachusetts� ��

�Pot �� Jean�Yves Potvin��Genetic Algorithms for the Traveling Salesman Problem��

Universit$e de Montr$eal� September ��

�Rei �� Gerhard Reinelt��TSPX � A Software Package for Traveling Salesman Pro�

blem Solving� User%s Guide�� Universit�at Augsburg� Dezember ��

�Rei �� Gerhard Reinelt��The Traveling Salesman� Computational Solutions for TSP

Applications�� Springer Verlag� Berlin Heidelberg ��

�Rei �� Gerhard Reinelt��TSPLIB �� Universit�at Heidelberg� World�Wide�Web�

http��www�iwr�uni�heidelberg�de�iwr�comopt�soft�TSPLIB��TSPLIB�html� ��

�Ros �� D�J� Rosenkrantz� R�E� Stearns� P�M� Lewis��An Analysis of Several Heuri�

stics for the Traveling Salesman Problem�� SIAM Journal on Computing �� S� ��

�Sah �� S� Sahni� T� Gonzales��P�complete Approximation Problems�� Journal of

the ACM� �� S� ��

�Sie �� Hans�Christian Siegert��EDV�Unterst�utzung im Fuhrpark�� Verlag moderne

industrie� Landsberg am Lech� ��

�Zie �� Hans�J�org Ziegler��Computerunterst�utzte Transport� und Tourenplanung��

expert�Verlag� Ehningen bei B�oblingen� ��

Erkl�arung

Danksagung

An dieser Stelle m�ochte ich mich bei Herrn Professor Dr� Oliver Vornberger bedanken�der mich w�ahrend dieser Diplomarbeit betreut hat� Au�erdem danke ich Herrn Dipl��Inf�Volker Schnecke� Herrn Dipl��Math� Frank Thiesing und Herrn Dr� Frank Lohmeyer f�urwichtige Hinweise und Anregungen sowie f�ur moralische Unterst�utzung�

Erkl�arung

Ich versichere� da� ich diese Arbeit selbst�andig angefertigt habe und keine au�er den ge�nannten Hilfsmitteln und Quellen verwendet habe�

Osnabr�uck� den �� M�arz ��

Frank Lauxtermann

Date post:	28-Jul-2020
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

Inhaltsviv Zeitaufw and b ei Einsatz einer Kandidatenmenge Laufzeit f ur die Berec hn ung v on...

Documents