Traveling Salesman Problem

Das Travelling-Salesman-Problem, Problem des Handlungsreisenden, Rundfahrtproblem, Rundreiseproblem, Reihenfolgeproblem, ist ein Problem des Operations Research, bei dem die optimale Reihenfolge von Orten oder Maschinen zu bestimmen ist, bei der die insgesamt entstehenden Kilometer, Zeiten oder Kosten ein Minimum ergeben. Das Problem verdankt seinen Namen dem Problem der Bestimmung der optimalen Rundfahrt eines Reisenden, der n Orte einmal zu besuchen hat und am Ende der Fahrt wieder an seinen Ausgangsort zurückkehren muß. Es ist ein Problem der Ablaufplanung oder Reihenfolgeplanung, das heute bei der Planung des Produktionsprozesses eine Rolle spielt. Es kann durch Näherungsverfahren gelöst werden.

Das Traveling Salesman-Problem (TSP) ist eines der klassischen Optimierungsprobleme. Es lässt sich wie folgt anhand eines Graphen beschreiben: Ein Handelsvertreter möchte, beginnend in seinem Heimatort (Knoten 1), n – 1 weitere Kundenorte (Knoten 2,...,n) in einer zu ermittelnden Reihenfolge besuchen und anschließend zum Ausgangspunkt zurückkehren. Dabei soll die insgesamt zurückgelegte Entfernung minimal sein. Im Graph ist also ein Zyklus (Rundreise) mit minimaler Länge gesucht, der alle Knoten genau einmal enthält. Das TSP (in gerichteten Graphen) lässt sich mit Hilfe von binären Variablen xij, die den Wert 1 annehmen, wenn Pfeil (i,j) im Zyklus liegt, und ansonsten 0 sind, wie in der nächsten Spalte dargestellt formulieren. Die ersten beiden Mengen von Nebenbedingungen garantieren, dass jeder Ort genau einmal erreicht und genau einmal verlassen wird. Die als Kurzzyklusbedingungen angegebenen und nicht ausformulierten Nebenbedingungen gewährleisten, dass die zu bestimmende Rundreise alle Knoten des Graphen enthält. Insbesondere ist zu verhindern, dass Kurzzyklen mit weniger als n Knoten entstehen. Der Kurzzyklus mit den Knoten 1, 2 und 3 wird z.B. durch ausgeschlossen. Insgesamt ist eine große Anzahl solcher Bedingungen zu formulieren, um alle denkbaren Kurzzyklen zu vermeiden. Zur Lösung des TSP existieren vielfältige exakte und heuristische Verfahren. Erstere sind v.a. B&B-Verfahren. Bei letzteren gibt es Eröffnungsverfahren (z.B. Nächster Nachbar, Cheapest Insertion) und Verbesserungsverfahren (z.B. r-opt), die häufig auch mit Meta-Heuristiken kombiniert werden.

Das auch als Rundreiseproblem oder Problem des Handlungsreisenden bezeichnete Travelling Salesman Problem beschreibt eine Planungssituation (Planung), in der ein strecken bzw. transportkostenminimaler Weg gesucht wird, der eine vorgegebene Menge von Orten, die genau einmal anzufahren sind, enthält und einen geschlossenen Zyklus darstellt. Dieses Planungsproblem findet sich in erster Linie im Speditionsbereich (siehe auch Logistik), aber auch beispielsweise im Zusammenhang mit der Festlegung der Reihenfolge der anzufahrenden Kunden im Rahmen eines Direktvertriebs, wie er von einigen Tiefkühlketten durchgeführt wird. Zur Lösung dieses Problems, das als ganzzahliges lineares Optimierungsproblem grundsätzlich gut strukturiert, bzgl. der Lösbarkeit aber äußerst komplex ist, hat sich für kleine Problemstellungen die Branch & Bound Methode bewährt; bei realitätsnäheren Problemgrößen sind eher Heuristiken oder neuere Ansätze wie beispielsweise evolutionäre Algorithmen oder lokale Verbesserungsverfahren (z. B. Simulated Annealing, Tabu Search) einzusetzen (siehe auch Operations Research).

Standardmodelltyp der kombinatorischen Optimierung. Es geht dabei um die Bestimmung des kürzesten Rundreiseweges von einem Ausgangsort durch eine vorgegebene Menge von Orten zurück zum Ausgangsort (Tourenplanung). Vom gleichen Typ sind Reihenfolgeprobleme der Fertigung, wenn die Produktwechselkosten von der Produktfolge abhängen, etwa bei Färbeprozessen. Zur Lösung des Travelling-Salesman-Problems sind sowohl Entscheidungsbaumverfahren, und zwar Branch and Bound, begrenzte Enumeration und dynamische Optimierung, als auch heuristische Verfahren vorgeschlagen worden. Die hierfür entwickelten Rechenverfahren bilden die Grundlage für die Lösung anderer Reihenfolgeprobleme.

Literatur: Müller-Merbach, H., Optimale Reihenfolgen, Berlin u. a. 1970. Pearl, J., Heuristics, Reading, Mass. 1984.

Siehe auch Transportplanung.

Vorhergehender Fachbegriff: Tratte | Nächster Fachbegriff: Traveling Salesman-Probleme

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Kommanditaktionär | Umsatzsteuerreform | Lombard

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer