Die Hauptschwierigkeit des Traveling Salesman Problem liegt nicht in der Berechnung der einzelnen  Graphen, sondern in der mit Zunahme der Knoten um ganze Fakultäten wachsenden Anzahl der möglichen Graphen. In der Praxis sind leistungsfähige, suboptimale Lösungen, die möglichst nahe dem Optimum liegen, häufig ausreichend. Hingegen laufen Optimallösungen auf eine vollständige Analyse der n! möglichen Graphen hinaus.  

Ohne Eingrenzung:
Daraus folgt, dass eine vollständige Enumeration nur für eine kleine Anzahl von Knoten möglich ist. Dabei ist es unerheblich, ob diese Grenze nun bei 15 Knoten oder erst bei 20 Knoten liegt oder noch weiter hinausgeschoben werden kann. Die Anzahl bleibt immer klein.

Eingrenzung über die Summe:
Oft kann man aber schon im Laufe der Berechnung einzelner Graphen anhand der erreichten Summe der Kantenwerte feststellen, dass ein Optimum nicht mehr gefunden werden kann, so dass man die Berechnung abbricht, einen oder mehrere Schritte zurückgeht und dann erst  weiterrechnet (Backtracking). Die bekannteste  Verfahrensweise ist die sog. begrenzte Enumeration. Die  Anzahl möglicher Knoten für die Berechnung optimaler Graphen erhöht sich zwar, die Grenze ist aber auch hier bald erreicht. Schon gar nicht ist die begrenzte Enumeration eine generelle Lösung für optimale TSP.

Eingrenzung über den Ausschluss von Kanten: 
Eine andere Möglichkeit, die Menge der möglichen Graphen einzuschränken, besteht darin, einzelne Kanten für eine optimale Lösung auszuschließen.  Als Beispiel sei hier "Branch-and-Bound" genannt. Mit dieser Methode werden wesentlich bessere Ergebnisse erzielt als mit der begrenzten Enumeration. Der "Branch-and-Cut"-Algorithmus, mit dem man das bisher größte TSP optimal berechnet hat (Weltrekord), baut auf der Methode von Branch-and-Bound auf. 

Eingrenzung über Nebenbedingungen:
Einer der häufigsten Einschränkungen über Nebenbedingungen ist der Spezialfall des TSP im euklidischen Raum. Hier können von vornherein bestimmte Kanten aufgrund ihrer Lage ausgeschlossen werden. Neben Kanten die im Graph zu Überschneidungen des Weges führen gehören z.B. alle diejenigen Kanten mit Sicherheit nicht zum optimalen Graph, die Knoten auf der konvexen Hülle verbinden, soweit jene nicht benachbart sind.  

Eingrenzung über die Reduzierung der Ausgangsmenge:
Die ZIP-Methode geht einen anderen Weg. Durch die Zerlegung der Gesamtgraphen in 
zwei gleichstrukturierte Teilgraphen erreicht man eine Minimierung der Ausgangsmenge 
von Elementen. Können bekannte Verfahren nicht nur auf Gesamtgraphen sondern auch 
auf Teilgraphen angewandt werden, so bringt die ZIP-Methode den entscheidenden Quantensprung der rechentechnischen Vereinfachung.

(03.10.2005)