Wie lautet die Geschichte des Problems der Handelsreisenden im Laufe der Jahre in einer kurzen, aufzählenden Liste?
What is the history of the travelling salesman problem throughout the years in a short bulleted list?
* 19th century - mathematically formulated for first time by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman
* 1930s - First studied by mathematicians in Vienna and at Harvard, most notably by Karl Menger and Merill M. Flood who was looking to solve a school bus routing problem.
* 1959 - Jillian Beardwood, J.H. Halton and John Hammersley published an article entitled "The Shortest Path Through Many Points" in the journal of the Cambridge Philosophical Society, which provided the first practical solution.
* 1960s - new approach is created, which produce a solution whose length is provably bounded by a multiple of the optimal length.
* 1972 - Richard M. Karp showed that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of traveling salesman problem.
* 1976 - Christofides and Serdyukov independently invented new algorithm, which yields a solution that in the worst case is at most 1.5 times longer than the optimal solution.
* 1990s -  Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions.
* 1991 - Gerhard Reinelt published the TSPLIB, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results
* 2006 - Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance.
* 2011 - Slightly improved approximation algorithm is developed for the subset of "graphical" traveling salesman problem.
* 2020 - The slightly improved approximation algorithm developed for the subset of "graphical" is extended to cover the full traveling salesman problem.
* 19. Jahrhundert - erstmals mathematisch formuliert von dem irischen Mathematiker William Rowan Hamilton und dem britischen Mathematiker Thomas Kirkman.
* 1930er Jahre - Erstmals von Mathematikern in Wien und in Harvard untersucht, vor allem von Karl Menger und Merill M. Flood, der ein Schulbus-Routing-Problem lösen wollte.
* 1959 - Jillian Beardwood, J.H. Halton und John Hammersley veröffentlichen einen Artikel mit dem Titel "The Shortest Path Through Many Points" in der Zeitschrift der Cambridge Philosophical Society, der die erste praktische Lösung liefert.
* 1960er Jahre - ein neuer Ansatz wird entwickelt, der eine Lösung liefert, deren Länge nachweislich durch ein Vielfaches der optimalen Länge begrenzt ist.
* 1972 - Richard M. Karp zeigt, dass das Hamilton-Zyklus-Problem NP-komplett ist, was die NP-Härte des Traveling-Salesman-Problems impliziert.
* 1976 - Christofides und Serdyukov entwickeln unabhängig voneinander einen neuen Algorithmus, der im schlimmsten Fall eine Lösung liefert, die höchstens 1,5 Mal länger ist als die optimale Lösung.
* 1990er Jahre - Applegate, Bixby, Chvátal und Cook entwickelten das Programm Concorde, das in vielen neueren Rekordlösungen verwendet wurde.
* 1991 - Gerhard Reinelt veröffentlichte die TSPLIB, eine Sammlung von Benchmark-Instanzen mit unterschiedlichem Schwierigkeitsgrad, die von vielen Forschungsgruppen zum Vergleich der Ergebnisse genutzt wurde.
* 2006 - Cook und andere berechneten eine optimale Tour durch eine 85.900-Städte-Instanz, die durch ein Mikrochip-Layout-Problem gegeben ist und derzeit die größte gelöste TSPLIB-Instanz darstellt.
* 2011 - Ein leicht verbesserter Approximationsalgorithmus wird für die Untermenge des "grafischen" Traveling Salesman Problems entwickelt.
* 2020 - Der leicht verbesserte Approximationsalgorithmus, der für die Teilmenge des "grafischen" Problems entwickelt wurde, wird auf das gesamte Traveling-Salesman-Problem ausgeweitet.
closed_qa
Die Ursprünge des Problems der Handelsreisenden sind unklar. In einem Handbuch für Handelsreisende aus dem Jahr 1832 wird das Problem erwähnt und es werden Beispieltouren durch Deutschland und die Schweiz angeführt, aber es gibt keine mathematische Behandlung.


William Rowan Hamilton
Das TSP wurde im 19. Jahrhundert von dem irischen Mathematiker William Rowan Hamilton und von dem britischen Mathematiker Thomas Kirkman mathematisch formuliert. Hamiltons ikosianisches Spiel war ein Freizeiträtsel, bei dem es darum ging, einen Hamilton-Zyklus zu finden. Die allgemeine Form des TSP wurde anscheinend erstmals in den 1930er Jahren von Mathematikern in Wien und in Harvard untersucht, insbesondere von Karl Menger, der das Problem definiert, den offensichtlichen Brute-Force-Algorithmus betrachtet und die Nichtoptimalität der Nearest Neighbour-Heuristik feststellt:

Wir bezeichnen als Botenproblem (da diese Frage in der Praxis von jedem Briefträger, aber auch von vielen Reisenden gelöst werden sollte) die Aufgabe, für endlich viele Punkte, deren paarweise Entfernungen bekannt sind, die kürzeste Route zu finden, die die Punkte verbindet. Natürlich ist dieses Problem durch endlich viele Versuche lösbar. Regeln, die die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte drücken würden, sind nicht bekannt. Die Regel, dass man zuerst vom Startpunkt zum nächstgelegenen Punkt gehen sollte, dann zum nächstgelegenen Punkt usw., führt im Allgemeinen nicht zum kürzesten Weg.

Erstmals mathematisch betrachtet wurde es in den 1930er Jahren von Merrill M. Flood, der ein Schulbus-Routenproblem lösen wollte. Hassler Whitney von der Princeton University weckte das Interesse an dem Problem, das er das "48-Staaten-Problem" nannte. Die früheste Veröffentlichung, in der der Begriff "Travelling-Salesman-Problem" verwendet wurde, war der Bericht der RAND Corporation von Julia Robinson aus dem Jahr 1949, "On the Hamiltonian game (a traveling salesman problem)."

In den 1950er und 1960er Jahren wurde das Problem in wissenschaftlichen Kreisen in Europa und den Vereinigten Staaten immer populärer, nachdem die RAND Corporation in Santa Monica Preise für Schritte zur Lösung des Problems ausgelobt hatte. Bemerkenswerte Beiträge leisteten George Dantzig, Delbert Ray Fulkerson und Selmer M. Johnson von der RAND Corporation, die das Problem als ganzzahliges lineares Programm formulierten und die Schneidebenenmethode zu seiner Lösung entwickelten. Sie schrieben die als bahnbrechend geltende Arbeit zu diesem Thema, in der sie mit diesen neuen Methoden einen Fall mit 49 Städten optimal lösten, indem sie eine Tour konstruierten und bewiesen, dass keine andere Tour kürzer sein konnte. Dantzig, Fulkerson und Johnson spekulierten jedoch, dass wir bei einer nahezu optimalen Lösung in der Lage sein könnten, Optimalität zu finden oder zu beweisen, indem wir eine kleine Anzahl von zusätzlichen Ungleichungen (Schnitten) hinzufügen. Sie nutzten diese Idee, um ihr ursprüngliches 49-Städte-Problem mit Hilfe eines String-Modells zu lösen. Sie fanden heraus, dass sie nur 26 Schnitte benötigten, um eine Lösung für ihr 49-Städte-Problem zu finden. Diese Arbeit lieferte zwar keinen algorithmischen Ansatz für TSP-Probleme, aber die darin enthaltenen Ideen waren unverzichtbar, um später exakte Lösungsmethoden für das TSP zu entwickeln, auch wenn es noch 15 Jahre dauern sollte, bis ein algorithmischer Ansatz für die Erstellung dieser Schnitte gefunden wurde. Neben den Methoden der Schnittebene verwendeten Dantzig, Fulkerson und Johnson vielleicht zum ersten Mal Branch-and-Bound-Algorithmen.

1959 veröffentlichten Jillian Beardwood, J.H. Halton und John Hammersley einen Artikel mit dem Titel "The Shortest Path Through Many Points" (Der kürzeste Weg durch viele Punkte) in der Zeitschrift der Cambridge Philosophical Society. Das Beardwood-Halton-Hammersley-Theorem bietet eine praktische Lösung für das Problem des Handelsreisenden. Die Autoren haben eine asymptotische Formel abgeleitet, um die Länge des kürzesten Weges für einen Handelsvertreter zu bestimmen, der von einem Haus oder Büro aus eine bestimmte Anzahl von Orten besucht, bevor er zum Ausgangspunkt zurückkehrt.

In den folgenden Jahrzehnten wurde das Problem von vielen Forschern aus der Mathematik, Informatik, Chemie, Physik und anderen Wissenschaften untersucht. In den 1960er Jahren wurde jedoch ein neuer Ansatz entwickelt, bei dem nicht nach optimalen Lösungen gesucht wurde, sondern eine Lösung gefunden werden sollte, deren Länge nachweislich durch ein Vielfaches der optimalen Länge begrenzt ist, um so untere Schranken für das Problem zu schaffen; diese unteren Schranken wurden dann bei Branch-and-Bound-Ansätzen verwendet. Eine Methode, dies zu tun, bestand darin, einen minimal spannenden Baum des Graphen zu erstellen und dann alle seine Kanten zu verdoppeln, was zu der Schranke führt, dass die Länge einer optimalen Tour höchstens doppelt so groß ist wie das Gewicht eines minimal spannenden Baums.

1976 erzielten Christofides und Serdyukov unabhängig voneinander einen großen Fortschritt in dieser Richtung: Der Christofides-Serdyukov-Algorithmus führt zu einer Lösung, die im schlimmsten Fall höchstens 1,5-mal länger ist als die optimale Lösung. Da der Algorithmus einfach und schnell war, hofften viele, dass er zu einer Methode führen würde, die einer optimalen Lösung nahe kommt. Diese Hoffnung auf eine Verbesserung erfüllte sich jedoch nicht sofort, und Christofides-Serdyukov blieb die Methode mit dem besten Worst-Case-Szenario bis 2011, als ein (sehr) leicht verbesserter Näherungsalgorithmus für die Teilmenge der "grafischen" TSPs entwickelt wurde. Im Jahr 2020 wurde diese winzige Verbesserung auf das vollständige (metrische) TSP ausgeweitet.

Richard M. Karp zeigte 1972, dass das Hamilton-Zyklusproblem NP-komplett ist, was die NP-Härte von TSP impliziert. Dies lieferte eine mathematische Erklärung für die offensichtliche Rechenschwierigkeit bei der Suche nach optimalen Touren.

Große Fortschritte wurden in den späten 1970er und 1980er Jahren erzielt, als Grötschel, Padberg, Rinaldi und andere es schafften, Instanzen mit bis zu 2.392 Städten mithilfe von Schnittebenen und Branch and Bound exakt zu lösen.

In den 1990er Jahren entwickelten Applegate, Bixby, Chvátal und Cook das Programm Concorde, das in vielen aktuellen Rekordlösungen verwendet wurde. Gerhard Reinelt veröffentlichte 1991 die TSPLIB, eine Sammlung von Benchmark-Instanzen mit unterschiedlichem Schwierigkeitsgrad, die von vielen Forschungsgruppen zum Vergleich der Ergebnisse genutzt wurde. Im Jahr 2006 berechneten Cook und andere eine optimale Tour durch eine Instanz mit 85.900 Städten, die durch ein Mikrochip-Layout-Problem gegeben ist und derzeit die größte gelöste TSPLIB-Instanz darstellt. Für viele andere Instanzen mit Millionen von Städten können Lösungen gefunden werden, die garantiert innerhalb von 2-3% einer optimalen Tour liegen.
de