Das Problem des Handlungsreisenden
Das Problem des Handlungsreisenden
Ein Pflegedienst aus Saarlouis besucht jeden Morgen Patientinnen und Patienten in Dillingen, Lebach, Schwalbach und Völklingen und kommt danach zurück. Es ist Berufsverkehr – die Karte zeigt die Fahrzeiten in Minuten, die morgens gelten. Welche Reihenfolge ist am schnellsten? Dieses Problem heißt Problem des Handlungsreisenden (engl. Traveling Salesman Problem, TSP).
S = Saarlouis, D = Dillingen, L = Lebach, W = Schwalbach, V = Völklingen, P = Püttlingen
Merke
Eine Rundreise beginnt und endet am selben Ort und besucht jeden anderen Ort genau einmal. Jede Rundreise ist eine zulässige Lösung. Gesucht ist die optimale, also die kürzeste Rundreise.
Eine kleine Instanz untersuchen
An einem Tag besucht der Pflegedienst nur Dillingen, Schwalbach und Völklingen. Bei so wenigen Orten kann man alle Rundreisen aufschreiben.
S = Saarlouis, D = Dillingen, W = Schwalbach, V = Völklingen
Aufgabe 1: Hier stehen alle Rundreisen ab Saarlouis. Berechne für jede die Fahrzeit.
| Rundreise | Fahrzeit (Minuten) |
|---|---|
| S → D → W → V → S | |
| S → D → V → W → S | |
| S → W → D → V → S | |
| S → W → V → D → S | |
| S → V → D → W → S | |
| S → V → W → D → S |
Aufwand beim Handlungsreisenden
Mit jedem weiteren Ort wird die Zahl der Rundreisen mit der Zahl der Orte multipliziert. Ein Rechner, der eine Million Rundreisen pro Sekunde prüft, braucht:
| weitere Orte | Rundreisen | Zeit |
|---|---|---|
| 5 | 120 | sofort |
| 10 | 3 628 800 | etwa 4 Sekunden |
| 15 | etwa 1,3 Billionen | etwa 15 Tage |
| 20 | etwa 2,4 Trillionen | etwa 77 000 Jahre |
Die Symmetrie aus Aufgabe 2 halbiert diese Zahlen – bei 20 Orten bleiben aber immer noch über eine Trillion Rundreisen. Brute Force ist für echte Lieferrouten mit 100 Stopps aussichtslos.
Eine Heuristik: der nächste Nachbar
Greedy-Idee: Fahre von deinem aktuellen Ort immer zum nächstgelegenen noch nicht besuchten Ort. Sind alle besucht, fahre zurück zum Start.
Ab heute kommt eine Patientin in Püttlingen dazu.
Aufgabe 6: Die schnellste Tour durch alle sechs Orte dauert 77 Minuten. Vergleiche mit deinem Ergebnis aus Aufgabe 5. Nenne einen Vorteil und einen Nachteil des Nächster-Nachbar-Verfahrens.