DasTraveling-Salesman-Problem (TSP) gilt als eines der klassischen kombinatorischen Probleme. Optimale Lösungen für TSP mit großer Anzahl von Orten sind Spezialfälle geografischer Natur und arbeiten als solche in metrischen Räumen. Im Gegensatz dazu sind bei allgemeinen TSP Optimallösungen nur mit einer vollständigen Analyse der n! denkbaren Rundreisen möglich; sie gelten daher als nicht effizient lösbar. 

Hier wird eine neue Zerlegungsmethode - die ZIP-Methode - vorgestellt, die kombinatorisch die bisherige Grenze optimaler Lösungen für allgemeine TSP klar überschreitet. Prinzipiell ist die neue Methode auch auf nicht-symmetrische TSP anwendbar. Die zusätzlichen Beispiele enthalten eine Vielzahl von Anregungen für weitere Untersuchungen. 
(deutsch)

Weiter zum Inhaltsverzeichnis