In dieser Arbeit geht es um die zentralen Inhalte des Traveling Salesman Problems. Dabei soll die Anwendung und Umsetzung des Traveling Salesman Problems in der Logistik betrachtet werden. Zentral geht es dabei darum, darzustellen, mit welchen Methoden und mathematischen Modellen auch komplexe Wegberechnungen und Optimierungen vor dem Hintergrund des Traveling Salesman Problems vorgenommen werden können
1 Einleitung
2 Grundlagen des Traveling Saleman Problems
2.1 Definition und Beschreibung
2.2 Anwendung in der Logistik
2.3 Zusatzbedingungen in der Logistik
3 Das Traveling Salesman Problem vor dem Hintergrund mathematischer Berechnungen
3.1 Das Traveling Salesman Problem als mathematisches Problem
3.2 Mathematische Überlegungen zum Traveling Salesman Problem
3.3 Grafische Modellierung
3.4 Das asymmetrische, symmetrische und metrische Traveling Salesman Problem
3.4.1 Asymmetrie
3.4.2 Symmetrie
3.4.3 Metrik
3.5 Lineare, ganzzahlige Darstellung
4 Approximative Lösungsverfahren für das Traveling Salesman Problem
4.1 Branch-and-Cut-Methode
4.2 Post-Optimization-Verfahren
4.3 Näherungsverfahren
4.3.1 Neighbor-Heuristik
4.3.2 Insertion-Heuristik
4.3.3 Christofides-Heuristik
5 Zusammenfassung
5.1 Grenzen des Traveling Salesman Problems
5.2 Erweiterungen
Literaturverzeichnis
1 Einleitung
Bei dem Traveling Salesman Problem handelt es sich um ein mathematisches Optimierungskonzept, dessen sprechende Bezeichnung bereits darauf verweist, wo das Problem eingesetzt werden kann. Da das Traveling Salesman Problem aus der Praxis eines reisenden Handelsvertreters entstanden ist, liegt es nahe, es auch für konkrete Anwendungen im Zusammenhang mit Warenflüssen und Handelstätigkeiten zu nutzen. Zahlreiche Anwendung findet das Traveling Salesman Problem daher in der Logistik. Aber auch im Vertrieb spielt die Optimierung des Traveling Salesman Problem eine große Rolle. Die vielfach gerade vor dem Hintergrund von Kostenerwägungen in der Logistik notwendige Optimierung der Wegstrecken stellt eine wichtige Grundbedingung für die Anwendung des Traveling Salesman Problems in der Logistik dar. Unter Berücksichtigung zahlreicher Faktoren, die relevant für die Wegstrecken, kann das Traveling Salesman Problem als Werkzeug eingesetzt werden, um eine optimale Lösung zu finden. Diese damit verbundenen Überlegungen und Ansätze sind eine der am häufigsten untersuchte Problematik in der rechnergestützen Mathematik.1
In dieser Arbeit geht es um die zentralen Inhalte des Traveling Salesman Problems. Dabei soll die Anwendung und Umsetzung des Traveling Salesman Problems in der Logistik betrachtet werden. Zentral geht es dabei darum, darzustellen, mit welchen Methoden und mathematischen Modellen auch komplexe Wegberechungen und Optimierungen vor dem Hintergrund des Traveling Salesman Problems vorgenommen werden können.
2 Grundlagen des Traveling Saleman Problems
2.1 Definition und Beschreibung
Bei dem Traveling Salesman Problem handelt es sich um ein sehr abstraktes, mathematisches Problem. Es lässt sich grundlegend folgendermaßen beschreiben: Ein Handlungsreisender besucht eine bestimmte Anzahl von Kunden und möchte nach dem letzten Besuch eines Kunden an seinen Ausgangsort zurückkehren. Das Traveling Salesman Problem betrifft nun den vom Handlungsreisenden zurückzulegenden Weg, bei dem die zurückzulegende Entfernung so gering wie möglich ist.2
Im einfachsten Fall wird von vier Kunden oder Punkten ausgegangen, die besucht werden müssen. Der Einfachheit halber wird in der Literatur hier oft von den mathematischen Punkten A, B, C und D gesprochen. Diese Punkte können sowohl Kunden als auch Speditionen oder andere Objekte sein, die in der Logistik eine Rolle spielen. Zwischen den Punkten bestehen Routen. Einige Routen sind realisierbar und werden in eine Optimierung einbezogen. Andere, theoretisch denkbare Routen müssen komplett ausgeschlossen werden und werden deshalb auch nicht in die Optimierung einbezogen. Das kann fachliche Gründe besitzen wie zum Beispiel eine durch die Beladung eingeschränkte Reihenfolge. Daneben kann es auch einfache geografische oder mathematische Gründe wie eine sehr weite Entfernung zwischen zwei Punkten haben. Eine mathematische Abstraktion eines Traveling Salesman Problems könnte wie folgt aussehen:
Abbildung in dieser Leseprobe nicht enthalten
Dabei handelt es sich um ein stark vereinfachtes Problem, das jedoch gut geeignet ist, um unterschiedliche Lösungsmöglichkeiten zu diskutieren.
Bereits vor vielen Jahrhunderten und sogar schon vor Jahrtausenden gab es Reisende, die Waren auf einem Teil der Welt einkauften, um sie in anderen Teilen der Welt wieder zu verkaufen. Von globalen Handelswegen bis hin zu regionalen Strukturen gibt es auch schon in der frühen Geschichte zahlreiche Beispiele. Bereits 1832 existierte das erste Handbuch für den Handlungsreisenden, das jedoch noch nicht mathematisch unterlegt war. Der australische Mathematiker Karl Menger schrieb Überlegungen zum „Postmann-Problem“ auf und war somit der erste, der das Traveling Salesman Problem in mathematischer Weise beschrieb.3 Fortan gab es zahlreiche Veröffentlichungen, die das Traveling Salesman Problem theoretisch behandelten. Viele Optimierungsalgorithmen, die im Laufe der Zeit entwickelt wurden, wurden anhand des Traveling Salesman Problems eingeführt und an der Lösung dieses Problems getestet.
Das Traveling Saleman Problem entstand zwar im Umfeld des Vertriebsmanagements, kann aber in vielen anderen Anwendungsbereichen, wie zum Beispiel der Logistik, ebenfalls herangezogen werden. Das Traveling Salesman Problem ist innerhalb der Mathematik den Optimierungsverfahren zuzuordnen. Diese Verfahren ermöglichen es, einem klar definierten Problem eine optimale Lösung zuzuordnen. Wie diese Lösung erreicht wird und wie die Randbedingungen definiert werden, hängt vom jeweiligen Verfahren ab. Die meisten Optimierungsverfahren beginnen mit einer zufällig kontruierten Anfangslösung. Einige Verfahren berechnen in den Folgeschritten die Lösungen nach einem deterministischen Schema, andere involvieren auch in den Folgeschritten Zufallsmechanismen.4
2.2 Anwendung in der Logistik
Die Logistik zielt auf die Systematisierung der Objektflüsse im Wertschöpfungszusammenhang im Sinne einer rationalen Optimierung der betrieblichen Ergebnisse.5 Vor diesem Hintergrund erfolgt ein „Management von Prozessen und Potenzialen zur koordinierten Realisierung unternehmensweiter und unternehmensübergreifender Materialflüsse und der dazu gehörigen Informationsflüsse (Prozessmanagement der Wertschöpfungskette)“.6 Die damit verbundene außerordentliche Komplexität der Umsetzung von Ressourcen impliziert im optimalen Fall ein Höchstmaß an Effizienz und eine Zuverlässigkeit der Warenverteilung, was in einem Logistikunternehmen mit LKWs, Zügen oder Schiffscontainern erfolgt. Wird im Unternehmen nun ein LKW mit Waren für verschiedene Kunden an verschiedenen Orten beladen, so muss für diesen LKW eine möglichst optimale Route unter Berücksichtigung von diversen Randbedingungen festgelegt werden, damit alle Waren kostengünstig, zuverlässig und effizient an die entsprechenden Kunden ausgeliefert werden können. Das Traveling Salesman hat mit ebendieser Gestaltung eines optimalen und effizienten Transportweges zu tun, betrifft aber immer nur ein Transportmittel, das auf einer mehr oder weniger vorgegebenen Route eine einzelne Tour fährt. Die Tourenplanung in der Logistik bezieht allerdings noch viele andere Faktoren mit ein, wie zum Beispiel die Verteilung der Waren auf verschiedene Transportmittel. Insofern kann die Optimierung der Reihenfolge der innerhalb einer Tour zu besuchenden Knoten und damit das Traveling Salesman Problem als ein Unterproblem des Tourenplanungsproblems aufgefasst werden.7 Vor diesem Hintergrund stellt die Optimierung des Traveling Salesman Problems einen entscheidenden Wettbewerbsvorteil dar. Vor allem in der Potentialanalyse eines Logistikunternehmens bietet sich eine regelmäßig durchgeführte Optimierung des Traveling Salesman Problems an, um eventuelle Schwachstellen oder dauerhafte Fehler aufzudecken und beheben zu können.
2.3 Zusatzbedingungen in der Logistik
Die Optimierung einer einzelnen Tour kann also direkt vor dem Hintergrund es Traveling Salesman Problems vorgenommen werden. Während es bei der eigentlichen Formulierung des Problems um einen einzelnen Vertriebsmitarbeiter geht, der eine gewisse Anzahl von Kunden an verschiedenen Orten besucht, um dort mit seinen Kunden zu sprechen und Geschäfte zu vereinbaren, geht es in der Logistik darum, Waren zu verteilen. Die Rahmenbedingungen, die auf die Logistik zutreffen, unterscheiden sich daher etwas von den Grundbedingungen des Traveling Salesman Problems. Ein wichtiger Faktor des ursprünglichen Problems ist die Länge der Route. Diese kann sowohl bei einem Vertriebsmitarbeiter als auch auf einer Logistiktour von wenigen Kilometern in einer großen Stadt bis zu Touren von internationalen Größenordnungen schwanken. Während bei einem Vertriebsmitarbeiter jedoch Faktoren wie Unterbringungskosten eine Rolle spielen, sind es bei Logistikunternehmen andere Faktoren. So ist zum Beispiel die Ladekapazität eine Randbedingung in der Logistik, die das Traveling Salesman Problem massiv beeinflusst. Denn die Beladung eines LKWs ist physikalisch begrenzt. Das Ladegewicht muss ausgeglichen sein. So können mögliche Reihenfolgen für die Belieferung bereits vorgeschrieben beziehungsweise ausgeschlossen sein. Doch auch andere Faktoren sind bei der Optimierung nach dem Traveling Salesman Problem zu berücksichtigen. Es müssen Termine eingehalten werden, wann die Fahrzeuge frühestens/spätestens an den einzelnen Orten einzutreffen/abzufahren haben. Die Be- und Entladezeiten und die gesetzlichen Bestimmungen über die Einsatzzeiten der Fahrer sind zu berücksichtigen.8 Die Möglichkeiten für die Touren nach dem Traveling Salesman Problem in der Logistik sind also deutlich eingeschränkter als im Vertriebsmanagement. Dabei ist bei der Formulierung der Definition und der Anfangslösung Rücksicht zu nehmen.
3 Das Traveling Salesman Problem vor dem Hintergrund mathematischer Berechnungen
3.1 Das Traveling Salesman Problem als mathematisches Problem
Um das Traveling Salesman Problem optimal mathematisch lösen zu können, bedarf es einer klaren, mathematisch haltbaren Definition des Problems. Zunächst wird deshalb das Problem selbst semantisch auf ein Minimum reduziert. Da der Name „Traveling Salesman Problem“ sprechend ist und sozusagen selbst erklärt, worum es in dem Problem eigentlich geht, ist er auch in der Mathematik erhalten geblieben, wird jedoch mit „TSP“ abgekürzt. Damit ist das gesamte Problem gemeint, das durch eine konkrete Fragestellung spezifiziert wird. Dazu gehören zum Beispiel die sogenannten Knoten. Die Knoten bezeichnen im ursprünglichen Traveling Salesman Problem die Orte, die ein Vertriebsmitarbeiter besuchen kann. Es gibt also eine Knotenanzahl n, die die Anzahl der zu besuchenden Orte repräsentiert. Diese Knoten werden mit Zählvariablen i und j identifiziert. Zwischen zwei Orten i und j ergibt sich eine sogenannte Kante. Jede Kante hat eine definierte Länge c(ij), die immer größer als 0 ist. Von einem Knoten i ergeben sich also nur Kanten zu anderen Knoten, aber nicht zu sich selbst.
[...]
1 Vgl. Applegate et al. 2011, S. 1.
2 Vgl. Domschke/Scholl 2010, S. 95.
3 Vgl. Simon 2013, S. 451.
4 Vgl. Gerdes/Klawonn/Kruse 2004, S. 15.
5 Vgl. Grün/Jammernegg/Kummer;2009, S. 257.
6 Grün/Jammernegg/Kummer;2009, S. 257.
7 Vgl. Vahrenkamp/Kotzab 2012, S. 456.
8 Vgl. Albers/Zottmann 1980, S. 69.