Das Problem des TSP


 

 

Das Problem des Traveling Salesman Problem liegt in der Anzahl der möglichen Rundreisen.  Alle Lösungsansätze gehen von dieser Menge der Rundreisen aus und versuchen, nicht- optimale Rundreisen auszuscheiden, um so zu optimalen bzw. suboptimalen Rundreisen zu gelangen. 

Im Gegensatz dazu verringert man mit der ZIP-Methode zuerst die Ausgangsmenge der möglichen Rundreisen auf die Anzahl möglicher Teilrundreisen und nimmt diese neue um Größenordnungen verringerte Anzahl als Ausgangspunkt aller weiteren Berechnungen. Die Verrimgerung der Ausgangsmenge ist bei symmetrischen Rundreisen besonderes groß. Dabei sind grundsätzlich alle bisherigen Lösungsansätze möglich, soweit sie nicht der neuen Struktur der Anzahl der Teilrundreisen widersprechen. Ggf. lassen sich jedoch auch neue Lösungen finden. Die ZIP-Methode wird also den bisherigen Lösungsansätzen vorgeschaltet.

Der Autor nutzt für seine Beispiele die bekannte Enumeration, um die praktische Durchführung der ZIP-Methode zu zeigen. Entscheidend dabei ist jedoch die durch die ZIP-Methode minimierte Ausgangsmenge, die es z.B. ermöglicht, bisher optimal nicht berechnenbare typische  Rundreisen mit 25 Städten kombinatorisch zu lösen. Die ZIP-Methode führt somit aufgrund der minimierten Ausgangsmenge zu besseren Lösungen bereits bekannter Verfahren.