Traveling Salesman Problem

In der Routenplanung ist man mit Problemen unterschiedlicher Art konfrontiert. Dazu gehört auch das vieldiskutierte Problem des Handlungsreisenden (Travelling-Salesman). Es geht dabei darum, die Reihenfolge für den Besuch mehrerer Orte so zu optimieren, dass der Gesamtreiseweg nach Rückkehr zum Ausgangsort möglichst kurz ist. Insbesondere wenn nicht euklidische Distanzen, sondern Zeit oder Kosten als Grundlage für die Routenberechnung dienen sollen, wird die Berechnung mittels einfacher Methoden erschwert (Haggett et al. 1977).

Hinweis: Insbesondere im Zusammenhang mit der Routenoptimierung bei der Planung von Lieferrouten spricht man auch vom Vehicle Routing Problem, welches weitere Kriterien der Planung von Lieferungsplanung beinhaltet.

Diese Unit geht einführend auf das Problem des Handlungsreisenden ein, führt unterschiedliche Szenarien auf, welche insbesondere im Sinne des Vehicle Routings die Vielschichtigkeit des Problems demonstrieren und stellt die verschiedenen Ansätze vor, die zur Lösung des Problems herangezogen werden können. Dazu gehören (Bott et al. 1986):

• Exakte Lösungsverfahren
• Heuristische Lösungsverfahren
• Interaktive Lösungsverfahren
• Kombinierte Lösungsverfahren