Optimierung mittels Nachbarschaftssuche am Beispiel des Rundreiseproblems

Inhalt

Einleitung

1 Das Travelling Salesman Problem
1.1 Eine Benchmark des Operations Research
1.2 Lösungsmethoden

2 Heuristiken
2.1 Nachbarschaftssuche
2.2 Eröffnungsverfahren
2.3 Verbesserungsverfahren und lokale Suchverfahren
2.3.1 Reine Verbesserungsverfahren
2.3.1.1 2-opt Verfahren
2.3.1.2 3-opt Verfahren
2.3.2 Lokale Suchverfahren
2.3.2.1 Simulated Annealing
2.3.2.2 Tabu Search

3 Ausblick

4 Literatur

5 Abbildungen

Anhang

Einleitung

Das Rundreise- oder auch Travelling Salesman Problem ist eines der bekanntesten Probleme der kombinatorischen Optimierung. Leicht zu verstehen und daher häufig vorschnell als einfach lösbar eingestuft, stellte und stellt es die Wissenschaft immer noch vor große Herausforderungen, denn die Ergebnis-findung gestaltet sich schon bei geringer Problemgröße aufgrund sehr großer Lösungsräume als äußerst schwierig.

Die Nachbarschaftssuche ist ein heuristisches Verfahren, das sehr gut zur Ermittlung der Lösung eines Rundreiseproblems eingesetzt werden kann. Durch den Vergleich verschiedener alternativer Lösungen erfolgt eine schrittweise Annäherung an das optimale Ergebnis, das in einer Minimierung der Reisekosten liegt. Dieses Prinzip machen sich alle in dieser Arbeit vorgestellten Heuristiken zu Nutze. Die Güte des Ergebnisses variiert dabei in Abhängigkeit von den jeweiligen Verfahrensregeln.

In Kapitel 2 wird zunächst das Travelling Salesman Problem vorgestellt. In seiner Eigenschaft als Benchmark für Forschung und Entwicklung sind im Laufe der Zeit vor dem Hintergrund der schweren Lösbarkeit vielfältige Methoden entwickelt worden, die auf verschiedene Art und Weise zu Lösungen führen. Die bisher effizientesten und damit am häufigsten einsetzbaren Metho-den sind Heuristiken, die jedoch nur annähernd optimale Ergebnisse liefern. In Kapitel 3 wird zunächst der Begriff Heuristik definiert. Im Anschluss daran folgt die Erläuterung der Systematik der Nachbarschaftssuche in ihrer Eigenschaft als Basis für heuristische Verfahren im Allgemeinen und im Hinblick auf den Zielgedanken des Rundreiseproblems. Der Darstellung eines Eröffnungs-verfahrens, schließen sich in den nächsten Unterkapiteln Ausführungen zu Optimierungsverfahren an. Am Beispiel zweier r-optimaler Verfahren wird die Anwendung von reinen Verbesserungsverfahren in Bezug auf das Rundreise-problem dargestellt. Simulated Annealing und Tabu Search dienen als Beispiele für lokale Suchverfahren im selben Kontext. Abschließend erfolgt ein kurzer Blick in das Feld der Forschung, die sich mit der Entwicklung immer neuer Varianten und Methoden von auf Nachbarschaftssuche basierenden Optimierungsverfahren beschäftigt.

1 Das Travelling Salesman Problem

Die Frage nach einer Zugfolge, mit der ein Springer alle 64 Felder des Schachbretts jeweils einmal besuchen kann, bereitete dem schweizerischen Mathematiker Leonhard Euler bereits im Jahre 1759 Kopfzerbrechen.^[1] Dass sich eine solche errechnen lässt, kann mittlerweile durch den Einsatz mathema-tischer Methoden sehr einfach bewiesen werden. Erweiterungen dieser Problemstellung aber stellen Wissenschaftler auch heute noch vor schwer zu lösende Aufgaben. Man befasst sich allerdings weniger mit dem Schachspiel, statt des Springers ist die Person eines Handlungsreisenden in das Blickfeld der Wissenschaft gerückt und das damit verbundene Problem ist als Rundreise- oder Travelling Salesman Problem bekannt.

Das klassische Rundreiseproblem kann in einfachen Worten erläutert werden: Ausgehend von einem Startpunkt möchte ein Handlungsreisender seine Kunden in n verschiedenen Städten besuchen. Nachdem er den letzten Besuch getätigt hat kehrt er an den Ausgangspunkt zurück. Die Frage ist, welchen Weg der Handlungsreisende fahren muss, um die zurückzulegende Strecke zu minimieren.^[2] Im Folgenden wird davon ausgegangen, dass die Ent-fernung zwischen zwei Städten gleich den Kosten ist, die für die Fahrt von der einen zur anderen Stadt anfallen und die im Zuge des Optimierungsprozesses minimiert werden sollen.

1.1 Eine Benchmark des Operations Research

Aufgrund seiner Anwendbarkeit auf die verschiedensten Situationen, spielt das Rundreiseproblem in unterschiedlichen Varianten eine wichtige Rolle in der kombinatorischen Optimierung. So findet es auf praktischer Ebene neben der klassischen Anwendung unter anderem in der Produktionssteuerung, der Warenkommissionierung oder bei Zuschneideproblemen Einsatz. Für die For-schung ist das Travelling Salesman Problem eine Benchmark zur Entwicklung und Verbesserung neuer Optimierungsverfahren, die wiederum zur Lösung der oben genannten praktischen Probleme angewendet werden.^[3]

Bei der Optimierung eines Fahrweges in Form eines Rundreiseproblems

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1

stellen im Wesentlichen die Vermeidung von Kurzzyklen sowie die Bedingung, dass jeder Ort einmal angefahren und wieder verlassen wird, einzuhaltende Restriktionen dar. Beschränkungen wie etwa die Kapazität der Fahrzeuge oder bestimmte Zeitfenster, innerhalb derer die Kunden besucht werden können, haben keine Bedeutung. Diese finden bei der Tourenplanung Beachtung, der wiederum das Rundreiseproblem zu Grunde liegt. Restriktionen erschweren Optimierungsprozesse dadurch, dass die Existenz von Rundreisen, die ihren Anforderungen nicht genügen, den Lösungsraum unnötig vergrößern. Obwohl sie als nicht ausführbar definiert werden, sind sie zunächst in der Menge aller Lösungen enthalten und müssen vom Optimierungsprozess ausgeschlossen werden.^[4] Formal lässt sich das Rundreiseproblem wie folgt darstellen:

1.2 Lösungsmethoden

Um die Frage nach der kostenminimalen Rundreise exakt zu beant-worten, kann bei einer geringen Menge von Zielorten das Verfahren der völligen Enumeration angewendet werden. Die Anzahl der möglichen Rundreisen ergibt sich aus der Permutation aller Zielorte. Bei n verschiedenen Städten erhält man demnach bis zu n! unterschiedliche Routen. Unter der Voraussetzung etwa, dass der Startpunkt zu Beginn der Suche für jede Rundreise feststeht, sind (n – 1)! mögliche Lösungen vorhanden; ist die Entfernung zwischen zwei Orten unabhängig von der Reiserichtung die gleiche, verringert sich der Lösungsraum auf (n – 1)!/2. Die völlige Enumeration beginnt mit der Generierung einer willkürlichen Rundreise. Dabei müssen evtl. bestehende Restriktionen beachtet werden, deren Verletzung zum Ausschluss eines Fahrweges führt. Die Berech-nung der Länge eines Weges und damit der anfallenden Kosten ermöglicht einen Vergleich einzelner Rundreisen, bei dem jeweils die bis dahin kostengün-stigste als Entscheidungsgrundlage dient. Nachdem alle ausführbaren Rund-reisen verglichen wurden, ist die beste aller Lösungen das Optimum.^[5]

Die Größe eines Travelling Salesman Problems, bestimmt durch die Anzahl der zu besuchenden Zielorte, ist ausschlaggebend für die Art der einzu-setzenden Optimierungsmethode und damit auch für die Güte des Ergebnisses. Ein Beispiel kann Aufschluss über den Aufwand an Zeit geben, den die exakte Ermittlung einer Lösung durch völlige Enumeration bereits bei relativ wenigen Städten erfordert: Es wird angenommen, dass man über einen Computer verfügt, der alle möglichen Lösungen eines 20-Städte-Problems in einer Stunde berechnen kann. Dies führt, ausgehend davon, dass (n – 1)! Lösungen vorliegen, zu 1,216 * 1017 verschiedenen Ergebnissen. Bei 21 Zielorten müssen bereits 20 Stunden Rechenzeit veranschlagt werden, bei 22 Orten 17,5 Tage und bei 25 Orten, die 6,204 * 1023 verschiedene Rundreisen ermöglichen, nahezu 600 Jahre.^[6] Damit wird der Grund für die Beschränkung der Einsatzfähigkeit der völligen Enumeration auf eine geringe Zahl von Zielorten deutlich. Eine Lösungsfindung in annehmbarer Rechenzeit ist in diesem Beispiel schon bei Rundreisen mit mehr als 20 Zielorten nicht möglich.

Aufgrund dieser eingeschränkten Anwendbarkeit wurden im Operations Research verschiedene Algorithmen entwickelt, die auf effizienterem Wege und bei weniger Rechenzeit als die völlige Enumeration zu einer genauen Lösung führen. Bekannte Beispiele sind in diesem Zusammenhang der Simplex Algorithmus^[7] sowie das Branch-and-Bound-Verfahren^[8], die aber im Hinblick auf die Aufgabenstellung dieser Arbeit nicht näher erläutert werden sollen. Die fortschreitende Entwicklung der Informationstechnologie ermöglichte die Lös-ung vieler auch größerer Probleme unter Anwendung dieser Methoden. Beim Travelling Salesman Problem stößt man jedoch auch hier an Grenzen, denn die Zahl der möglichen Rundreisen steigt mit wachsender Anzahl der Zielorte expo-nentiell an und optimale Lösungen können auch durch diese Verfahren häufig nicht in begrenzter Rechenzeit gefunden werden. Versuche, Algorithmen zu entwickeln, durch die derartige Probleme mit polynomialem Aufwand gelöst werden können, schlugen fehl. Damit gehört das Rundreiseproblem zu den NP-schweren Problemen, die durch schwere Lösbarkeit definiert sind.^[9]

Aufgrund der geschilderten Schwierigkeiten verlagerte sich die Aufmerk-samkeit des Operations Research mehr und mehr auf heuristische Verfahren, die auch bei umfangreichen Problemstellungen in annehmbarer Rechenzeit zu annäherungsweise optimalen Ergebnissen führen. Im folgenden Kapitel werden ausgehend von einer Definition des Begriffs Heuristik verschiedene Verfahrens-weisen erläutert, mit deren Hilfe Probleme der kombinatorischen Optimierung gelöst werden können.

2 Heuristiken

Eine endgültige und allseits akzeptierte Definition des Begriffs Heuristik gibt es aufgrund der Vielzahl der in Theorie und Praxis angewendeten Metho-den nicht. Die folgende versucht einige Hauptmerkmale in sich aufzunehmen:

„A heuristic technique (or simlpy a heuristic) is a method which seeks good (i. e. near optimal) solutions at a reasonable computational cost without being able to guarantee optimality, and possible not feasibility. Unfortunately, it may not even be possible to state how close to optimality a paticular heuristic solution is.”^[10]

Obwohl dieser Definition eine Problematik in Bezug auf die Genauigkeit und Umsetzbarkeit von Lösungen zu entnehmen ist, führen viele moderne Me-thoden zu qualitativ hochwertigen Ergebnissen.^[11] In Abhängigkeit von Problem-stellung und Problemstruktur folgen Heuristiken jeweils besonderen Regeln der Lösungsfindung und -verbesserung. Dabei gibt es heuristische Verfahren, die speziell auf ganz bestimmte Problemstellungen zugeschnitten sind und andere, die als Metastrategien bezeichnet werden und in unterschiedlichen Zusammen-hängen Anwendung finden können. Zu dieser Gruppe gehören unter anderem Tabu Search und Simulated Annealing, die in Bezug auf das Thema dieser Arbeit zu den lokalen Suchverfahren gezählt werden. Sie finden ebenso wie die, der anderen Gruppe zugehörigen, reinen Verbesserungsverfahren gewöhnlich in Kombination mit Eröffnungsverfahren Anwendung. Domschke definiert mit Relaxionsverfahren und unvollständig ausgeführten exakten Verfahren zwei weitere Gruppen heuristischer Methoden, die im Rahmen dieser Ausführungen jedoch nicht von Bedeutung sind.^[12]

In den folgenden Unterkapiteln wird zunächst das Prinzip der Nachbarschaftssuche im Allgemeinen erläutert, um darauf aufbauend die Strukturen der anderen Verfahren darzustellen.

2.1 Nachbarschaftssuche

Die Nachbarschaftssuche ist die Basis vieler heuristischer Anwendungen zur Lösung von Problemen der kombinatorischen Optimierung. Isoliert betrach-tet ist sie eine einfache Methode, um gute, annäherungsweise optimale Ergeb- nisse zu erarbeiten.^[13] Das ihr zu Grunde liegende Prinzip kann wie folgt verbali-siert werden: Eine mögliche Lösung einer gegebenen Problemstellung wird durch den Vektor x ausgedrückt, wobei die Menge aller ausführbaren Lösungen durch X definiert ist. Die Zielfunktion c(x) bestimmt die Kosten dieser Lösung. Jede Lösung x Î X besitzt eine gewisse Menge von Nachbarlösungen N(x) Ì X, die Nachbarschaft von x genannt werden. Jede Lösung x’ Î N(x) kann direkt durch einen von x ausgehenden Zug erreicht werden. (Unter einem Zug ist beim Rundreiseproblem im Kontext dieser Arbeit der Tausch von Kanten zu verstehen. Eine Kante ist die Verbindungsstrecke zwischen zwei Zielorten, die auch als Knoten bezeichnet werden.) Somit enthält N(x) alle Lösungen, die sich durch einmalige Anwendung einer Transformationsvorschrift aus x ergeben.^[14]

Die Darstellung dieses Vorgangs in Form eines Pseudo-Codes kann Abbildung 2 entnommen werden. Besonders zu beachten ist dabei der zweite Schritt ‚Auswahl und Abbruch’, der in der geschilderten allgemeinen Form keine näher spezifizierten Auswahl- und Abbruchkriterien beinhaltet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2

Durch Definition von Auswahl- und Abbruchkriterien in Schritt 2.1 und, falls erforderlich, geringe Modifikationen in den anderen Teilschritten, können sehr leicht Erweiterungen und Variationen in den Suchvorgang implementiert werden. Auf diese Weise ist es möglich, verschiedene Optimierungsverfahren auf Basis der vorgegebenen Struktur darzustellen.^[15]

[...]

^[1] vgl. Michalewicz; Fogel (2000), S. 189.

^[2] vgl. Domschke (1997), S. 100.

^[3] vgl. Reinelt (1994), S. 1.

^[4] vgl. Gudehus (2004), S. 863 f.

^[5] vgl. Gudehus (2004), S. 863 f.

^[6] vgl. Reeves; Beasley (1993), S. 7.

^[7] vgl. dazu Hillier; Lieberman (1997), S. 46 ff.

^[8] vgl. dazu Domschke (1997), S. 6 ff.

^[9] vgl. Domschke; Drexl (2002), S. 114 ff. und Reeves; Beasley (1993), S. 8 ff.

^[10] Reeves, (1996), S.5.

^[11] vgl. Ebenda, S.5.

^[12] vgl. Domschke (1997), S. 20 ff.

^[13] vgl. Voudouris; Tsang (1999), S. 470.

^[14] vgl. Glover; Laguna (1993), S. 83 f.

^[15] vgl. Glover;Laguna (1993), S. 83 f.