Das grundsätzliche Problem beim TSP ist die Anzahl der Lösungen, die mit jedem zusätzlichen Knoten um eine Fakultät ansteigt. Diese Anzahl gilt es zu verringern, um daraus die optimale Lösung zu ermitteln. Sind Kanten bekannt, die zur optimalen Lösung gehören, so vermindert sich die Anzahl der Lösungen um eine Fakultät je bekannter Kante. Im geringeren Umfang wird das Problem auch dann kleiner, wenn man Kanten, die nicht zur optimalen Lösung gehören, ausschließen kann.

Für allgemeine TSP gilt:
Es gibt erkennbar kein Merkmal, das eine Kante von vornherein als zur optimalen Lösung zugehörig erkennen lässt. Gleiches gilt auch für den negativen Fall. Es gibt kein Merkmal, das eine Kante von vornherein ausschließt. Daraus folgt, dass weder die kleinste Kante immer zur optimalen Lösung gehört (z. B. Raute) noch die größte Kante immer ausgeschlossen werden kann (z.B. Trapez).

Anders verhält es sich beim TSP im euklidischen Raum, bei dem man die Lage im Raum ausnutzen kann. Eine besondere Rolle spielt dabei u.a. die konvexe Hülle aller beteiligten Knoten:

a) absoluter Ausschluss:
Aufgrund der geografischen Kreuzungsfreiheit von optimalen TSP kann man alle Kanten, die die Fläche der konvexen Hülle teilen, von vornherein ausschließen; das sind alle Kanten, die zwei Knoten auf der konvexen Hülle verbinden, soweit diese Knoten nicht benachbart sind. Liegen alle Knoten auf der konvexen Hülle, so folgt daraus trivial, dass die Kanten der konvexen Hülle die optimale Lösung des TSP darstellen. 

b) relativer Ausschluss:
Weiter muss bekanntlich eine optimale Lösung des TSP von einem Knoten auf der konvexen Hülle immer - direkt oder über weitere innerhalb der konvexen Hülle liegenden Knoten - zum benachbarten Knoten der konvexen Hülle führen, ehe der Weg einen anderen Knoten der Hülle berührt. Daraus folgt, dass ein Knoten, der durch eine Kante direkt oder über weitere Kanten mit einem Knoten auf der konvexen Hülle verbunden ist, nur - direkt oder wieder über weitere Kanten - mit einem benachbarten Knoten der konvexen Hülle verbunden werden kann. Kanten, die in diesem Zusammenhang zu nicht-benachbarten Knoten der konvexen Hülle führen, können also ausgeschieden werden.

c) Nähe von inneren Knoten zu Knoten auf der konvexen Hülle:
Aus der Nähe zu einem Knoten auf der konvexen Hülle kann man nicht schließen, dass bei einer optimalen Lösung ein Knoten, der innerhalb der konvexen Hülle liegt, mit diesem (direkt oder über weitere innere Knoten) verbunden ist. Somit kann man für eine optimale Lösung aufgrund der Nähe von zwei entsprechenden Knoten keine Kanten von vornherein zuweisen oder ausschließen.

d) allgemeiner Ausschluss:
Allgemein gilt, dass aufgrund der geografischen Kreuzungsfreiheit von optimalen TSP alle Kanten ausgeschlossen werden können, die eine Kante des optimalen TSP schneiden. 

Nicht-negativ-Bedingung und Dreiecks-Ungleichung:
Die häufig geforderte Nicht-negativ-Bedingung der Kosten einer Kante sowie die  Dreiecks-Ungleichung lässt sich immer durch die Erhöhung aller Ausprägungen um einen entsprechenden Fixkosten-Betrag erfüllen. Ggf. ist das TSP dann aber nicht mehr im geografischen Raum abbildbar. 
Aufgrund des kombinatorischen Lösungsansatzes sind beide Anforderungen für die ZIP-Methode irrelevant. Die mit Hilfe eines Zufallsgenerator erzeugte Matrix des Beispiels mit 10 Knoten erfüllt nicht die Dreiecks-Ungleichung. Weiter hätten die Kanten auch negative Werte haben können.

Auf die Dissertation 1998 von Dr. Walter Schmitting, Münster, der in seiner Arbeit einen umfassenden und ausführlichen Überblick ( mit umfangreichen Quellenangaben) über optimale und und heuristische Lösungen gibt, sei hier nochmals hingewiesen. 

 wird fortgesetzt ...

(19.07.2003)