Die vorliegende Untersuchung beschaftigt sich mit dem NP-vollstandigen, symmetrischen Traveling Salesman Problem (TSP) unter Zugrundelegung euklidischer Distanzmessung. Nach einer Einfuhrung in exakte und heuristische Losungsverfahren wird untersucht, inwieweit bei einer Einschrankung auf aussichtsreiche Kanten die Optimallosung gefunden werden kann. Durch Einschrankung der zulassigen Kanten sind erhebliche Rechenzeiteinsparungen moglich. Besonders aussichtsreich fur das Auffinden optimaler Touren ist die Delaunay-Triangulation, die im weiteren untersucht wird. Nach der Konstruktion einer Reihe von zufallig gebildeten euklidischen Testinstanzen mit Umfang von bis zu 90 Stadten (n=90) werden die tatsachliche Optimallosung und die beste Losung innerhalb der Delaunay-Triangulation miteinander verglichen. Zur Erstellung der Losungen wird ein Branch & Bound-Verfahren eingesetzt, welches eigens fur eingeschrankte Kantenauswahl modifiziert wird. Fur alle zufallig gebildeten Instanzen konnen innerhalb der Delaunay-Triangulation sehr gute Losungen gefunden In der Mehrzahl der Testinstanzen wird das Optimum erreicht, die anderen gefunden Touren ubersteigen das tatsachliche Optimum um maximal 3%. Die Rechenzeit reduziert sich im Schnitt um das 30-fache. Bei den untersuchten TSP-Instanzen gehoren ca. 98% der Kanten der Optimallosung auch zur Delaunay-Triangulation.
