| |
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.
|
|