Bibelschule und Problem des Handlungsreisenden: Unterschied zwischen den Seiten

Inhalt gelöscht Inhalt hinzugefügt

Inline

Version vom 19. August 2006, 19:05 Uhr

Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Der Weg ist der kürzeste von 43589145600 möglichen.

Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein kombinatorisches Problem der Mathematik und der theoretischen Informatik. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist.

Komplexitätstheoretisch gehört das TSP zur Klasse der NP-vollständigen Probleme. Vereinfacht bedeutet dies, dass die Laufzeit jedes deterministischen Algorithmus, der für dieses Problem stets optimale Lösungen liefert, exponentiell von der Anzahl der Städte abhängt. Daher lässt sich bereits bei wenigen Städten nur sehr schwer die bestmögliche Rundreise finden.

Seit seiner ersten Erwähnung als mathematisches Problem im Jahre 1930 haben sich viele Forscher damit befasst und neue Optimierungsverfahren daran entwickelt und erprobt. Heute steht eine Vielzahl von heuristischen Verfahren sowie verschiedene Methoden der ganzzahligen linearen Optimierung zur Verfügung, um Instanzen mit mehreren Tausend Knoten optimal lösen zu können.

Das Problem des Handlungsreisenden hat schon in der Reinform viele praktische Anwendungen, wie z. B. in der Tourenplanung oder im Design von Mikrochips. Noch häufiger tritt es allerdings als Unterproblem auf, wie beispielsweise bei der Verteilung von Waren, bei der Planung von Touren eines technischen Kundendienstes, oder bei Pannendiensten. In solchen Fällen müssen oft Zusatzbedingungen wie Zeitfenster oder Kapazitäten beachtet werden, was das Problem wesentlich schwerer lösbar macht.

Geschichte

Wann das Problem des Handlungsreisenden das erste Mal wissenschaftlich untersucht wurde, ist unklar. Aus dem Jahre 1832 ist ein Handbuch für Handlungsreisende bekannt (Titel: Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), in dem das Problem erwähnt, aber nicht mathematisch behandelt wird. Statt dessen werden Beispieltouren für einige Regionen Deutschlands und der Schweiz vorgeschlagen.

Datei:W r hamilton.jpeg

William Rowan Hamilton

Als früher Vorläufer des Problems kann das Icosian Game von William Rowan Hamilton im 19. Jahrhundert gesehen werden, bei dem es darum ging, in einem Graphen Touren zwischen 20 Knoten zu finden. Die erste explizite Erwähnung als mathematisches Optimierungsproblem scheint jedoch auf Karl Menger zurückführbar zu sein, der dieses 1930 in einem mathematischen Kolloquium in Wien folgendermaßen formulierte:

„Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden.“

Schon bald darauf wurde die heute übliche Bezeichnung Traveling Salesman Problem durch Hassler Whitney an der Princeton University eingeführt.

Neben der einfachen Definition und Verständlichkeit der Aufgabenstellung zeichnet sich das Problem des Handlungsreisenden dadurch aus, dass die Bestimmung guter Lösungen vergleichsweise leicht ist, während das Finden einer beweisbar optimalen Lösung sehr schwer ist. Aufgrund dieser Eigenschaften hat sich das Problem in der zweiten Hälfte des 20. Jahrhunderts zu einer Art Spielwiese zur Entwicklung neuer Optimierungsverfahren entwickelt. Viele heutige Standardmethoden der ganzzahligen linearen Optimierung, wie Schnittebenenverfahren, Branch-and-Cut und verschiedene heuristische Ansätze, sind am Beispiel des TSP entwickelt und getestet worden.

In den 1950er und 1960er Jahren gewann das Problem sowohl in Europa als auch in den USA zunehmend an wissenschaftlicher Popularität. Besonders herausragende Beträge stammen von George Dantzig, Delbert Ray Fulkerson und Selmer M. Johnson, die 1954 am Institut der RAND Corporation in Santa Monica sowohl die erste Formulierung des TSP als ganzzahliges lineares Programm als auch ein Schnittebenenverfahren zu dessen Lösung entwickelten. Mit den neuen Methoden konnten sie eine Instanz mit 49 Städten optimal lösen. In den 1960er und 1970er Jahren befassten sich zahlreiche interdiszplinäre Forschergruppen mit der Mathematik des Problems und dessen Anwendungen u. a. in der Informatik, den Wirtschaftswissenschaften, der Chemie und der Biologie.

Richard M. Karp bewies im Jahre 1972 die NP-Vollständigkeit des Problems des Handlungsreisenden und lieferte damit auch eine theoretische Begründung für seine schwere Lösbarkeit in der Praxis. Größere Fortschritte darin wurden Ende der 1970er und 1980er Jahren erzielt, als es Martin Grötschel, Manfred Padberg, Giovanni Rinaldi und anderen gelang, mit Hilfe von neuen Schnittebenen und einem Branch-and-Cut-Verfahren Probleminstanzen mit bis zu 2392 Städten optimal zu lösen. In den 1990er Jahren begannen David Applegate, Robert Bixby, Vašek Chvátal und William Cook mit der Entwicklung des Programms Concorde, das an sämtlichen Lösungsrekorden der letzten Jahre beteiligt war. Im Jahre 2004 berechneten sie in Zusammenarbeit mit Keld Helsgaun eine beweisbar optimale Tour durch 24.978 schwedische Städte, was bislang der Weltrekord ist. Für Instanzen mit mehreren Millionen Städten konnten sie mit Hilfe zusätzlicher Dekompositionstechniken Touren bestimmen, deren Länge beweisbar weniger als 1% vom Optimum entfernt liegt.

Mathematische Beschreibung

Modellierung als Graph

Das Problem des Handlungsreisenden lässt sich mathematisch mit Hilfe eines Graphen modellieren, also aus Knoten und Kanten. Dabei repräsentieren die Knoten (im Bild: A bis D) die Städte, während sich jede Kante $(i,j)$ zwischen zwei Knoten $i$ und $j$ zusammen mit ihrer Länge $c_{ij}\geq 0$ je nach Zusammenhang beispielsweise als geographische Länge einer Verbindung, als Reisezeit oder als Kosten einer Reise zwischen zwei Städten interpretieren lässt. Eine Tour (auch Hamiltonkreis genannt) ist ein Kreis in diesem Graphen, der jeden Knoten genau einmal enthält. Ziel ist es, eine möglichst kurze Tour zu finden.

Um die Untersuchung des Problems zu vereinfachen und um sicherzustellen, dass es eine Tour gibt, wird meist angenommen, dass der Graph vollständig ist, dass also zwischen je zwei Knoten immer eine Kante existiert. Dies lässt sich dadurch erreichen, dass überall dort, wo keine Kante existiert, eine künstliche, sehr lange Kante eingefügt wird. Aufgrund ihrer hohen Länge wird eine solche Kante nie in einer kürzesten Tour vorkommen, es sei denn, es gäbe sonst keine Tour.

Je nach Eigenschaften der Kantengewichte werden noch unterschiedliche Spezialfälle des Problems unterschieden, von denen die wichtigsten das symmetrische und das metrische TSP sind.

Symmetrisches TSP

Beim allgemeinen asymmetrischen TSP können die Kanten in Hin- und Rückrichtung unterschiedliche Länge haben, so dass dieses Problem mit Hilfe eines gerichteten Graphen modelliert werden muss. Er reicht also nicht, bloß von der Verbindung zwischen zwei Knoten und ihrer Länge zu sprechen, zusätzlich muss noch die Richtung angegeben werden.

Beim symmetrischen TSP dagegen sind für alle Knotenpaare $(i,j)$ die Kantenlängen in beide Richtungen identisch, d. h. es gilt $c_{ij}=c_{ji}$ . Als Konsequenz davon hat jede Tour in beide Richtungen dieselbe Länge. Die Symmetrie halbiert also die Anzahl der möglichen Touren. Ein symmetrisches TSP wird üblicherweise mit Hilfe eines ungerichteten Graphen modelliert (wie im Bild). Ein Traveling Salesman Problem zwischen realen Städten kann asymmetrisch oder symmetrisch sein, je nachdem, ob beispielsweise durch Baustellen oder Einbahnstraßen der Weg in eine Richtung länger dauert als in die andere oder nicht.

Metrisches TSP

Ein symmetrisches TSP heißt metrisch, wenn zusätzlich seine Kantenlängen die Dreiecksungleichung erfüllen. Anschaulich bedeutet dies, dass sich Umwege nicht lohnen, weil die direkte Verbindung von $i$ nach $j$ nie länger ist als der Weg von $i$ nach $j$ über einen dritten Knoten $k$ :

c_{ij}\leq c_{ik}+c_{kj}

Solche Kantenlängen definieren eine metrische Distanzfunktion auf der Knotenmenge, also ein Entfernungsmaß, das die intuitiv von einem Abstand erwarteten Bedingungen erfüllt. Mehrere in der Praxis häufig auftretende Distanzfunktionen sind metrisch, erfüllen also die Dreiecksungleichung:

die euklidische Metrik des euklidischen TSP,
die Manhattan-Metrik (auch City-Block-Metrik) des rektilinearen TSP, bei der die Distanz zwischen zwei Knoten eines gitterförmigen Graphen (wie dem Straßennetz von Manhattan) die Summe der Entfernungen in x- und y-Richtung ist,
oder die Maximums-Metrik, bei der die Distanz zwischen zwei Knoten eines gitterförmigen Graphen das Maximum der Entfernungen in x- bzw. y-Richtung ist.

Die letzten beiden Metriken finden beispielsweise Anwendung beim Bohren von Leiterplatten, wo ein Bohrer, der eine vorgegebene Menge von Löchern in möglichst kurzer Zeit abarbeiten muss, in beide Dimensionen unabhängig bewegt werden kann, um von einem Loch zum nächsten zu gelangen. Die Manhattan-Metrik entspricht dem Fall, dass die Bewegung in beide Richtungen nacheinander erfolgt, während bei der Maximum-Metrik beide Bewegungen gleichzeitig erfolgen und die Gesamtzeit von der jeweils längeren Strecke in x- bzw. y-Richtung bestimmt wird.

Distanzen, die aus Entfernungstabellen in Straßenkarten entnommen werden, sind nicht notwendigerweise metrisch, weil dort oft die km-Länge eines zeitlich kürzesten Weges angegeben ist, der nicht unbedingt ein kürzester Weg bzgl. der Reisestrecke ist. Falls es im praktischen Planungsproblem zulässig ist, Orte mehrfach zu besuchen, kann man das Problem auf ein metrisches TSP im sogenannten Distanzgraphen reduzieren. Dort entspricht die Kantenlänge zwischen zwei Knoten $i$ und $j$ der Länge eines kürzesten $i-j$ -Weges bzgl. der ursprünglichen Kantenlängen $c_{ij}$ . Die so definierten neuen Kantenlängen erfüllen immer die Dreiecksungleichung.

Modellierung als ganzzahliges lineares Programm

Ein Ansatz zur Lösung des Problems ist die ganzzahlige lineare Optimierung. Dazu muss es als ganzzahliges lineares Programm formuliert werden, in dem die Entscheidungen durch Variablen und die Bedingungen durch lineare Ungleichungen beschrieben werden. Hierfür gibt es mehrere mögliche Varianten. Beispielhaft soll hier eine Formulierung für das symmetrische TSP mit Knotenmenge $V$ vorgestellt werden. Für jede Kante $\{i,j\}$ wird eine binäre Variable $x_{ij}\in \{0,1\}$ eingeführt, die für eine gegebene Tour angibt, ob die Kante $\{i,j\}$ in dieser Tour enthalten ist ( $x_{ij}=1$ ) oder nicht ( $x_{ij}=0$ ). Jede Tour lässt sich auf diese Art durch Angabe der zugehörigen Variablenwerte angeben, aber nicht jede 0-1-Belegung der Variablenwerte definiert eine Tour. Die Bedingungen dafür, dass eine Variablenbelegung eine Tour definiert, lassen sich durch lineare Ungleichungen ausdrücken:

Jeder Knoten muss über genau zwei Tourkanten mit den restlichen Knoten verbunden sein, nämlich durch eine hinein- und eine hinausführende Kante:

\sum _{j\in V\setminus \{i\}}x_{ij}=2\qquad (1)

für alle $i\in V$ . In der Summe ist jeder Summand $x_{ij}$ entweder 1 (in der Tour enthalten) oder 0 (nicht enthalten). Die Summe zählt daher genau die Zahl der Kanten der Tour, die den Knoten $i$ als Endknoten haben. Sie muss den Wert 2 annehmen, da jeweils eine Kante hinein- und hinausführen muss. Im nebenstehenden Bild ist ein Knoten $i$ mit ein- und ausgehenden Kanten dargestellt, wobei die Tourkanten fett gekennzeichnet sind. An den Kanten stehen die Werte $x_{ij}$ , die zu den oben genannten Summen beitragen.

Die obige Bedingung wird nicht nur von Touren erfüllt, sondern auch von Variablenbelegungen, die mehrere getrennte Kreise (sogenannte Kurzzyklen) beschreiben, wobei jeder Knoten in genau einem Kreis enthalten ist (siehe Bild). Um so etwas auszuschließen, müssen noch Kurzzyklusungleichungen (auch Subtour-Eliminationsbedingungen genannt) erfüllt werden. Sie besagen, dass jede Knotenmenge $S\subset V$ , die weder leer ist noch alle Knoten enthält, durch mindestens zwei Kanten der Tour mit den restlichen Knoten verbunden sein muss:

\sum _{i\in S,\;j\notin S}x_{ij}\geq 2\qquad (2)

für alle Knotenmengen $S$ mit $1\leq |S|\leq |V|-1$ . Die Summe zählt alle Kanten der Tour zwischen einem Knoten $i\in S$ und einem anderen Knoten $j\notin S$ . Zur Vermeidung redundanter Ungleichungen kann man sich auch auf Knotenmengen $S$ mit mindestens zwei und höchstens $|V|-2$ Knoten beschränken. Im nebenstehenden Bild sind wieder die Kanten $\{i,j\}$ mit $x_{ij}=1$ fett gezeichnet, während die übrigen Kanten den Wert $x_{ij}=0$ haben. Das Hinzufügen der Bedingung (2) für die Knotenmenge $S$ , die aus den drei linken Knoten besteht, würde dafür sorgen, dass S durch mindestens zwei Tourkanten mit den drei rechten Knoten verbunden sein muss, und damit die beiden gezeigten Kurzzyklen ausschließen.

Man kann zeigen, dass jede 0-1-Belegung der Variablen $x_{ij}$ , die alle Ungleichungen vom Typ (1) und (2) erfüllt, eine Tour definiert. Ziel ist es jetzt, unter allen Touren eine kürzeste zu finden:

\min \;\{\sum _{i\in V}\sum _{j\in V\setminus \{i\}}c_{ij}x_{ij}|x\;\mathrm {erf{\ddot {u}}llt\;(1)\;und\;(2)} \}.\qquad (3)

Da die Variablen $x_{ij}$ nur die Werte 0 oder 1 annehmen, zählt die Summe genau die Längen $c_{ij}$ der Kanten $(i,j)$ zusammen, die in der Tour enthalten sind.

Dieses ganzzahlige lineare Programm tatsächlich optimal zu lösen, ist schon für relativ kleine Anzahlen von Städten schwer, da die Zahl der Ungleichungen vom Typ (2) exponentiell mit der Anzahl der Städte wächst. Varianten dieser Formulierung können aber mit Hilfe von Schnittebenenverfahren bearbeitet werden, bei denen die Ungleichungen (2) erst dann hinzugefügt werden, wenn sie tatsächlich gebraucht werden.

Lösungsverfahren

Bei der Suche nach einer Lösung für das Problem des Handlungsreisenden ist eine der wohl grundlegendsten Fragen die nach der Anzahl der möglichen Rundreisen. In jedem Knoten der Tour stehen dem Handlungsreisenden jeweils alle Städte zur Auswahl, die er noch nicht besucht hat. Da der Ausgangspunkt beliebig ist, ergeben sich insgesamt $(n-1)!$ mögliche Touren für ein asymmetrisches und $(n-1)!/2$ Touren für ein symmetrisches TSP.

Das Problem des Handlungsreisenden ist NP-vollständig, auch wenn eine bestimmte Metrik vorausgesetzt wird. Für metrische TSP gibt es jedoch verschiedene polynomiale Heuristiken.

Exakte Lösungsverfahren

Da es nur endlich viele Rundreisen gibt, ist es theoretisch möglich, alle Touren aufzuzählen, für jede Tour ihre Länge zu berechnen und sich die kürzeste herauszusuchen. Praktisch ist dies jedoch nicht durchführbar, da die Anzahl der möglichen Touren mit $n!$ schneller als jede Exponentialfunktion wächst und es beispielsweise schon bei nur 15 Städten über 87 Milliarden mögliche Rundreisen gibt.

Mit Methoden der ganzzahligen linearen Optimierung, insbesondere Branch-and-Cut (als Verbindung von Branch-and-Bound mit Schnittebenenverfahren), lassen sich Instanzen in praktisch relevanten Größenordnungen beweisbar optimal lösen, oder zumindest die Güte einer gefundenen Tour im Vergleich zu einer Optimallösung abschätzen. Diese Verfahren betrachten das Problem als konvexes Polytop (mehrdimensionales Vieleck), über dem die lineare Zielfunktion (3) zu minimieren ist, die die Länge einer Tour angibt. Jede Ecke des Polytops entspricht einer Tour, so dass das Ziel ist, eine Ecke mit minimalem Zielfunktionswert zu finden. Da das Polytop nicht genau bekannt ist, wird stattdessen ein größeres Polytop betrachtet, das einfacher zu behandeln ist und das ursprüngliche Polytop enthält. Durch Lösen vieler linearer Programme, Abschneiden nicht benötigter Teile des größeren Polytops mit Hilfe von Schnittebenen (was in etwa dem Hinzufügen weitere (Un)gleichung vom Typ (1) oder (2) entspricht) sowie durch Aufteilung in mehrere Teilpolytope mit Hilfe von Branch-and-Bound wird versucht, eine optimale Ecke des inneren Polytops zu bestimmen. Eine genauere Beschreibung dieser Verfahren ist im Artikel Ganzzahlige lineare Optimierung zu finden.

Die alleinige Anwendung dieser Verfahren reicht meist nicht aus, um schnell gute Lösungen zu finden. Ihr Hauptvorteil liegt darin, dass sie Angaben liefern, wie lang eine kürzeste Tour mindestens sein muss. Mit einer solchen unteren Schranke für den optimalen Lösungswert lässt sich abschätzen, wie gut eine gefundene Tour im Vergleich zu einer optimalen Rundreise ist, ohne diese zu kennen. Hat man beispielsweise eine untere Schranke von 100 und eine Tour der Länge 102 gefunden, beträgt der so genannte Optimalitätsgap, also der relative Abstand zwischen oberer und unterer Schranke, (102-100)/100 = 2%. Da eine optimale Tour nur zwischen 100 und 102 liegen kann, kann der gefundene Lösungswert 102 ebenfalls höchstens 2% vom Optimalwert entfernt sein. Wenn die Länge einer gefundenen Tour genauso groß ist wie die untere Schranke, ist damit bewiesen, dass die gefundene Lösung optimal ist. Um gute Touren zu finden, werden diese exakten Verfahren oft mit Heuristiken kombiniert, von denen einige im nachfolgenden Abschnitt beschrieben werden.

Heuristiken

Um schnell zu brauchbaren Lösungen zu kommen, sind meist Heuristiken, also Näherungsverfahren, notwendig, die aber in der Regel keine Güteabschätzung für die gefundenen Lösungen liefern. Je nachdem, ob eine Heuristik eine neue Lösung konstruiert oder ob sie versucht, eine bestehende Lösung zu verbessern, wird sie als Eröffnungs- (auch Konstruktions-) oder Verbesserungsverfahren bezeichnet.

Eröffnungsverfahren

Datei:Nearest Neighbor Heuristik.png

Nearest-Neighbor-Heuristik

Dem intuitiven Vorgehen eines Handlungsreisenden entspricht wohl am ehesten die Nearest-Neighbor-Heuristik (nächster Nachbar). Von einer Stadt ausgehend wählt diese jeweils die nächstgelegene als folgenden Ort aus. Dieses wird sukzessive fortgesetzt, bis alle Städte bereist wurden und der Handlungsreisende zum Ausgangsort zurückgekehrt ist. In jeder Stadt muss also der kürzeste ausgehende Weg gesucht werden. Maximal kann es pro Stadt nur so viele ausgehende Kanten geben, wie Knoten im Graphen vorhanden sind. Daraus ergibt sich eine algorithmische Komplexität von O(n²), die Anzahl der Rechenschritte hängt also quadratisch von der Zahl der Städte ab. Dass diese Heuristik im Allgemeinen jedoch nicht die beste Lösung liefert, liegt daran, dass die Distanz zwischen der Ausgangsstadt und der letzten besuchten Stadt bis zuletzt nicht berücksichtigt wird. Die Nearest-Neighbor-Heuristik kann beliebig schlechte Ergebnisse liefern, das heißt, es gibt keinen konstanten, instanzunabhängigen Approximationsfaktor für den Lösungswert im Vergleich zum Optimalwert.

Ein ganze Klasse weiterer Eröffnungsverfahren bilden die sogenannten Einfüge-Heuristiken. Die einfachsten Varianten davon sind die Nearest-Insertion-Heuristik (nächste Einfügung) und die Farthest-Insertion-Heuristik (entfernteste Einfügung). Gegeben seien (wenige) einander benachbarte Städte, für die sich durch exakte Verfahren schnell eine optimale Rundreise ermitteln lässt. Nun wird schrittweise überprüft, welche noch nicht besuchte Stadt am nächsten (beziehungsweise am entferntesten) zu einer der Verbindungslinien der bisherigen Rundreise liegt. Ist diese Stadt gefunden, so wird sie zwischen den ihr am nächsten liegenden Städten in die Tour eingebaut. Das Verfahren wird solange fortgesetzt, bis die Rundreise alle Städte umfasst. Auch die Lösungen dieser Heuristik können im Vergleich zu einer Optimallösung beliebig schlecht sein.

Die Minimum-Spanning-Tree-Heuristik (MST) berechnet zunächst einen minimal aufspannenden Baum, also einen Graphen, in dem alle Punkte miteinander verbunden sind und der minimale Länge besitzt. Davon ausgehend wird eine Tour konstruiert, indem zunächst alle Baumkanten verdoppelt werden und danach eine Eulertour in dem entstandenen eulerschen Graphen gesucht wird. Diese wird zuletzt durch direkte Kanten abgekürzt, falls Knoten doppelt besucht werden. Im Falle eines metrischen TSP kann man zeigen, dass die so konstruierte Tour höchstens doppelt so lang ist wie eine kürzeste Tour.

Eine noch bessere Approximationsgüte für metrische TSP wird durch die Christofides-Heuristik erreicht. Mit ihr kann eine Rundreise berechnet werden, die höchstens eineinhalb mal so lang wie eine optimale ist. Hierbei wird statt der Verdopplung der Kanten in der MST-Heuristik eine kleinste perfekte Paarung auf den Knoten ungeraden Grades im minimal aufspannenden Baum berechnet, um einen eulerschen Graphen zu erzeugen. Dieser Algorithmus ist jedoch aufwändiger.

Eine andere Klasse von Heuristiken unterteilt die Knotenmenge in einzelne Partitionen (z. B. nach geographischen Kriterien), die jeweils teiloptimiert werden. Anschließend werden die Teillösungen zu einer Gesamtlösung kombiniert. Diese ist in der Regel nur lokal optimal und kann gegenüber dem globalen Optimum beliebig schlecht sein.

Verbesserungsverfahren

Verbessernde Optimierungsverfahren, auch Post-Optimization-Verfahren (Nach-Optimierung) versuchen, eine bestehende Tour durch kleine Modifikationen zu verkürzen. Führt keine der betrachteten Änderungen mehr zu einer Verbesserung, so ist ein lokales Optimum gefunden (aber nicht notwendigerweise ein globales). Die k-Opt-Heuristiken verfolgen diesen Ansatz, indem sie systematisch Gruppen von $k$ Kanten aus der Tour entfernen und durch $k$ andere Kanten ersetzen, so dass wieder eine Tour entsteht. Problematisch bei solchen Verfahren wird jedoch schnell die Tatsache, dass bei einer vollständigen Durchführung der Aufwand im Vergleich zur Aufzählung aller möglichen Touren nicht gesenkt würde. In praktischen verwendeten Implementierungen ist $k$ daher üblicherweise höchstens 5. Dabei werden oft alle Austauschmöglichkeiten von zwei und drei Kanten durchprobiert, während Kantenaustausche von mehr als drei Kanten wegen des Rechenaufwandes nur noch sehr sparsam eingesetzt werden.

Die Güte einer k-Opt-Heuristik in der Praxis hängt stark von der Auswahl der auszutauschenden Kanten und des Parameters $k$ ab, für die es verschiedene heuristische Kriterien gibt. Eine bekannte k-Opt-basierte Heuristik ist die Lin-Kernighan-Heuristik, die 1973 von S. Lin und B.W. Kernighan entwickelt wurde und in der Implementierung von Keld Helsgaun unter anderem an der optimalen Lösung des Schweden-TSP mit 24978 Städten beteiligt war. Sie basiert darauf, erst alle Austauschmöglichkeiten von zwei Kanten durchzutesten, dann solche mit drei Kanten, usw., bis eins von mehreren möglichen Abbruchkriterien erfüllt ist.

Duale Heuristiken

Das Problem des Handlungsreisenden ist eines der wenigen kombinatorischen Optimierungsprobleme, bei dem sich auf einfache Weise brauchbare untere Schranken für die minimale Länge einer Tour (allgemein: die minimalen Kosten einer Lösung) angeben lassen. Da beispielsweise jede Tour, auch eine optimale, genau $n$ Kanten enthält, muss sie mindestens so lang sein wie die Summe der $n$ kleinsten Kantenlängen. Eine andere untere Schranke ergibt sich aus der Beobachtung, dass beim Löschen einer beliebigen Kante aus einer Tour ein aufspannender Baum entsteht, also ein Teilgraph, der alle Knoten, aber keine Kreise enthält. Die Tour ist mindestens so lang wie dieser Baum und damit per Definition auch mindestens so lang wie ein minimal aufspannender Baum (also ein aufspannender Baum mit minimaler Summe der Kantenlängen), der sich leicht bestimmen lässt. Da dies für jede Tour gilt, liefert die Länge eines minimal aufspannenden Baums eine untere Schranke für die Länge einer optimalen Tour.

Metaheuristische Verfahren

Metaheuristiken kombinieren lokale und globale Suchverfahren in einer abstrakten Strategie für die heuristische Optimierung eines Problems. Einige Metaheuristiken basieren auf lokalen Suchverfahren und versuchen, z. B. mit Hilfe von Tabu-Listen für bereits besuchte Lösungen das Steckenbleiben in lokalen Minima zu vermeiden.

Andere Verfahren wurden durch die Natur inspiriert. Das Verfahren der simulierten Abkühlung (engl. simulated Annealing) ahmt den Prozess der Bildung von Kristallstrukturen nach. Dabei wird eine vorhandene Rundreise stochastisch approximiert (z. B. durch Kantenaustausch), wobei abhängig von der Optimierungsstufe (Temperatur des Kristalls) auch Verschlechterungen (anfangs auch stärkere, später nur leichte) akzeptiert werden, um nicht in lokalen Minima steckenzubleiben. Varianten dieses Verfahrens sind der Sintflutalgorithmus und der Bergsteigeralgorithmus.

Eine ganze Klasse weiterer naturinspirierter Verfahren verwendet Schwarmintelligenzen. Bei so genannten Ameisenalgorithmen (engl. Ant Colony Optimization), wird hierzu das natürliche Verhalten von Ameisen auf der Wegsuche modelliert, während bei der Partikelschwarmoptimierung (engl. Particle Swarm Optimization) das Verhalten von Vogel- oder Fischschwärmen als Vorbild genommen wird. Einige der derzeit effizientesten Verfahren entspringen den Familien evolutionärer und genetischer Algorithmen. Ob und in welchem Ausmaß die Anlehnung an natürliche Selektionsprozesse oder das Verhalten von Schwärmen für das schnelle Finden guter Lösungen von Vorteil ist, ist umstritten.

Praktische Grenzen der Berechenbarkeit

Die größte Instanz eines Rundreiseproblems, die bisher nachweisbar optimal gelöst wurde, umfasst 24.978 schwedische Städte. Dieser Rekord wurde im Mai 2004 erreicht. Die Instanz wurde gemeinsam von mehreren universitären Arbeitsgruppen mit Hilfe einer Kombination aus verschiedenen Heuristiken (u. a. Lin-Kernighan-Heuristik) und dem Branch-and-Cut-basierten Programm Concorde gelöst. Bis dahin bestand die größte optimal gelöste Instanz aus 15.112 deutschen Städten (im Jahre 2001). Mit Hilfe spezieller Dekompositionstechniken und dem Einsatz mehrerer paralleler Computer haben William Cook u. a. Lösungen für ein TSP auf über 526 Millionen Sternen gefunden, die nachweislich höchstens 0,798 % vom Optimum entfernt sind.

Aus der Tatsache, dass ein TSP einer bestimmten Größe optimal gelöst werden konnte, folgt jedoch nicht, dass jede Instanz dieser Größe optimal gelöst werden kann, da – wie bei den meisten kombinatorischen Optimierungsproblemen – die Schwierigkeit der Lösung stark von den Eingabeparametern (in diesem Fall den Kantengewichten) abhängt. Bei TSPs, die aus praktischen Anwendungen entstehen, müssen oft noch weitere Nebenbedingungen, wie beispielsweise Zeitfenster, berücksichtigt werden. Daher sind in der Regel die größten optimal lösbaren Probleminstanzen solcher Varianten deutlich kleiner als beim klassischen Problem des Handlungsreisenden, so dass in der Praxis oft auf heuristische Ansätze zur Lösung zurückgegriffen wird. Kombinationen von heuristischen Verfahren mit LP-basierten Verfahren wie Branch-and-Cut werden vor allem im Forschungsumfeld eingesetzt, um mit Hilfe unterer Schranken für die Tourlänge die Qualität von Lösungen und Lösungsverfahren beurteilen zu können.

Nichtapproximierbarkeit des TSP

Neben der NP-Vollständigkeit des Problems des Handlungsreisenden, die nach momentanem Kenntnisstand einen effizienten Lösungsalgorithmus verhindert, lässt sich eine weitere Eigenschaft zeigen, die die Suche nach guten Lösungen deutlich erschwert.

Unter der allgemein vermuteten, aber bisher unbewiesenen Annahme, dass die beiden Komplexitätsklassen P und NP nicht identisch sind, kann man beweisen, dass das Problem des Handlungsreisenden nicht in polynomialer Laufzeit beliebig gut approximierbar ist. Man findet also nicht zu jedem beliebig kleinen $\epsilon >0$ einen polynomialen Algorithmus ALG, der für jedes TSP-Problem G eine Tour berechnet, deren Lange höchstens um den Faktor $1+\epsilon$ vom Optimalwert abweicht:

{\mbox{OPT(G)}}\leq {\mbox{ALG(G)}}\leq (1+\epsilon ){\mbox{OPT(G)}}

OPT(G) bezeichnet dabei die Länge einer optimalen Tour, ALG(G) die der vom Algorithmus berechneten.

Die Beweisidee beruht darauf, dass aus dieser „ $\epsilon$ -Approximierbarkeit“ die Existenz eines Algorithmus folgen würde, der in polynomialer Laufzeit entscheiden kann, ob ein beliebiger Graph hamiltonsch ist, also einen Kreis durch alle Knoten enthält, oder nicht. Dies steht jedoch im Widerspruch zu der Tatsache, dass dieses Problem NP-schwer ist.

Weiter oben wurden allerdings bereits zwei Heuristiken vorgestellt, die für metrische TSP und bestimmte $\epsilon$ eine Gütegarantie von $1+\epsilon$ geben, nämlich die Minimum-Spanning-Tree-Heuristik mit $\epsilon =1$ und die Christofides-Heuristik mit $\epsilon =$ 1/2. Bisher ist kein Algorithmus mit einer besseren Gütegarantie als 1/2 bekannt, genauso wenig wie ein $\epsilon$ -approximativer Algorithmus für allgemeine, nicht-metrische TSP.

Varianten und Anwendungen

Schon die in den vorhergehenden Abschnitten beschriebene klassische Variante des Problems besitzt viele Anwendungen, beispielsweise in der Genom-Sequenzierung, beim Layout Integrierter Schaltkreise oder bei der Steuerung eines Bohrers in der Herstellung von Leiterplatten. Darüber hinaus hat sich aus der Praxis heraus eine nahezu unerschöpfliche Auswahl an beliebig kombinierbaren Varianten entwickelt, die zusammen die Familie der TSP bilden und alle NP-schwer sind. Die meisten davon unterscheiden sich von der klassischen Variante durch zusätzliche Nebenbedingungen oder durch die grundlegende Veränderung der Zielfunktion.

Multiple TSP

Beim multiple TSP (mTSP) werden die Städte auf mehrere Handlungsreisende aufgeteilt, wobei alle ihre Rundreise in der selben Stadt starten und ihre Rundreise dort auch wieder beenden. Ziel ist es, dass jede Stadt von jeweils einem Handlungsreisenden besucht wird, so dass die zurückgelegte Gesamtstrecke minimal ist. In der Variante mTSP with nonlazy Salesmen werden nur Rundreisen mit mindestens zwei Städten zugelassen. Die klassische Version ergibt sich als Spezialfall mit nur einem Handlungsreisenden.

TSP mit Zeitfenstern

Eine häufig auftretende Erweiterung des TSP bzw. des mTSP sind Zeitfenster. Beispielsweise vereinbart ein technischer Kundendienst zur Reparatur von Haushaltsgeräten mit seinen Kunden in der Regel einen Zeitraum, in dem der Besuch des Technikers stattfinden soll. Dieser muss bei der anschließenden Planung der Touren durch den Reparaturbetrieb berücksichtigt werden.

Vehicle Routing Problem

Diese Verallgemeinerung entstand direkt aus der praktischen Notwendigkeit der Tourenplanung, bei der Waren aus einem zentralen Depot an Kunden ausgeliefert werden sollen. Die Rundreisen entsprechen den Touren von Transportern mit beschränkter Transportkapazität, die von dem gemeinsamen Depot aus starten und wieder dorthin zurückkehren. Ziel des Vehicle Routing Problems (VRP) ist es, alle Kunden möglichst kostengünstig zu beliefern. Dabei kann ein Kunde zwar mehrfach, aber jeweils nur von einem Transporter beliefert werden.

In dem Spezialfall, dass die Kapazitäten der Transporter größer sind als die Summe aller Bestellmengen sind, entspricht das VRP dem mTSP und ist daher ebenfalls NP-schwer. Vom Vehicle Routing Problem (VRP) abgeleitete Varianten sind:

Capacitated VRP (CVRP): Die Kapazität der Transporter ist einheitlich.
Multiple Depot VRP (MDVRP): Die Transporter können von mehreren verschiedenen Depots starten.
Periodisches VRP (PVRP): Der Bedarf der Kunden wächst in zeitlichen Abständen nach. Betrachtet wird eine bestimmte Zeitdauer.
Split Delivery VRP (SDVRP): Ein Kunde kann von verschiedenen Transportern beliefert werden.
VRP with Backhauls (VRPB): Lieferanten und deren Abgabemengen werden berücksichtigt.

Prize Collecting TSP

Beim Prize Collecting TSP (PCTSP) werden dem Handlungsreisenden in jeder Stadt bestimmte Preisgelder bezahlt. Um von einer Stadt zur nächsten zu reisen, muss er jedoch wiederum Kosten aufbringen. Er soll nun eine vorgegebene Anzahl von Städten und eine Rundreise zwischen diesen Städten so auszuwählen, dass der Gewinn maximal wird. Da das Problem als Spezialfall die klassische Variante enthält (alle Städte müssen besucht werden und alle Preisgelder sind 0), ist das PCTSP ebenfalls NP-schwer. Eine von ihm abgeleitete Spezialform ist das Traveling Salesman Selection Problem (TSSP), bei dem zu vorgegebenem $k$ eine kürzeste Tour zwischen beliebigen $k$ Städten gesucht ist, wobei auf Preisgelder verzichtet wird und metrische Distanzen vorausgesetzt werden.

Bottleneck TSP

Beim Bottleneck TSP (BTSP) soll nicht die Summe der Kantenlängen, sondern die Länge der längsten verwendeten Kante minimiert werden. Dies bewirkt eine weniger starke Streuung der einzelnen Distanzen, um möglichen Engpässen, sogenannten Flaschenhälsen, entgegenzuwirken. Eine verwandte Variante ist das maximum scatter TSP, bei dem die kleinste verwendete Länge maximiert wird.

Online TSP

Beim Online TSP sind nicht alle Städte von vornherein gegeben, sondern werden erst nach und nach bekannt, während der Handlungsreisende schon unterwegs ist. Dieser muss dann seine Tour auf Basis der jeweils vorhandenen Daten so planen bzw. abändern, dass neue Städte „möglichst gut“ in seine bisher geplante Tour hineinpassen (was auch immer das in der jeweiligen Anwendung genau bedeutet). Diese Variante tritt beispielsweise bei Pannendiensten wie dem ADAC auf, wo die Positionen liegengebliebener Autos erst nach und nach bekannt werden und die Zentrale versuchen muss, neue Fälle möglichst günstig in die bestehenden Touren der Pannenhelfer einzubauen. Da mehrere von diesen unterwegs sind und die Zentrale bei der Meldung einer Panne auch eine ungefähre Zeitangabe macht, wann ein Pannenhelfer eintreffen wird, handelt es sich hierbei um ein Multiple Online TSP mit Zeitfenstern.

Literatur

David Applegate, Robert Bixby, Vašek Chvátal, William Cook: On the Solution of Traveling Salesman Problems. Documenta Mathematica, Extraband III zum Internationalen Mathematikerkongress 1998, Seiten 645-656.
Keld Helsgaun, An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, European Journal of Operational Research Bd. 126, Nr.1, 2000, S. 106–130. – (Preprint-Version, pdf)
Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985, ISBN 0-471-90413-9
W. Domschke: Logistik: Rundreisen und Touren. 4. Aufl., Oldenbourg-Verlag, München - Wien 1997.
T. Grünert und S. Irnich: Optimierung im Transport, Band II: Wege und Touren. Shaker Verlag, Aachen 2005.

Weblinks

The Traveling Salesman Problem Home Ausführliche Informationen zum Traveling Salesman Problem (engl.)
TSPLIB Sammlung von Beispiel-Instanzen des TSP und verschiedener Varianten
Spektrum der Wissenschaft: Die optimierte Odyssee Artikel von Martin Grötschel und Manfred Padberg
The VRP Web Ausführliche Informationen zum Vehicle Routing Problem (engl.)