Einführung in die Graphentheorie und das Traveling-Salesman-Problem
Vom anschaulichen Rundreiseproblem bis zur Komplexitätstheorie – ein kompakter Einstieg in eines der bekanntesten Optimierungsprobleme der Informatik.
Einführung
Das Traveling-Salesman-Problem (auch: Rundreiseproblem, kurz TSP) gehört zu den kombinatorischen Optimierungsproblemen. Es handelt sich um ein Rundreiseproblem, bei dem mehrere Orte unter Minimierung der Reisezeit oder der Kosten nacheinander angesteuert werden sollen. Dabei darf jeder Ort nur einmal besucht werden. Die Reihenfolge ist nicht von Bedeutung. Das TSP ist daher ein anschauliches Optimierungsproblem aus der Tourenplanung.
Anwendungsgebiete
Logistik & Routenplanung
Lieferdienste wie UPS oder DHL nutzen TSP-Ansätze, um alle Stationen anzufahren und Kosten zu minimieren.
Telekommunikation
Effiziente Verbindungen zwischen Knotenpunkten in Glasfaser- und Mobilfunknetzen planen.
Mikrochips
Optimierung der Verkabelung in VLSI-Schaltkreisen für bessere Leistung und Energieeffizienz.
Tourismus
Reiseplattformen berechnen optimale Rundreisen durch mehrere Städte oder Sehenswürdigkeiten.
Was ist ein Graph?
Ein Graph in der Informatik unterscheidet sich grundlegend vom mathematischen Verständnis eines Graphen als Darstellung von Funktionen. Die Definition gemäß der Graphentheorie lautet:
Ein Graph besteht also aus Knoten (den zu besuchenden Orten) und Kanten (den Straßen). Nicht jeder Knoten muss verbunden sein (isolierter Knoten), aber eine Kante kann nicht „ins Nichts" führen. Zusätzlich sind positive Distanzen zwischen allen Knoten gegeben. Ziel ist die Bestimmung einer Besuchsreihenfolge mit minimaler Gesamtdistanz.
Was ist das TSP?
Beim TSP hat man einen Graphen mit n Städten als Knoten und Kanten zwischen jedem Städtepaar. Ein Händler startet in einer Stadt, besucht alle Städte genau einmal und kehrt zum Startpunkt zurück. Diese Route soll so kurz wie möglich sein.
Beispiel
Die Suche nach dem kürzesten Weg vom Startknoten A kann dazu verleiten, immer den Knoten mit der kleinsten Entfernung zu wählen. Dies könnte zum Weg ABDCA führen – die Kante von C nach A ist mit 15 gewichtet, wodurch der Weg eine Gesamtlänge von 24 hat.
Wählt man bei Knoten B die Kante nach C (Gewicht 6), umgeht man die Kante von C nach A und kommt mit der Route ABCDA auf eine Länge von 21 – in diesem Fall von A aus der kürzeste Weg.
Vorgehensweise: Adjazenzmatrix (ADM)
Eine Adjazenzmatrix (auch Nachbarschaftsmatrix) eines Graphen speichert, welche Knoten durch eine Kante verbunden sind. Sie besitzt für jeden Knoten eine Zeile und eine Spalte – für n Knoten ergibt sich eine n × n-Matrix. Auf den obigen Graphen angewendet:
Vorgehensweise: Baumgraph aus der ADM
Der Baumgraph lässt sich leicht aus der Adjazenzmatrix ableiten:
Das Ziel des TSP auf Baumgraphen besteht darin, die kürzeste Rundreise durch den Baum zu finden, die alle Städte besucht und am Ausgangspunkt endet. Das TSP auf Baumgraphen ist in der Regel einfacher zu lösen als das allgemeine TSP, da der Baum spezielle strukturelle Eigenschaften hat.
Schwierigkeiten beim TSP
Die Fragestellung wirkt einfach, doch die Antwort ist deutlich schwieriger. Naive Strategien:
- Immer die Kante mit der kleinsten Gewichtung wählen – Problem: man erreicht nicht zwingend alle Knoten und läuft Gefahr, einen doppelt zu besuchen.
- Immer zum nächsten noch nicht besuchten Knoten mit der geringsten Entfernung – Problem: durch diese Wahl können später Kanten mit sehr großer Gewichtung entstehen, wodurch der Weg dennoch länger ist.
Zwei Lösungsansätze
- Exakte Algorithmen – eine optimale Lösung wird für jedes Problembeispiel konstruiert; mathematisch bewiesen, dass sie den kürzesten Weg liefert.
- Heuristiken – so schnell wie möglich wird eine zulässige Lösung gefunden, die nicht zwingend optimal ist, aber nahe herankommt.
Eine Methode wäre ein exakter Algorithmus: Man berechnet alle Wege und ihre Länge – der kürzeste Weg gewinnt. Problem: Bei wachsender Knotenzahl nimmt die Berechnung kein Ende. Bei n Städten, die jeweils genau einmal besucht werden müssen, gibt es (n − 1)! mögliche Rundreisen mit beliebigem Startpunkt.
Heuristik: Nächster Nachbar
Im Kontext des TSP ist eine Heuristik eine Methode oder Regel, um schneller eine annähernd gute Lösung zu finden – ohne die Gewissheit, dass sie optimal ist. Angewendet auf unseren Baumgraphen:
In diesem Beispiel gibt es (n − 1)! = (4 − 1)! = 6 mögliche Rundreisen. Das ist überschaubar – doch mit wachsendem n steigt die Anzahl exponentiell.
Wachstum der Rundreisen
Die Anzahl möglicher Rundreisen wächst mit (n − 1)!:
| n | (n − 1)! | Berechnung | Ergebnis |
|---|---|---|---|
| 4 | 3! | 3 · 2 · 1 | 6 |
| 5 | 4! | 4 · 3 · 2 · 1 | 24 |
| 6 | 5! | 5 · 4 · 3 · 2 · 1 | 120 |
| 7 | 6! | 6 · 5 · 4 · 3 · 2 · 1 | 720 |
Ein möglicher Algorithmus
Einfach gesagt: Man geht immer zum nächstgelegenen, noch nicht besuchten Knoten und kehrt am Ende zum Start zurück. Diese Methode ist nicht ideal – sie liefert nicht immer den kürzesten Weg.
Das TSP und der Solver in Excel
Der Excel Solver kann beim TSP verwendet werden, um eine optimale Route zu finden, bei der ein Vertriebsmitarbeiter alle Städte genau einmal besucht und am Startpunkt zurückkehrt.
Vorgehen
- Datenaufbereitung: Entfernungen zwischen allen Städten in einer Matrix eingeben.
- Entscheidungsvariablen: Der Solver entscheidet über die Reihenfolge der Städte.
- Zielsetzung: Minimierung der Gesamtstrecke entlang der Route.
- Einschränkungen: Jeder Punkt genau einmal, Route endet am Ausgangspunkt.
Der Solver berechnet dann die optimale Route mit minimaler Gesamtreise.
Lernvideo: Excel Solver für das TSP