Quelltext der Seite Problem des Handlungsreisenden

[[Datei:TSP Deutschland 3.png|mini|Optimaler Reiseweg eines Handlungsreisenden durch die 15 [[Liste der Großstädte in Deutschland|größten Städte Deutschlands]]. Die angegebene Route ist die kürzeste von {{formatnum:43589145600}} möglichen.]]

Das '''Problem des Handlungsreisenden''' (auch '''Problem des Handelsreisenden''', '''Botenproblem''', '''Rundreiseproblem''', [[Englische Sprache|englisch]] ''{{lang|en-US|Traveling Salesman Problem}}''<!-- im British English auch „travelling“, zur Bewahrung der Konsistenz bitte nicht ändern.--> oder ''{{lang|en-US|Traveling Salesperson Problem}}'' (TSP)) ist ein [[Kombinatorische Optimierung|kombinatorisches Optimierungsproblem]] des ''[[Operations Research]]'' und der [[Theoretische Informatik|theoretischen Informatik]]. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des [[Handlungsreisender|Handlungsreisenden]] möglichst kurz und die erste Station gleich der letzten Station ist.

Seit seiner ersten Erwähnung als mathematisches Problem im Jahre 1930 haben sich viele Forscher damit befasst und neue [[Optimierung (Mathematik)|Optimierungsverfahren]] daran entwickelt und erprobt, die momentan auch für andere [[Optimierungsproblem]]e eingesetzt werden. Heute steht eine Vielzahl von [[Heuristik|heuristischen]] und [[Ganzzahlige lineare Optimierung|exakten]] Methoden zur Verfügung, mit denen auch schwierige Fälle mit mehreren tausend Städten optimal gelöst wurden.

Das Problem des Handlungsreisenden tritt schon in seiner Reinform in vielen praktischen Anwendungen auf, beispielsweise in der [[Tourenplanung]], in der [[Logistik]] oder im Design von [[Integrierter Schaltkreis|Mikrochips]]. Noch häufiger erscheint es allerdings als ein Unterproblem, etwa bei der Verteilung von Waren, bei der Planung von Touren eines [[Kundendienst|Kunden-]] oder [[Pannendienst]]es oder bei der [[DNA-Sequenzierung|Genom-Sequenzierung]]. Dabei sind die Begriffe „Stadt“ und „Entfernung“ nicht wörtlich zu nehmen, vielmehr repräsentieren die Städte beispielsweise zu besuchende Kunden, Bohrlöcher oder DNA-Teilstränge, während Entfernung für Reisezeit, Kosten oder den Grad der Übereinstimmung zweier DNA-Stränge steht. In vielen praktischen Anwendungen müssen zudem Zusatzbedingungen wie Zeitfenster oder eingeschränkte Ressourcen beachtet werden, was die Lösung des Problems erheblich erschwert.

Das Problem des Handlungsreisenden ist ein [[NP-Schwere|NP-schweres]] Problem. Unter der bislang [[P-NP-Problem|unbewiesenen Annahme]], dass die [[Komplexitätsklasse]]n '''[[P (Komplexitätsklasse)|P]]''' und '''[[NP (Komplexitätsklasse)|NP]]''' verschieden sind, gilt demnach, dass kein [[Algorithmus]] existiert, der eine kürzeste Rundreise in [[Polynomialzeit|polynomieller]] [[Zeitkomplexität|Worst-case-Laufzeit]] bestimmt.

== Geschichte ==
Wann das Problem des Handlungsreisenden erstmals 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<!--sic!--> hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß<!--sic!--> zu sein – von einem alten Commis-Voyageur''), in dem das Problem erwähnt, aber nicht mathematisch behandelt wird. Darin werden Beispieltouren für einige Regionen [[Deutschland]]s und der [[Schweiz]] vorgeschlagen.<ref>''Der Handlungsreisende – wie er sein soll und was er zu thun<!--sic!--> hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß<!--sic!--> zu sein – von einem alten Commis-Voyageur.'' Verlag von B. Fr. Voigt, Ilmenau 1832, S. 188–203, [https://haab-digital.klassik-stiftung.de/viewer/image/4075599590/202/ Digitalisat]</ref>

[[Datei:William Rowan Hamilton portrait oval combined.png|mini|William Rowan Hamilton (1805–1865)]]

Als Vorläufer des Problems kann das ''[[Icosian Game]]'' von [[William Rowan Hamilton]] aus dem 19. Jahrhundert angesehen werden, bei dem es galt, in einem [[Graph (Graphentheorie)|Graphen]] Touren zwischen 20 Knoten zu finden. Die erste explizite Erwähnung als mathematisches Optimierungsproblem scheint auf [[Karl Menger]] zurückführbar zu sein, der dieses 1930 in einem mathematischen Kolloquium in Wien formulierte:

{{Zitat|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.}}

Bald darauf wurde die heute übliche Bezeichnung ''Travelling Salesman Problem'' durch [[Hassler Whitney]] von 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 ''[[Optimum|optimalen]]'' Lösung sehr schwierig ist.
Daher ist das Studium dieses Problems seit der zweiten Hälfte des 20. Jahrhunderts weniger durch direkte Anwendungen motiviert – es dient als eine Art Spielwiese zur Entwicklung von Optimierungsverfahren.

Viele heutige Standardmethoden der [[Ganzzahlige lineare Optimierung|ganzzahligen linearen Optimierung]], wie [[Schnittebenenverfahren]], [[Branch-and-Cut]] und verschiedene [[Heuristik|heuristische]] Ansätze, wurden am Beispiel des TSP entwickelt und getestet.

Seit den 1950er Jahren gewann das Problem des Handlungsreisenden sowohl in [[Europa]] als auch in den [[USA]] an Popularität. Herausragende Beiträge leisteten [[George Dantzig]], [[Delbert Ray Fulkerson]] und [[Selmer M. Johnson]], die 1954 am Institut der [[RAND Corporation]] in [[Santa Monica]] die erste Formulierung des Problems als ganzzahliges lineares Programm als auch ein Schnittebenenverfahren zu dessen Lösung entwickelten. Sie berechneten eine Tour für ein konkretes Rundreiseproblem (eine sogenannte ''[[Probleminstanz]]'') mit 49 Städten und bewiesen, dass es keine kürzere Tour gibt. In den 1960er und 1970er Jahren befassten sich viele interdisziplinäre Forschergruppen mit Anwendungen des Problems unter anderem in der [[Informatik]], den [[Wirtschaftswissenschaften]], der [[Chemie]] und der [[Biologie]].

[[Richard M. Karp]] bewies im Jahre 1972 die [[NP-Vollständigkeit]] des [[Hamiltonkreisproblem]]s, aus der sich leicht die [[NP-Äquivalenz]] des TSP ableiten lässt. Damit lieferte er eine theoretische Begründung für die schwere Lösbarkeit dieses Problems in der Praxis.

Größere Fortschritte wurden Ende der 1970er und 1980er Jahre erzielt, als [[Martin Grötschel]], [[Manfred Padberg]], [[Giovanni Rinaldi]] und andere mit neuen Schnittebenen und einem Branch-and-Cut-Verfahren einige Probleminstanzen mit bis zu 2392 Städten optimal lösten.

Ein 1976 unabhängig von [[Nicos Christofides]] und [[Anatoli Iwanowitsch Serdjukow|Anatoli I. Serdjukow]] beschriebener Algorithmus ergab eine Rundreise, die maximal um die Hälfte länger ist als die optimale Tour.<ref>{{Literatur |Autor=René van Bevern, Viktoriia A. Slugina |Titel=A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem |Hrsg= |Sammelwerk=Historia Mathematica |Band= |Nummer= |Auflage= |Verlag= |Ort= |Datum=2020-05 |ISBN= |arXiv=2004.02437 |DOI=10.1016/j.hm.2020.04.003 |Seiten= |Online=https://linkinghub.elsevier.com/retrieve/pii/S0315086020300240 |Abruf=}}</ref>

In den 1990er Jahren begannen [[David Applegate]], [[Robert Bixby]], [[Vašek Chvátal]] und [[William Cook (Mathematiker)|William Cook]] mit der Entwicklung des Programms ''Concorde'', das an vielen Lösungsrekorden beteiligt war. Gerhard Reinelt stellte 1991 die TSPLIB bereit, eine Sammlung verschieden schwerer standardisierter Testinstanzen, womit viele Forschergruppen ihre Resultate vergleichen konnten. Im Jahre 2006 berechnete Cook mit anderen eine beweisbar kürzeste Tour durch 85.900 Städte eines Layoutproblems für [[Integrierter Schaltkreis|integrierte Schaltkreise]], was die bislang größte optimal gelöste TSPLIB-Instanz ist.<ref name=":0">David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook: ''The Traveling Salesman Problem. A Computational Study''. Princeton University Press, Februar 2007. S. 522–524. ISBN 0-691-12993-2</ref><ref name=":3">{{Literatur |Autor=David L. Applegate, Robert E. Bixby, Vašek Chvátal, William Cook, Daniel G. Espinoza, Marcos Goycoolea, Keld Helsgaun |Titel=Certification of an optimal TSP tour through 85,900 cities |Sammelwerk=Operations Research Letters |Band=37 |Nummer=1 |Datum=2009-01 |ISSN=0167-6377 |DOI=10.1016/j.orl.2008.09.006 |Seiten=11–15 |Online=https://www.math.uwaterloo.ca/~bico/papers/proof.pdf |Abruf=2024-01-18}}</ref> Für andere Instanzen mit Millionen Städten bestimmten sie mit zusätzlichen Dekompositionstechniken Touren, deren Länge beweisbar weniger als 1 % vom Optimum entfernt liegt.<ref name=":1">{{Internetquelle |autor=William Cook |url=https://www.math.uwaterloo.ca/tsp/star/star10m.html |titel=TSP: Tours visiting 10,000,000 Stars |werk=Mathematics Department University Waterloo |sprache=en |abruf=2024-01-16}}</ref>

[[András Sebö]] von der Universität Grenoble und [[Jens Vygen]] von der Universität Bonn stellten 2014 mit einem Algorithmus, welcher eine polynomielle Laufzeit besitzt, einen neuen Rekord im Bereich der Heuristiken mit [[Gütegarantie]] auf: Ihr neuartiger, ''Schöne-Ohren-Zerlegung'' genannter Algorithmus bestimmt Lösungen des Graph-TSP, die höchstens 1,4-mal so lang sind wie die optimale Rundreisestrecke, was eine neue Bestmarke darstellt.<ref>András Sebö, Jens Vygen: ''Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs''. Combinatorica 34 (5) (2014), 597-629, ([[doi:10.1007/s00493-011-2960-3]])</ref>

== Mathematische Beschreibung ==
=== Modellierung als Graph ===
[[Datei:Weighted K4.svg|mini|klasse=skin-invert-image|Symmetrisches TSP auf vier Städten]]

Damit mathematische Verfahren zur Lösung verwendet werden können, muss eine reale Situation zunächst durch ein einfaches [[Mathematisches Modell|Modell]] abgebildet werden. Das Problem des Handlungsreisenden lässt sich mit Hilfe eines [[Graph (Graphentheorie)|Graphen]] modellieren, das heißt: durch [[Knoten (Graphentheorie)|Knoten]] und [[Kante (Graphentheorie)|Kanten]]. Dabei repräsentieren die Knoten (im Bild: A bis D) die Städte, während jede Kante <math>(i,j)</math> zwischen zwei Knoten <math>i</math> und <math>j</math> eine Verbindung zwischen diesen Städten beschreibt. Zu jeder Kante <math>(i,j)</math> gibt es eine Länge <math>c_{ij} \geq 0</math> (im Bild: 20, 42, …), die sich 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 [[Zyklus (Graphentheorie)|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ändiger 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.

==== Asymmetrisches und symmetrisches TSP ====
Beim allgemeinen ''asymmetrischen TSP'' können die Kanten in Hin- und Rückrichtung unterschiedliche Längen haben, so dass dieses Problem mit Hilfe eines [[Gerichteter Graph|gerichteten Graphen]] modelliert werden muss. Es 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 <math>(i,j)</math> die Kantenlängen in beide Richtungen identisch, d.&nbsp;h., es gilt <math>c_{ij} = c_{ji}</math>. 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 [[Ungerichteter Graph|ungerichteten Graphen]] modelliert (wie im Bild). Ein Problem des Handlungsreisenden zwischen realen Städten kann asymmetrisch oder symmetrisch sein, je nachdem, ob beispielsweise durch Baustellen oder [[Einbahnstraße]]n der Weg in eine Richtung länger dauert als in die andere oder nicht. Ebenso könnte die Reise zu Wasser oder in der Luft unterschiedlichen Strömungen ausgesetzt sein.

==== 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 <math>i</math> nach <math>j</math> nie länger ist als der Weg von <math>i</math> nach <math>j</math> über einen dritten Knoten <math>k</math>:

: <math>c_{ij} \le c_{ik} + c_{kj}</math>

Solche Kantenlängen definieren eine [[Metrischer Raum#Pseudometrik|Pseudometrik]] auf der Knotenmenge, also ein Entfernungsmaß, das die intuitiv von einem Abstand erwarteten Bedingungen erfüllt. Mehrere in der Praxis häufig auftretende [[Distanzfunktion]]en sind Pseudometriken, erfüllen also die Dreiecksungleichung:

* die [[Euklidischer Abstand|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 [[Metrischer Raum|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 [[Leiterplatte]]n, 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.

Ein nicht-metrisches TSP kann zum Beispiel vorliegen, wenn die Dauer einer Reise minimiert werden soll und auf verschiedenen Strecken verschiedene Verkehrsmittel möglich sind. Dabei kann ein Umweg mit dem Flugzeug schneller sein als die direkte Verbindung mit dem Auto.

Falls es im praktischen Planungsproblem zulässig ist, Orte mehrfach zu besuchen, lässt sich das symmetrische TSP auf das metrische TSP reduzieren. Dazu wird das Rundreiseproblem auf dem sogenannten ''Distanzgraphen'' betrachtet. Dieser hat dieselbe Knotenmenge wie der ursprüngliche Graph und ist ebenfalls [[Vollständiger Graph|vollständig]]. Die Kantenlängen <math>c_{ij}</math> zwischen zwei Knoten <math>i</math> und <math>j</math> im Distanzgraphen entsprechen der Länge eines kürzesten <math>i</math>-<math>j</math>-Weges zwischen diesen Knoten im ursprünglichen Graphen. Die so definierten Werte <math>c_{ij}</math> erfüllen immer die Dreiecksungleichung, und jede Tour im Distanzgraphen entspricht einer Tour mit möglichen Knotenwiederholungen im ursprünglichen Graphen.
<!-- Mit Bild veranschaulichen? -->

Sollte es ''nicht'' zulässig sein, Orte mehrfach zu besuchen, lässt sich ein beliebiges TSP ebenfalls auf ein metrisches TSP reduzieren, indem man jede Kantenlänge um dieselbe nichtnegative Konstante vergrößert: Es kann ja immer eine Konstante <math>q\ge0</math> gefunden werden, die groß genug ist, um <math>(c_{ij}+q) \le (c_{ik}+q) + (c_{kj}+q)</math> für alle Knotentripel zu erfüllen. Bei Heuristiken, die eine maximale Abweichung vom Optimum gewährleisten, vergrößert dieses Vorgehen natürlich den Abweichungsfaktor der ursprünglichen Aufgabe.

=== Formulierung als ganzzahliges lineares Programm ===
Ein Ansatz zur Lösung des Problems ist die Formulierung als [[Ganzzahlige lineare Optimierung|ganzzahliges lineares Optimierungsproblem]], in dem die Entscheidungen durch binäre [[Entscheidungsvariable]]n und die Bedingungen durch lineare [[Nebenbedingung]]en beschrieben werden. Es gibt verschiedene Möglichkeiten, das TSP als [[Optimierungsmodell]] zu beschreiben. Beispielhaft soll hier eine Modellierung für das symmetrische TSP mit Knotenmenge <math>V</math> vorgestellt werden, welche auch als [[George Dantzig|Dantzig]]-[[Delbert Ray Fulkerson|Fulkerson]]-Formulierung bezeichnet wird.<ref>{{Literatur |Autor=G. Dantzig, R. Fulkerson, S. Johnson |Titel=Solution of a Large-Scale Traveling-Salesman Problem |Sammelwerk=Journal of the Operations Research Society of America |Band=2 |Nummer=4 |Datum=1954-11 |ISSN=0096-3984 |DOI=10.1287/opre.2.4.393 |Seiten=393–410 |Online=https://apps.dtic.mil/sti/pdfs/AD0604317.pdf |Abruf=2024-01-15}}</ref> Eine andere bekannte Formulierung des TSP ist die Miller-Tucker-Zemlin-Formulierung.<ref>{{Literatur |Autor=C. E. Miller, A. W. Tucker, R. A. Zemlin |Titel=Integer Programming Formulation of Traveling Salesman Problems |Sammelwerk=Journal of the ACM |Band=7 |Nummer=4 |Datum=1960-10 |ISSN=0004-5411 |DOI=10.1145/321043.321046 |Seiten=326–329 |Online=https://dl.acm.org/doi/pdf/10.1145/321043.321046 |Abruf=2024-01-15}}</ref> Für jede [[Kante (Graphentheorie)|Kante]] <math>\{i,j\}</math> wird eine binäre Variable <math>x_{\{i,j\}} \in \{0,1\}</math> eingeführt, die für eine gegebene Tour angibt, ob die Kante <math>\{i,j\}</math> in dieser Tour enthalten ist (<math>x_{\{i,j\}} = 1</math>) oder nicht (<math>x_{\{i,j\}} = 0</math>). 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, die im Folgenden vorgestellt werden sollen.

[[Datei:TSP degree constraints.png|mini|klasse=skin-invert-image|Gradbedingung: In jeden Knoten i muss genau eine Kante der Tour hinein- bzw. hinausgehen.]]

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

: <math>\sum_{j \in V \setminus \{i\}} x_{\{i,j\}} = 2 \qquad (1)</math>

für alle <math>i \in V</math>. In der [[Summe]] ist jeder [[Summand]] <math>x_{\{i,j\}}</math> 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 <math>i</math> als Endknoten haben. Sie muss den Wert 2 annehmen, da jeweils eine Kante hinein- und hinausführen muss. Im nebenstehenden Bild ist ein Knoten <math>i</math> mit ein- und ausgehenden Kanten dargestellt, wobei die Tourkanten fett gekennzeichnet sind. An den Kanten stehen die Werte <math>x_{\{i,j\}}</math>, die zu den oben genannten Summen beitragen.

[[Datei:TSP short cycles.png|mini|klasse=skin-invert-image|Kurzzyklen: Diese Variablenbelegung erfüllt alle Gradbedingungen, definiert aber keine Tour.]]

Die obigen ''Gradbedingungen'' werden 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. Diese von Dantzig, Fulkerson und Johnson 1954 als ''loop conditions'' eingeführten Nebenbedingungen besagen, dass jede Knotenmenge <math>S \subset V</math>, die weder leer ist noch alle Knoten enthält, durch mindestens zwei Kanten der Tour mit den restlichen Knoten verbunden sein muss:

: <math>\sum_{i \in S, \; j \notin S} x_{\{i,j\}} \geq 2 \qquad (2)</math>

für alle Knotenmengen <math>S</math> mit <math>1 \leq |S| \leq |V|-1</math>. Die Summe zählt alle Kanten der Tour zwischen einem Knoten <math>i \in S</math> und einem anderen Knoten <math>j \notin S</math>. Zur Vermeidung redundanter Ungleichungen kann man sich auch auf Knotenmengen <math>S</math> mit mindestens zwei und höchstens <math>|V|-2</math> Knoten beschränken. Im nebenstehenden Bild sind wieder die Kanten <math>\{i,j\}</math> mit <math>x_{\{i,j\}} = 1</math> fett gezeichnet, während die übrigen Kanten den Wert <math>x_{\{i,j\}} = 0</math> haben. Das Hinzufügen der Bedingung (2) für die Knotenmenge <math>S</math>, 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. Die Anzahl der Subtour-Eliminationsbedingungen nach Dantzig, Fulkerson und Johnson beträgt <math>2^{n}-2(n-1)</math>. Eine 1960 von Miller, Tucker und Zemlin veröffentlichte alternative Darstellung der Nebenbedingungen zur Vermeidung von Subtouren kommt durch Einführung von <math>n</math> neuen Variablen, die die Reihenfolge der besuchten Orte angeben, mit nur <math>n^2-n+1</math> Nebenbedingungen aus. Allerdings bleibt das TSP wegen der Binarität der <math>x_{\{i,j\}}</math> auch mit der Formulierung nach Miller, Tucker und Zemlin weiterhin [[NP-Schwere|NP-schwer]].

Da jeder Vektor <math>x=(x_{\{i,j\}})_{i,j \in V, i \neq j}</math> mit Einträgen aus 0 und 1, der alle diese Ungleichungen erfüllt, eine gültige Rundreise definiert, ergibt sich als reformuliertes Problem des Handlungsreisenden: Finde

: <math>\min \; \left\{ \sum_{i \in V} \sum_{j \in V \setminus \{i\}} c_{\{i,j\}} x_{\{i,j\}} \;|\; x \text{ erfüllt (1) und (2) }, \; x_{\{i,j\}} \in \{0,1\} \right\}. \qquad (3)</math>

Da die Variablen <math>x_{\{i,j\}}</math> nur die Werte 0 oder 1 annehmen, zählt die Summe genau die Längen <math>c_{\{i,j\}}</math> der Kanten <math>\{i,j\}</math> zusammen, die in der Tour enthalten sind.

Die Zahl der Ungleichungen vom Typ (2) wächst exponentiell mit der Anzahl der Städte, da fast jede der <math>2^{|V|}</math> Teilmengen von Knoten eine Ungleichung definiert. Dieses Problem kann aber mit Hilfe von [[Schnittebenenverfahren]] umgangen werden, bei denen diese Ungleichungen erst dann hinzugefügt werden, wenn sie tatsächlich gebraucht werden. Geometrisch lässt sich jede lineare Gleichung als [[Hyperebene]] im Raum der Variablen interpretieren. Die Menge der zulässigen Lösungen bildet in diesem Raum ein [[Polytop (Geometrie)|Polytop]], also ein mehrdimensionales Vieleck, dessen genaue Gestalt von den Kosten <math>c_{\{i,j\}}</math> abhängt und meist unbekannt ist. Man kann aber zeigen, dass die meisten der Bedingungen (1) und (2) [[Facette (Geometrie)|Facetten]] des TSP-Polytops definieren, also Seitenflächen des Polytops mit höchstmöglicher Dimension. Damit gehören sie zu den stärksten linearen Ungleichungen, die es zur Beschreibung einer Tour geben kann. Es gibt noch viele weitere Facetten, deren zugehörige Ungleichungen allerdings nur in wenigen Fällen bekannt sind. Obwohl (1) und (2) zusammen mit der Beschränkung auf 0/1-Vektoren das Problem vollständig modellieren, können solche zusätzlichen Ungleichungen innerhalb eines [[Branch-and-Cut]]-Verfahrens zur Formulierung hinzugefügt werden, um bestimmte [[Lineare Optimierung|LP]]-Lösungen mit nicht-ganzzahligen Koordinaten auszuschließen (siehe Abschnitt [[#Exakte Lösungsverfahren|Exakte Lösungsverfahren]]).

== Algorithmische Komplexität ==
Da dem Handlungsreisenden in jedem Schritt die Städte zur Auswahl stehen, die er noch nicht besucht hat, gibt es [[Fakultät (Mathematik)|<math>(n-1)!</math>]] mögliche Touren für ein asymmetrisches und <math>(n-1)!/2</math> Touren für ein symmetrisches TSP (mit <math>n>2</math>). Die Größe des Suchraums hängt also überexponentiell von der Anzahl der Städte ab. Das ist aber schon bei einer kleinen Zahl von Städten nicht mehr praktisch durchführbar. Bei einem symmetrischen TSP mit 15 Städten gibt es über 43 Milliarden verschiedene Rundreisen und bei 18 Städten bereits über 177 [[Billion]]en. Wie schnell die Rechenzeit mit wachsender Anzahl von Städten wächst, zeigt das folgende Beispiel: Hat man einen Rechner, der die Lösung für 30 Städte in einer Stunde berechnet, dann braucht dieser für zwei zusätzliche Städte annähernd die tausendfache Zeit; das sind mehr als 40 Tage.

Das Problem des Handlungsreisenden ist sowohl für den allgemeinen als auch für den symmetrischen oder metrischen Fall [[NP-Äquivalenz|NP-äquivalent]]. Unter der allgemein vermuteten, bisher aber unbewiesenen Annahme, dass die Komplexitätsklassen '''P''' und '''NP''' verschieden sind (siehe [[P-NP-Problem]]), folgt daraus, dass keine deterministische [[Turingmaschine]] existiert, die das Problem für jede Instanz in [[Polynomialzeit|polynomialer Laufzeit]] bezüglich der Anzahl der Städte löst.

Ferner ist bekannt, dass es unter der Annahme '''P'''<math>\neq</math>'''NP''' für das allgemeine Problem des Handlungsreisenden keinen Polynomialzeitalgorithmus geben kann, der für irgendein Polynom <math>p</math> grundsätzlich eine Lösung berechnet, deren Wert höchstens um einen Faktor <math>2^{p(n)}</math> vom Optimalwert abweicht.

Allerdings lassen sich für das metrische TSP Approximationsalgorithmen angeben, die in polynomieller Laufzeit eine Lösung liefern, die höchstens doppelt ([[MST-Heuristik|Minimum-Spanning-Tree-Ansatz]]) bzw. höchstens 1,5-mal ([[Christofides-Heuristik|Algorithmus von Christofides]]) so lang wie die optimale Lösung ist (siehe [[#Eröffnungsverfahren|unten]]). Bisher ist kein Polynomialzeitalgorithmus mit einer besseren Gütegarantie als 1,5 bekannt. Für die Beschränkung auf die Distanzen 1 und 2 ist ein Polynomialzeitalgorithmus mit Gütegarantie 8/7 bekannt.<ref>Pjotr Berman, Marek Karpinski, ''8/7-approximation algorithm for (1,2)-TSP'', Proceedings SODA '06, S.&nbsp;641–648. [[doi:10.1145/1109557.1109627]]</ref> Unter der Annahme '''P'''<math>\neq</math>'''NP''' gibt es eine (unbekannte) Konstante <math>c\geq \tfrac{1}{122}\approx 0{,}0081</math>, so dass kein Polynomialzeitalgorithmus für das metrische TSP existieren kann, der die Güte <math>1+c</math> garantiert, wie Karpinski, Lampis und Schmied 2013 gezeigt haben.<ref>Marek Karpinski, Michael Lampis, and Richard Schmied, ''New Inapproximability Bounds for TSP'', appeared in Algorithms and Computation - 24th International Symposium, ISAAC 2013, S.&nbsp;568–578, 2013,
[[doi:10.1007/978-3-642-45030-3]]</ref>
Die entsprechende bestbekannte Konstante <math>c</math> für das Graph-TSP ist <math>\tfrac{1}{534}</math>.<ref>{{Literatur |Autor=Marek Karpinski, Richard Schmied |Titel=Approximation hardness of graphic TSP on cubic graphs |Sammelwerk=RAIRO - Operations Research |Band=49 |Nummer=4 |Datum=2015-10-01 |ISSN=0399-0559 |arXiv=1304.6800 |DOI=10.1051/ro/2014062 |Seiten=651–668 |Online=http://www.numdam.org/articles/10.1051/ro/2014062/ |Abruf=2024-12-31}}</ref>
Unabhängig voneinander gaben [[Sanjeev Arora|Arora]] (1996) und Mitchell (1996) ein [[Approximationsalgorithmus|polynomielles Approximationsschema (PTAS)]] für das euklidische TSP an.<ref>{{Literatur |Autor=Sanjeev Arora |Titel=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems |Sammelwerk=Journal of the ACM |Band=45 |Nummer=5 |Datum=1998-09 |ISSN=0004-5411 |DOI=10.1145/290179.290180 |Seiten=753–782 |Online=https://dl.acm.org/doi/10.1145/290179.290180 |Abruf=2024-12-31}}</ref><ref>{{Literatur |Autor=Joseph S. B. Mitchell |Titel=Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k -MST, and Related Problems |Sammelwerk=SIAM Journal on Computing |Band=28 |Nummer=4 |Datum=1999-01 |ISSN=0097-5397 |DOI=10.1137/S0097539796309764 |Seiten=1298–1309 |Online=https://dl.acm.org/doi/pdf/10.5555/313852.314090 |Abruf=2024-12-31}}</ref>

== Lösungsverfahren ==
Die bekannten Lösungsverfahren unterteilen sich in zwei Gruppen, die miteinander kombiniert werden können. ''Exakte'' Lösungsverfahren finden – beliebig lange Laufzeit vorausgesetzt – grundsätzlich eine beweisbare Optimallösung. ''Heuristische'' Verfahren finden oft in kurzer Zeit gute Lösungen, die aber im allgemeinen Fall beliebig schlecht sein können. Für das metrische TSP gibt es [[Polynomieller Algorithmus|polynomiale]] [[Heuristik]]en, deren Lösungen grundsätzlich höchstens um den Faktor 1,5 bzw. 2 länger sind als eine kürzeste Rundreise.

=== Exakte Lösungsverfahren ===
{{Hauptartikel|Branch-and-Cut}}

[[Datei:TSP cutting plane.png|mini|klasse=skin-invert-image|TSP auf drei Knoten: Die rot gestrichelte [[Schnittebenenverfahren|Schnittebene]] <math>x_1 + x_2 + x_3 \geq 2</math> schneidet alle unzulässigen Lösungen mit höchstens einer Kante ab. Alle Punkte im roten [[Polytop (Geometrie)|Polytop]] erfüllen diese Ungleichung, unter anderem der einzige zulässige Punkt (1,1,1).]]

Mit Methoden der [[Ganzzahlige lineare Optimierung|ganzzahligen linearen Optimierung]], insbesondere [[Branch-and-Cut]], 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.
Geometrisch interpretiert betrachten diese Verfahren das Problem als [[Konvexe Menge|konvexes]] [[Polytop (Geometrie)|Polytop]], also als mehrdimensionales Vieleck im <math>m</math>-dimensionalen [[Würfel (Geometrie)#Verallgemeinerung|Einheitswürfel]] <math>[0,1]^m</math>, wobei <math>m</math> die Anzahl der Kanten des Graphen ist. Jede Ecke dieses Einheitswürfels beschreibt eine Tour, sofern der zugehörige 0/1-Vektor die oben beschriebenen linearen Ungleichungen erfüllt. Die zu diesen Ungleichungen gehörenden [[Hyperebene]]n schneiden daher Ecken des Einheitswürfels ab, die keine Tour darstellen.

Das nebenstehende Bild illustriert dies für das (sehr einfache) TSP mit drei Knoten. Entsprechend den drei möglichen Kanten zwischen diesen Knoten gibt es auch drei binäre Variablen <math>x_1,\, x_2</math> und <math>x_3</math>. Es gibt in diesem Fall nur eine mögliche Tour, nämlich diejenige, die alle drei Kanten benutzt. Diese Tour erfüllt die Ungleichung <math>x_1 + x_2 + x_3 \geq 2</math>, die besagt, dass jede Tour mindestens zwei Kanten haben muss. Außer dieser Tour, die dem Punkt (1,1,1) entspricht, erfüllen auch alle Punkte im rot eingegrenzten Bereich diese Ungleichung. Die zugehörige [[Schnittebenenverfahren|Schnittebene]], die durch die rot gestrichelten Linien aufgespannt wird, schneidet also alle Ecken ab, die unmöglichen Touren mit höchstens einer Kante entsprechen, nämlich den [[Nullvektor]] (0,0,0) und die Einheitsvektoren (1,0,0), (0,1,0) und (0,0,1). Die stärkere Ungleichung <math>x_1 + x_2 + x_3 \geq 3</math> würde vom Einheitswürfel alles außer dem einzigen zulässigen Punkt (1,1,1) abschneiden. In diesem speziellen Fall lässt sich derselbe Effekt auch schon durch die drei Ungleichungen vom Typ (1) erzielen.

Durch Lösen vieler [[Lineare Optimierung|linearer Programme]], Abschneiden nicht benötigter Teile des Einheitswürfels mit Hilfe weiterer Schnittebenen (zum Beispiel vom Typ (2) oder auch ''Kamm-'', ''Cliquenbaum-'' und ''Domino-Parity-Ungleichungen''<ref name="CookEspinozaGoycoolea2005">William Cook, Daniel Espinoza, Marcos Goycoolea: ''[http://www2.isye.gatech.edu/~wcook/papers/DP_paper.pdf Computing with Domino-Parity Inequalities for the TSP.]'' 2005. (Preprint, pdf; 261&nbsp;kB)</ref>) sowie durch Aufteilung in mehrere Teilpolytope mit Hilfe von [[Branch-and-Bound]] wird versucht, eine zulässige 0/1-Ecke mit minimalem Zielfunktionswert 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 Rundreisen 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, kann eine optimale Tour nur zwischen 100 und 102 liegen. Die sogenannte ''Optimalitätslücke'', also der maximale relative Abstand zwischen der optimalen Tourlänge und der kürzesten bekannten Tourlänge, beträgt daher (102-100)/100 = 2 %, d.&nbsp;h., der gefundene Lösungswert 102 ist höchstens 2 % vom Optimalwert entfernt. 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, können diese exakten Verfahren mit Heuristiken kombiniert werden, von denen einige im nachfolgenden Abschnitt beschrieben werden.

=== Heuristiken ===
Um schnell zu brauchbaren Lösungen zu kommen, sind meist durch [[Heuristik]]en motivierte 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 Tour konstruiert oder ob sie versucht, eine bestehende Rundreise zu verbessern, wird sie als ''Eröffnungs-'' (auch ''Konstruktions-'') oder ''Verbesserungsverfahren'' bezeichnet. Darüber hinaus gibt es ''Dualheuristiken'', die Mindestlängen für eine Tour berechnen. ''Metaheuristiken'' können mehrere dieser Einzelheuristiken unterschiedlich kombinieren. Eine Übersicht über die meisten der hier vorgestellten Heuristiken ist im Abschnitt ''[[#Übersicht|Übersicht]]'' zu finden.

==== Eröffnungsverfahren ====
[[Datei:Nearest Neighbor Heuristik.svg|mini|klasse=skin-invert-image|Die [[Nearest-Neighbor-Heuristik]] besucht in jedem Schritt den nächstgelegenen Knoten.]]

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ätstheorie|Komplexität]] von [[Landau-Notation|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- und die Farthest-Neighbor-Heuristik können beliebig schlechte Ergebnisse liefern, das heißt, es gibt keinen konstanten, instanzunabhängigen [[Approximationsfaktor]] für den Lösungswert im Vergleich zum Optimalwert.

Eine 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 so lange 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.

[[Datei:Minimum spanning tree.svg|mini|links|klasse=skin-invert-image|Ein [[Minimal spannender Baum|minimal aufspannender Baum]] verbindet alle Punkte eines Graphen bei minimaler Kantenlänge]]

Eine andere Klasse von Heuristiken unterteilt die Knotenmenge in einzelne [[Partition (Mengenlehre)|Partitionen]] (zum Beispiel 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.

Die [[Minimum-Spanning-Tree-Heuristik]] ''(MST)'' berechnet zunächst einen [[Minimal spannender Baum|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 [[Eulerscher Graph|eulerschen Graphen]] gesucht wird. Diese wird zuletzt durch direkte Kanten abgekürzt, falls Knoten doppelt besucht werden. Sofern der minimale aufspannende Baum mittels des [[Algorithmus von Kruskal|Verfahrens von Kruskal]] berechnet wird, liefert die MST-Heuristik dasselbe Ergebnis wie die Nearest-Insertion-Heuristik. Im Vergleich zu einer Optimallösung kann das Ergebnis beliebig schlecht sein. Im Falle eines metrischen TSP kann man jedoch 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 den [[Algorithmus von Christofides|Algorithmus von Christofides und Serdjukow]] 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 [[Grad (Graphentheorie)|Grades]] im minimal aufspannenden Baum berechnet, um einen eulerschen Graphen zu erzeugen. Dieser Algorithmus ist jedoch aufwändiger.
<!--

Eine weitere Eröffnungsheuristik bestimmt zu jedem Knoten die kürzeste Kante zu einem Nachbarknoten. Anschließend wird die längste unter diesen kürzesten Kanten ausgewählt. Diese ist ein Teil der kürzesten Route. Danach wird (solange nötig) erneut die längste aller kürzesten Verbindungen unter den restlichen Wegen bestimmt. Dabei muss darauf geachtet werden, dass kein geschlossener Weg entsteht, solange nicht alle Punkte besucht worden sind. Zudem darf jeder Knoten nur mit zwei Wegen verbunden sein. Dann wird wiederum ein Teilstück des Weges selektiert. Dies wird wiederholt, bis alle Punkte besucht sind. Das Verfahren versagt, falls Symmetrien auftreten. [http://www.ika.ethz.ch/td/tsp.html]
-->

==== 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-Heuristik]]en verfolgen diesen Ansatz, indem sie systematisch Gruppen von <math>k</math> Kanten aus der Tour entfernen und durch <math>k</math> andere Kanten ersetzen, so dass wieder eine Tour entsteht. Da eine vollständige Durchführung dieses Verfahrens einer Aufzählung aller möglichen Touren entsprechen würde, ist <math>k</math> in praktischen Implementierungen ü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 <math>k</math> ab, für die es verschiedene heuristische Kriterien gibt. Eine bekannte k-Opt-basierte Heuristik ist die ''[[Kernighan-Lin-Algorithmus|Lin-Kernighan-Heuristik]]'', die 1973 von S. Lin und [[Brian W. Kernighan|B. W.&nbsp;Kernighan]] entwickelt wurde und in der Implementierung von Keld Helsgaun<ref name="Helsgaun2000">Keld Helsgaun: ''[http://www.akira.ruc.dk/~keld/research/LKH/LKH-1.3/DOC/LKH_REPORT.pdf An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.] (PDF; 646&nbsp;kB)'' In: European Journal of Operational Research. Amsterdam 126.2000, Nr. 1, S. 106–130. {{ISSN|0377-2217}}</ref> unter anderem an der optimalen Lösung des TSP durch 24.978 schwedische Orte im Jahre 2004 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.

==== Metaheuristische Verfahren ====
[[Metaheuristik]]en kombinieren lokale und globale Suchverfahren in einer abstrakten Strategie für die heuristische Optimierung eines Problems. Viele dieser Verfahren basieren auf [[Lokale Suche|lokaler Suche]], d.&nbsp;h., sie berechnen eine heuristische Startlösung (beispielsweise mit der Nearest-Neighbor-Heuristik) und verbessern diese so lange durch ein lokales Suchverfahren, wie zum Beispiel [[K-Opt-Heuristik]]en, bis keine bessere Tour mehr gefunden wird. Durch verschiedene Strategien, wie beispielsweise [[Tabu-Suche]] oder [[Simulierte Abkühlung]], kann versucht werden, das Steckenbleiben in lokalen Minima weitestgehend zu verhindern. Andere Ansätze, wie [[Ameisenalgorithmus|Ameisenalgorithmen]], [[Evolutionärer Algorithmus|genetische Algorithmen]] oder [[Künstliches neuronales Netz|künstliche neuronale Netze]] (dort vor allem das [[Hopfield-Netz]]), haben natürliche Prozesse als Vorbild. Prinzipiell können all diese Verfahren gute Lösungen berechnen, aber auch beliebig schlecht im Vergleich zu einer Optimallösung sein. Ihre Qualität und Laufzeit hängen wesentlich von der Definition und Implementierung der einzelnen Schritte ab.

==== 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. Diese Schranken sind insbesondere wichtig, um Aussagen über die Güte einer zulässigen Tour zu treffen.
Da beispielsweise jede Tour, also insbesondere auch eine optimale, genau <math>n</math> Kanten enthält, muss sie mindestens so lang sein wie die Summe der <math>n</math> 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 (Graphentheorie)|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 spannender Baum|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. Etwas allgemeiner kann man auch einen sogenannten minimalen ''1-Baum'' berechnen. Dies ist ein minimal aufspannender Baum zwischen den Knoten 2 bis <math>n</math> (bei beliebiger Nummerierung), der über die zwei kürzestmöglichen Kanten an den Knoten mit der Nummer 1 angebunden wird (daher der Name). Auch dessen Länge liefert eine untere Schranke. Weiterhin ist jede Tour auch ein [[B-Matching|perfektes 2-Matching]]. Das bedeutet also, dass eine kürzeste Tour mindestens so lang sein muss, wie der Wert eines minimalen perfekten 2-Matchings, das sich in O(n³) berechnen lässt.

==== Übersicht ====
In der folgenden Übersichtstabelle sind für die meisten hier vorgestellten Heuristiken der Typ des Verfahrens, die maximale Laufzeit bei <math>n</math> Städten <!-- und m = O(n²) Kanten-->sowie evtl. Gütegarantien für die berechneten Lösungen aufgeführt. Da die Laufzeit und Qualität von Metaheuristiken stark von der Wahl der Teilalgorithmen abhängig sind und sich nicht allgemein angeben lassen, sind sie hier nicht aufgeführt.

{| class="wikitable"
|-
! Verfahren
! Typ
! [[Landau-Symbole|Laufzeit]]
! Max. Abweichung vom Optimum
|-
| [[Nearest-Neighbor-Heuristik]]
| Eröffnungsheuristik
| <math>\mathcal{O}(n^2)</math> <!-- für jeden Knoten einmal alle Nachbarn abklappern -->
| Faktor (log(n)+1)/2 (metrisches TSP)
|-
| [[Farthest-Neighbor-Heuristik]]
| Eröffnungsheuristik
| <math>\mathcal{O}(n^2)</math> <!-- für jeden Knoten einmal alle Nachbarn abklappern -->
| beliebig groß
|-
| [[Farthest-Insertion-Heuristik]]
| Einfügeheuristik
| <math>\mathcal{O}(n^2)</math> <!-- für jeden einzufügenden Knoten einmal alle Teiltourknoten abklappern -->
| beliebig groß
|-
| [[Nearest-Insertion-Heuristik]]
| Einfügeheuristik
| <math>\mathcal{O}(n^2)</math> <!-- für jeden einzufügenden Knoten einmal alle Teiltourknoten abklappern -->
| beliebig groß, Faktor 2 (metrisches TSP)<ref>Nach Rosenkrantz, D.J.; Stearns, R.E.; Lewis, P.M. "Approximate algorithms for the traveling salesperson problem", Conference on Switching and Automata Theory, 1974.
[[doi:10.1109/SWAT.1974.4]]</ref>
|-
| [[Minimum-Spanning-Tree-Heuristik]]
| Eröffnungsheuristik
| <math>\mathcal{O}(n^2 \log(n))</math> <!-- O(m log m) für das Sortieren der Kantenlängen, n² log n² = 2n² log n -->
| wie Nearest-Insertion
|-
| [[Christofides-Heuristik]]
| Eröffnungsheuristik
| <math>\mathcal{O}(n^3)</math> <!-- O(n³) für das minimale perfekte Matching -->
| Faktor 1,5 (metrisches TSP)
|-
| [[K-Opt-Heuristik]]
| Verbesserungsheuristik
| <math>\mathcal{O}(k!)</math> pro Schritt <!-- 2k-Städte-TSP, um die 2k Endknoten gelöschter Tourkanten wieder zu verbinden -->
| beliebig groß
|-
| Summe der n kürzesten Kanten
| Dualheuristik
| <math>\mathcal{O}(n^2 \log(n))</math> <!-- O(m log m) für das Sortieren der Kantenlängen, n² log n² = 2n² log n -->
| beliebig groß
|-
| Länge eines [[Minimal spannender Baum|minimalen aufspannenden Baumes]]
| Dualheuristik
| <math>\mathcal{O}(n^2 \log(n))</math> <!-- O(m log m) für das Sortieren der Kantenlängen, n² log n² = 2n² log n -->
| beliebig groß
|-
|}

=== Praktische Grenzen der Berechenbarkeit ===
Die größte nicht-triviale Instanz eines (symmetrischen) Rundreiseproblems, die bisher nachweisbar optimal gelöst wurde, ist ein Planungsproblem für das Layout [[integrierter Schaltkreis]]e mit 85.900&nbsp;Knoten.<ref name=":0" /><ref name=":3" /> Dieser Rekord wurde in den Jahren 2005/2006 von [[William Cook (Mathematiker)|William Cook]] und anderen mit Hilfe einer Kombination aus verschiedenen [[Heuristik]]en und dem [[Ganzzahlige lineare Optimierung#Branch-and-Bound bzw. Branch-and-Cut|Branch-and-Cut]]-basierten Programm ''Concorde'' aufgestellt, wobei frühere Teilergebnisse verschiedener universitärer Arbeitsgruppen als Grundlage verwendet wurden.<ref name="CookEspinozaGoycoolea2005" /> Mit Hilfe spezieller Dekompositionstechniken und dem Einsatz mehrerer paralleler Computer haben William Cook und andere unter anderem Touren für ein TSP auf über 10 Millionen [[Stern]]en gefunden, deren Länge nachweislich höchstens 0,003 % vom Optimum abweicht.<ref name=":1" />

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 [[Kombinatorische Optimierung|kombinatorischen Optimierungsproblemen]] – die Schwierigkeit der Lösung stark von den Eingabeparametern (in diesem Fall den Kantengewichten) abhängt. Ein kleineres Problem kann deutlich schwerer lösbar sein; beispielsweise gibt es in der TSPLIB eine aufgrund ihrer vielen Symmetrien schwer optimal zu lösende Instanz mit nur 225 Städten<ref>[https://users.encs.concordia.ca/~chvatal/tsp/tsp.html TSP-Seite von Vašek Chvátal]</ref>, wobei heutzutage alle Instanzen der TSPLIB mit dem Solver Concorde gelöst werden können<ref name=":2">{{Internetquelle |autor=William Cook |url=https://www.math.uwaterloo.ca/tsp/pla85900/index.html |titel=Optimal 85,900-Point Tour: A VLSI Application |hrsg=Mathematics Department University Waterloo |sprache=en |abruf=2024-01-16}}</ref>.

== Varianten und Anwendungen ==
Schon die klassische Variante des Problems tritt in vielen Anwendungen auf, beispielsweise in der [[DNA-Sequenzierung]], beim Layout [[integrierter Schaltkreis]]e oder bei der Steuerung eines [[Bohrer]]s in der Herstellung von [[Leiterplatte]]n.<ref>[http://www.tsp.gatech.edu/apps/index.html Dokumentierte Anwendungen von Concorde]</ref>
Auch Astronomen suchen bei Himmelsdurchmusterungen die kürzeste Route von Stern zu Stern.

Die Vielzahl an kombinierbaren Varianten bilden zusammen die ''Familie der TSP'' – die alle als [[NP-Schwere|NP-schwer]] gelten. Einige der Verallgemeinerungen betrachten mehrere Handlungsreisende, während sich andere Varianten durch grundlegend veränderte Optimierungskriterien oder durch zusätzliche Nebenbedingungen von der klassischen Version unterscheiden.

Die Vorgehensweise in der Praxis unterscheidet sich von der mathematischen Theorie dadurch, dass man zumeist keine beste Lösung sucht, sondern nur eine ausreichend gute. Hierbei muss der Gesamtaufwand betrachtet werden – als Aufwand für Durchführung ''und'' Berechnung. Was dabei „gut“ bedeutet und welche Kriterien zum Tragen kommen, hängt vom Kontext des Problems ab. So wird man sich für eine einmalige Liefertour weniger Mühe machen als für die Bestückungsplanung einer Leiterplatte, die in einer Millionenauflage hergestellt wird.

=== Mehrere Handlungsreisende ===
Beim ''multiple TSP (mTSP)''<!--"multiple“ ist das englische Wort, also kein Grammatikfehler--> werden die Städte auf mehrere Handlungsreisende aufgeteilt, wobei alle ihre Rundreisen in derselben Stadt starten und dort auch beenden. Jede Stadt muss von genau einem Handlungsreisenden besucht werden. Ziel ist die Minimierung der zurückgelegten Gesamtstrecke. In der Variante ''mTSP with nonlazy Salesmen'' werden nur Rundreisen mit mindestens zwei Städten zugelassen, so dass sich jeder Rundreisende tatsächlich fortbewegen muss. Die klassische Version ergibt sich als Spezialfall mit nur einem Handlungsreisenden.

Das ''[[Vehicle Routing Problem|Vehicle Routing Problem (VRP)]]'' ist ein multiple TSP mit zusätzlichen Transportkapazitätsrestriktionen. Es 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 [[Lastkraftwagen|Transportern]], die von dem gemeinsamen Depot aus starten und wieder dorthin zurückkehren. Ziel des 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, entspricht das VRP dem ''mTSP'' und ist daher ebenfalls [[NP-Schwere|NP-schwer]]. Vom ''Vehicle Routing Problem'' (''VRP'') abgeleitete Varianten sind:

; Capacitated VRP (''CVRP'')
: Alle Transporter haben eine maximale Kapazität.
; Multiple Depot VRP (''MDVRP'')
: Die Transporter können von mehreren verschiedenen Depots starten.
; VRP with Time Windows (''VRPTW'')
: Die Kunden können jeweils nur innerhalb vorgegebener Zeitfenster beliefert werden.
; 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.
; Dynamisches VRP (''DVRP'')
: Zusätzlicher Bedarf kann während der Berechnung entstehen, was vorzeitig zu berücksichtigen ist.
: {{Siehe auch|Vehicle Routing Problem}}

=== Städtecluster ===
Beim ''generalized TSP (GTSP)'' (deutsch: verallgemeinertes TSP) werden mehrere Städte zu einem Cluster zusammengefasst. Der Handlungsreisende muss aus jedem Cluster genau eine Stadt besuchen. Das TSP ist ein Spezialfall des GTSP, in dem jede Stadt in einem Cluster liegt, der eben nur diese eine Stadt enthält. Jede Instanz des GTSP lässt sich in eine Instanz des einfachen TSP überführen und mit den für dieses Problem bekannten Algorithmen lösen. Aus diesem Grund ist auch das GTSP NP-schwer.

In der Praxis werden die Lösungsalgorithmen des GTSP zum Beispiel dazu verwendet, den Leerweg von [[Computerized Numerical Control|CNC]]-Schneidemaschinen zu optimieren. Diese werden unter anderem in der Textilbranche eingesetzt, um aus einer großen Bahn Stoff kleinere Teile für Kleidungsstücke auszuschneiden. Hierbei stellen die auszuschneidenden Konturen die Cluster und die möglichen Ansatzpunkte des [[Schneidwerkzeug]]es auf den Konturen die Städte dar.

=== Änderungen des Optimierungskriteriums ===
Beim ''Prize Collecting TSP'' (''PCTSP'') werden dem Handlungsreisenden in jeder Stadt bestimmte Preisgelder bezahlt (beispielsweise Verkaufsumsätze). Um von einer Stadt zur nächsten zu reisen, muss er jedoch Kosten aufbringen. Er soll nun eine vorgegebene Anzahl von Städten und eine Rundreise zwischen diesen Städten so auswählen, dass der Gewinn maximal wird. Da das Problem als Spezialfall die klassische Variante enthält (alle Städte werden besucht und alle Preisgelder sind 0), ist das PCTSP ebenfalls NP-schwer. Eine davon abgeleitete Form ist das ''Traveling Salesman Selection Problem'' (''TSSP''), bei dem zu vorgegebenem <math>k</math> eine kürzeste Tour zwischen beliebigen <math>k</math> Städten gesucht ist, wobei auf Preisgelder verzichtet wird und metrische Distanzen vorausgesetzt werden.

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, den [[Flaschenhals (Logistik)|Flaschenhälsen]], entgegenzuwirken. Eine verwandte Variante ist das ''maximum scatter TSP'', bei dem die kleinste verwendete Länge maximiert wird.

=== Zusätzliche Nebenbedingungen ===
Eine in Anwendungen häufige Einschränkung sind ''Zeitfenster'', in denen eine Stadt besucht werden muss. Beispielsweise vereinbart ein technischer Kundendienst zur Reparatur von Haushaltsgeräten mit Kunden in der Regel einen Zeitraum, in dem der Besuch des Technikers erfolgt. Dieser Zeitraum muss bei der Tourenplanung berücksichtigt werden.

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 ändert dann seine Tour so ab, dass neue Städte „möglichst gut“ in seine bisher geplante Tour passen. Diese Variante tritt beispielsweise bei Pannendiensten wie dem [[ADAC]] auf, wo Positionen liegengebliebener Autos erst nach und nach bekannt werden und die Zentrale versucht, neue Fälle möglichst günstig in bestehende Touren einzubauen. Da viele Pannenhelfer unterwegs sind und die Zentrale bei der Meldung einer Panne eine ungefähre Zeitangabe macht, wann ein Pannenhelfer eintrifft, handelt es sich um ein ''Multiple Online TSP mit Zeitfenstern''.

Der Paketdienst [[United Parcel Service|UPS]] mit rund 55.000 Kurierfahrern und durchschnittlich 120 Paketen pro Tag und Fahrer verwendete bisher optimierte statische Routen für jedes Fahrzeug, die individuell von den Fahrern gemäß ihrer Erfahrung abgewandelt wurden. Ab 2013 stellt das Unternehmen auf das System ORION (''On-Road Integrated Optimization and Navigation'') um. Dieses berücksichtigt garantierte Lieferfristen für einzelne Pakete, angemeldete Abholungen und spezielle Kundenklassen mit bevorzugter Bedienung sowie Daten aus dem Verkehrsfluss in Echtzeit. Es lässt erfahrenen Mitarbeitern die Möglichkeit, von der vorgeschlagenen Route abzuweichen.<ref>Wired.com: [https://www.wired.com/2013/06/ups-astronomical-math/ The Astronomical Math Behind UPS’ New Tool to Deliver Packages Faster], 13. Juni 2013</ref> Für dieses Unternehmen kommt als weitere Bedingung hinzu, dass UPS-Fahrer in Städten mit regelmäßigem Straßenraster nicht links abbiegen, weil damit zu große Verzögerungen beim Warten auf Gegenverkehr und ein zu großes Unfallrisiko verbunden sind.<ref>New York Times: [https://www.nytimes.com/2007/12/09/magazine/09left-handturn.html Left-Hand-Turn Elimination], 9. Dezember 2007</ref>

== Literatur ==
* David Applegate, [[Robert Bixby]], [[Vašek Chvátal]], [[William Cook (Mathematiker)|William Cook]]: ''On the Solution of Traveling Salesman Problems''. Documenta Mathematica. Extraband 3 zum Internationalen Mathematikerkongress. Berlin 1998, S. 645–656. ([http://www.mathematik.uni-bielefeld.de/documenta/xvol-icm/17/Cook.MAN.ps.gz Postscript]; [[Gzip]]; 68&nbsp;kB)
* David L. Applegate, Robert E. Bixby, Vašek Chvátal, William J. Cook: ''The Traveling Salesman Problem. A Computational Study''. Princeton University Press, Februar 2007. ISBN 0-691-12993-2
* William J. Cook: ''In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation.'' Princeton University Press 2011, ISBN 0-691-15270-5.
* Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): ''The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization''. Wiley, Chichester 1985. ISBN 0-471-90413-9
* W. Domschke: ''Logistik – Rundreisen und Touren''. Oldenbourg-Verlag, München/Wien 1997 (4. Aufl.). ISBN 3-486-29472-5
* T. Grünert, S. Irnich: ''Optimierung im Transport.'' Bd. 2. Wege und Touren. [[Shaker Verlag]], Aachen 2005. ISBN 3-8322-4515-4
* Gregory Gutin, Abraham P. Punnen: ''The traveling salesman problem and its variations''. Kluwer Academic Publishers. Auszugsweise [https://books.google.de/books?id=mQ5RxzsuOXAC online] (englisch)
* Walter Schmitting: ''Das Traveling-Salesman-Problem – Anwendungen und heuristische Nutzung von Voronoi-/Delaunay-Strukturen zur Lösung euklidischer, zweidimensionaler Traveling-Salesman-Probleme'', 1999, Dissertation, Wirtschaftswissenschaftliche Fakultät, Heinrich-Heine-Universität Düsseldorf, {{URN|nbn:de:hbz:061-19990210-000314-6}}

== Weblinks ==
{{Commonscat|Traveling salesman problem|Problem des Handlungsreisenden}}
* [https://algorithms.discrete.ma.tum.de/graph-games/tsp-game/index_de.html TSP-Spiel] – ein interaktives Spiel zum ''Traveling Salesman Problem'' mit ausführlicher Erklärung und Darstellung des Lösungsverfahrens
* [https://www.math.uwaterloo.ca/tsp/ The Traveling Salesman Problem Home] – ausführliche Informationen zum ''Traveling Salesman Problem'' (englisch)
* [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ TSPLIB] – Sammlung von Benchmark-Instanzen des ''TSP'' und verschiedener Varianten (englisch)
* [https://www.spektrum.de/magazin/die-optimierte-odyssee/825343 Spektrum der Wissenschaft (4/99): Die optimierte Odyssee] – Artikel von [[Martin Grötschel]] und [[Manfred Padberg]]
* [https://www.bernabe.dorronsoro.es/vrp/ The VRP Web] – ausführliche Informationen zum ''Vehicle Routing Problem'' (englisch)
* [https://studylibde.com/doc/7873282/das-travelling-salesman-problem 40. Algorithmus der Woche – Informatikjahr 2006] ''TSP'' oder ''die optimale Tour für den Nikolaus''
* {{Internetquelle |url=http://zbw.eu/stw/descriptor/15520-6 |titel=Rundreiseproblem |werk=[[Standard-Thesaurus Wirtschaft]] |hrsg=[[ZBW – Leibniz-Informationszentrum Wirtschaft|ZBW]] |abruf=2024-12-31}}

== Einzelnachweise ==
<references />

{{Exzellent|7. November 2006|23501139}}

{{Normdaten|TYP=s|GND=4185966-2|LCCN=sh85137179}}

[[Kategorie:Problem (Graphentheorie)]]
[[Kategorie:Kombinatorische Optimierung]]
[[Kategorie:Reise- und Routenplanung]]