Lösungsverfahren für das 2-dimensionale, euklidische Traveling Salesman Problem unter besonderer Berücksichtigung der Delaunay-Triangulation

Silvia Annette Schiemann

ISBN 978-3-8325-0795-4
644 Seiten, Erscheinungsjahr: 2005
Preis: 40.50 €

Die vorliegende Untersuchung beschäftigt sich mit dem NP-vollständigen, symmetrischen Traveling Salesman Problem (TSP) unter Zugrundelegung euklidischer Distanzmessung. Nach einer Einführung in exakte und heuristische Lösungsverfahren wird untersucht, inwieweit bei einer Einschränkung auf aussichtsreiche Kanten die Optimallösung gefunden werden kann. Durch Einschränkung der zulässigen Kanten sind erhebliche Rechenzeiteinsparungen möglich. Besonders aussichtsreich für das Auffinden optimaler Touren ist die Delaunay-Triangulation, die im weiteren untersucht wird.

Nach der Konstruktion einer Reihe von zufällig gebildeten euklidischen Testinstanzen mit Umfang von bis zu 90 Städten (n=90) werden die tatsächliche Optimallösung und die beste Lösung innerhalb der Delaunay-Triangulation miteinander verglichen. Zur Erstellung der Lösungen wird ein Branch & Bound-Verfahren eingesetzt, welches eigens für eingeschränkte Kantenauswahl modifiziert wird. Für alle zufällig gebildeten Instanzen können innerhalb der Delaunay-Triangulation sehr gute Lösungen gefunden werden: In der Mehrzahl der Testinstanzen wird das Optimum erreicht, die anderen gefunden Touren übersteigen das tatsächliche Optimum um maximal 3%. Die Rechenzeit reduziert sich im Schnitt um das 30-fache. Bei den untersuchten TSP-Instanzen gehören ca. 98% der Kanten der Optimallösung auch zur Delaunay-Triangulation.