Kandidatenmengen für das TSP

Más información sobre el libro

Das Traveling Salesman Problem (TSP) ist ein zentrales Problem im Operations Research, das die Planung einer minimalen Rundreise durch eine bestimmte Anzahl von Städten betrifft. Es findet zahlreiche Anwendungen in Bereichen wie Logistik, Maschinensteuerung und Personaleinsatzplanung. Trotz der einfachen Formulierung erweist sich die exakte Lösung für relevante Problemgrößen als äußerst komplex. Daher hat sich die heuristische Lösung als besonders effektiv für Theorie und Praxis erwiesen. Heutzutage können auch große TSP in akzeptabler Zeit mit guten, wenn auch nicht optimalen, Ergebnissen gelöst werden. Mit der technischen Entwicklung wachsen jedoch die Herausforderungen in der TSP-Forschung. Um schnelle und effiziente Lösungen für große TSP zu finden, ist es sinnvoll, die Suche auf vielversprechende Wege zwischen den Städten zu beschränken, anstatt alle möglichen Routen zu betrachten. Diese Auswahl wird als Kandidatenmenge oder Candidate Set bezeichnet. Die Arbeit behandelt die Erzeugung und Verwendung von Kandidatenmengen im Zusammenhang mit der heuristischen Lösung einer spezifischen TSP-Klasse und führt eine neuartige Methode zur Generierung von Kandidatenmengen ein. Diese Methode wird einer umfassenden empirischen Analyse unterzogen und zeigt vielversprechende Ergebnisse.