Das Problem des Handlungsreisenden – ein bißchen was zum Wahnsinnigwerden für zwischendurch

So zeichnet sich mehr und mehr die Komplexität des Traveling Salesman Problems ab. Basie-rend auf dem Grundprinzip von herangezogenen Knoten und Kanten bedarf es der exakten Berechnung und Auslotung des Gesamten also auch Berücksichtigung wenn möglich aller Variablen, die, je nach Anforderung, zu bedenken sind.

Die Frage, ob eine Anwendung zum Beispiel des metrischen TSP zum Tragen kommen sollte, stellt sich etwa, wenn ein Umweg zwar eine größere Distanz in Kauf genommen werden muß, aber der Zeitrahmen eine sehr gewichtige Rolle spielt und sich etwa eine zwar größere Ent-fernung in verhältnismäßig kürzerer Zeit zurücklegen lassen würde, als würde man die direkte Strecke wählen.
Ebenso müssen etwa Zusatzfahrten möglicherweise zu Depots berücksichtigt werden, um die gesamte Anzahl an Kunden auch zu beliefern und diese bedürfen ebenso einer Einberechnung in die ursprünglich zu Grunde liegenden Daten und Routen.

Die bisher erstellten Varianten und Formeln zur Optimierung des Traveling Salesman Problem dienen einer Grundlage zur Berechnungen von sogenannten Unterkanten und –werten, die keinen oder kaum etwaigen zusätzlichen Variablen unterliegen. Insofern lassen sich diese Algorithmen heranziehen, um dem optimal bestmöglichen Ergebnis in der Theorie auch dann in der Praxis so nahe wie möglich zu kommen, indem diese Resultate als Fixpunkte herange-zogen werden können.

Zudem lassen sich auch Kombinationen verschiedener Verkehrsmittel anwenden, um Distan-zen und zeitlichen Aufwand zu verkürzen. Längere Strecken lassen sich mitunter mit Zugfahr-ten auf den zweiten Blick schneller bewältigen (dabei gilt es logistisch auch zu betrachten, was „Mitreisen“ muß, Ware zum Beispiel), da vielleicht ein Zurücklegen einer bestimmten Strecke mit dem Kraftfahrzeug einer enorm hohen Verkehrsdichte und Unfallgefahr unterliegt und somit Zeit kostet.

Dies gilt auch für Flüge. Insofern ist die Wahl der Reise-Variante eine ebenso gewichtige Va-riable. In einigen Fällen wird auch zu Sub-Optimierungen gegriffen, d.h. einzelne Bereiche werden nicht in der Gesamtheit der Route betrachtet, sondern diese wird in ihrer Gesamtheit gesplittet und in Unterpunkte gegliedert. Diese Untergliederungen werden nun jeweils einzelnen behandelt und optimiert.

Ist dies getätigt, wird aus den erstellten und optimierten Einzel-Fragmenten die Gesamt-Route zusammengestellt oder falls diese bereits vorab bestand überarbeitet anhand der neuen Resul-tate. Die Frage des Traveling Salesman Problem stellt sich nicht nur bei neuen Anforderungen oder jedem „Projekt“ neu, oftmals werden auch bestehende Strukturen und Routen, die bereits Umsetzung in der Praxis fanden, nochmals aufgegriffen und analysiert und gegebenfalls verfeinert oder auch komplett von Beginn an erstellt.
Eine allgemein gültige Lösung für das TSP gibt es nicht, da es zu vielen Variablen unterwor-fen ist bzw sein kann und scheinen manche auch noch derart verschwinden klein zu sein, können diese jedoch maßgeblich die praktische Umsetzung der Theorie und der Berechnung beeinflussen.

Allgemein kann davon ausgegangen werden, daß das Lösungsverfahren bezüglich des TPS eine Anzahl an Heuristiken heranzieht, hier seien zum einem das Eröffnungsverfahren genannt, das verschiedene mathematische Ansätze parat hält, das Verbesserungsverfahren, also eine Form der Nach-Optimierung, duale Heuristiken (hier lassen sich untere Schranken für die betreffende Tour anhand der Variablen errechnen und angeben) oder auch metaheuristische Verfahren, die nach dem Ausschlußverfahren gehen, um die optimalste Route und bzw das bestmöglichste Resultat unter Bezugnahme auf die Quellangaben zu erhalten.

Und? Nun richtig verwirrt? EV

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google Foto

Du kommentierst mit Deinem Google-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s