Am Anfang war es reiner Zufall, am Ende ist alles immer ganz einfach.

Die Geschichte begann 1985: Der Autor, seit einigen Jahren Programmierer,  ist 1985 das erste Mal mit dem Rundreiseproblem in Berührung gekommen. Das im Fachschullehrbuch Mathematik für Wirtschaftswissenschaften, Verlag die Wirtschaft, Berlin (DDR),1983, beschriebene Rundreiseproblem (S 418ff. ) war sehr anschaulich und schien auf den ersten Blick einfach, eine Lösung schnell gefunden. Bald stellte der Autor aber fest, dass mit wachsender Zahl der Orte alle Rundreisen nicht mehr optimal berechenbar sind. Diese Aussage wollte er zumindest im Ansatz überprüfen. 

Nach den üblichen Anfängerfehlern und simplen Lösungen, die natürlich bereits alle bekannt waren, und mit den damit verbundenen Enttäuschungen fing der Autor noch einmal von vorn an. Als "Zahlen"-Mensch (Programmierer) störte ihn, dass bei einer Rundreise jeder Ort, d.h. jede Zahl, zweimal vorkommt, einmal als Anfangs- und einmal als Endpunkt einer Strecke.  Was kommt heraus, wenn nun jede Zahl nur einmal vorkommt? Und was bleibt bei einer Rundreise mit 6 Orten übrig? Er fing an, die Möglichkeiten aufzuschreiben, bis er bemerkte, dass es nur sehr wenige Grundformen gab. Das war der  entscheidende Moment.  Alles weitere bis heute baut nur noch auf diese Erkenntnis auf:

Der Autor stellte fest, dass sich die 5! =120 möglichen Rundreisen mit 6 Orten auf genau 15 Grundformen (= Teilrundreisen) zurückführen lassen. Die fehlenden Teile hatten genau dieselbe Struktur. Zu jeder Teilrundreise gibt es genau 8 passende "Komplement-" Teilrundreisen. Der Algorithmus war klar: Statt 1 x 2 x 3 x 4 x 5 .... sind es nur  1 x 3 x 5 x 7 ... . 
Die fehlenden 2 x 4 x 6 ....  ergeben genau die Anzahl der Komplement-Teilrundreisen. Diese Zerlegungsmethode war auch offensichtlich noch nicht bekannt (29.3.1985).

1998 fand der Autor die allgemeine Formel für die Mächtigkeit der Teilgraphen (s.Anmerk.3.3.). Damit war auch die mathematische Erklärung geliefert: Die Fakultät im Nenner beschreibt die Permutation der freien Kanten, die 2-Potenzen im Nenner die Variation der freien Kanten bei Symmetrie. Wegen der Form der Zerlegung und Zusammenfügung wie ein Reißverschluss bezeichnete der Autor die neue Methode als  ZIP-Methode.

Ist die ZIP-Methode wirklich neu?

Ob diese Zerlegungsmethode wirklich neu ist, kann man natürlich nie sagen. Zwei Gründe sprechen jedoch dafür, dass diese Methode allgemein noch nicht bekannt ist:

1.
Die Struktur der Zerlegung ist überraschend einfach und dehnt auf jeden Fall die Grenze der optimal berechenbaren Rundreisen nach oben aus. Man kann daher davon ausgehen, dass die ZIP-Methode veröffentlicht sein würde, wenn sie bekannt wäre. Der Autor hat bei seinen Literatur-Recherchen und schließlich auch im Internet nicht einmal im Ansatz einen Hinweis auf diese Methode gefunden. Wenn selbst  Kenner des TSP wie Grötschel und Padberg 1999 in der "Optimierten Odyssee" schreiben, dass kombinatorisch Rundreisen mit 25 Knoten nicht optimal lösbar seien, dann scheint die ZIP-Methode wirklich neu zu sein.

2.
Es gibt außerdem eine einleuchtende Erklärung, warum die ZIP-Methode bisher nicht entdeckt wurde: 
Jeder, der sich mit dem TSP beschäftigt, ist unmittelbar gefangen von der geographischen Vorstellung einer Rundreise.  Man hat sofort die Vorstellung einer Aneinanderreihung von Strecken. Das Ende einer Strecke ist der Anfangspunkt der folgenden. Müller-Merbach spricht deshalb auch von einem Reihenfolgeproblem. Diese geographische Vorstellung blockiert (zuverlässig!) den Weg zum hier vorgestellten Lösungsansatz. Erst die Betrachtung der reinen Zahlen, d.h. die algebraische Sicht, führte den Autor zufällig zu dieser Lösung.

(17.04.2004)