Walter Schmitting: Das Traveling-Salesman-Problem - Anwendungen und heuristische Nutzung von Voronoi-/Delaunay-Strukturen zur Lösung euklidischer, zweidimensionaler Traveling-Salesman-Probleme

Das Traveling-Salesman-Problem (TSP; synonym Handlungsreisenden- oder Rundreiseproblem) ist eine der populärsten kombinatorischen Problemstellungen der letzten vier Jahrzehnte. In seiner illustrativsten Formulierung unterstellt es einen Handlungsreisenden, welcher durch eine geeignete Wahl der Reihenfolge der von ihm zu bereisenden Städte die Länge der zurückzulegenden Strecke minimieren soll. Der besondere Anreiz zur Beschäftigung mit dem TSP liegt dabei in der Tatsache begründet, daß das Problem nach dem derzeitigen Kenntnisstand der Mathematik als nicht effizient optimal lösbar gilt. Folglich müssen - insbesondere zur Bewältigung realer Anwendungsfälle - leistungsfähige Heuristiken herangezogen werden.

Die vorliegende Arbeit verfolgt zwei Anliegen: Zum ersten soll in Form einer reflektiv-kritischen Synopse ein vergleichender Überblick über die zahlreichen realen Erscheinungsformen des TSP gegeben werden. Die Lösung dieser in der Literatur bislang nicht bewältigten Aufgabe verlangt aufgrund der Vielzahl und Vielfalt praktisch relevanter TSP eine Auseinandersetzung mit zahlreichen Themenkontexten - von der Archäologie über die Röntgenkristallographie bis hin zum Flugzeugturbinenbau. Es können dabei auch zahlreiche Problemstellungen im ökonomisch relevanten Umfeld identifiziert werden (so z.B. Maschinenbelegungsprobleme, Tourenplanungsprobleme, Platinenbohrprobleme usw.). Allerdings resultiert aus der eingehenden Darstellung und Untersuchung von elf derartigen "Anwendungen" (und Skizzen zahlreicher weiterer) der Schluß, daß gerade in einer fachübergreifenden Betrachtung besonders fruchtbar Verwandtschaften und Beziehungen der einzelnen TSP-Anwendungen untereinander aufgezeigt werden können. Im Ergebnis wird festgestellt, daß hinsichtlich der Modellierung von realen Problemen als TSP noch zahlreiche theoretische und praktische Fragen als ungelöst gelten müssen.

Das zweite Anliegen der Arbeit ist es, Möglichkeiten zur heuristischen Lösung einer speziellen Instanz des TSP - des euklidischen, zweidimensionalen Typs - unter Berücksichtigung einer spezifischen räumlichen Strukturierung - den Voronoi-/Delaunay-Strukturen - weiterzuentwickeln bzw. neu zu entwickeln. Ein euklidisches, zweidimensionales TSP läßt sich als eine Schar von Punkten, folgend als "Städte" bezeichnet, in der Ebene auffassen. Die Distanz zweier Städte ergibt sich als die Länge einer Geraden von der einen zur anderen. Gesucht ist wiederum die kürzeste mögliche Rundreise durch sämtliche Städte. Die zugehörigen euklidischen, zweidimensionalen Voronoi-/Delaunay-Strukturen teilen eine gegebene Fläche aufgrund der Lage der Städte in jeweils denselben zuzuordnende polygonale Teilflächen ein und konstituieren damit natürliche Nachbarschaftsbeziehungen zwischen den Städten. Letztere können nun einerseits für eine erhebliche Beschleunigung von heuristischen Verfahren zur Lösung des euklidischen, zweidimensionalen TSP genutzt werden. Andererseits ermöglichen sie eine dezidiertere Steuerung der heuristischen Verfahren selbst und damit zugleich Steigerungen der erzielbaren Lösungsqualität. Die Arbeit geht zunächst den grundlegenden Beziehungen zwischen Voronoi-/Delaunay-Strukturen und dem euklidischen, zweidimensionalen TSP nach und vermag dabei bereits einen bislang unbekannten Zusammenhang aufzuzeigen. Sodann reflektiert sie bereits vorhandene Ansätze zur Nutzung von Voronoi-/Delaunay-Strukturen in der genannten Art und entwickelt anschließend unter Rückgriff auf bekannte Heuristiken neue Nutzungsmöglichkeiten. Dabei gilt die Aufmerksamkeit insbesondere einer erheblichen Verkürzung der von den Heuristiken benötigten Rechenzeit unter Wahrung der realisierbaren Lösungsqualitäten. Die vorgeschlagenen Heuristiken werden anhand von allgemein akzeptierten Testproblemen ausgiebig evaluiert. Somit können die prognostizierten Rechenzeitsenkungen auch empirisch nachgewiesen werden.

Als "Elektronische Dissertation" publiziert
von der Universitäts- und Landesbibliothek Düsseldorf;
Link zur Eintragungsseite der ULB Düsseldorf (neues Fenster)
Direkter Download (PDF in neuem Fenster, 3198 KB)

Schmitting, Münster 2000
ISBN 3-00-004089-7
Umfang 773 Seiten, 155 Abbildungen
als PDF-Datei auf CD; 20,-- Euro