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

Das Traveling Salesman Problem, zu Deutsch das Rundreiseproblem oder auch Problem des Handlungsreisenden, kurz TSP, beschäftigt sich, vereinfacht man es auf das Basisprinzip schlechthin, auf die Effizienz eines Weges zu einem festgelegten Ziel, der bestmöglichen Lö-sung einer Aufgabe. Dies kann in vielerlei anderen Sparten ebenso auftauchen, dabei sei das Beispiel etwa der Regulierung von tsp 1Ampelschaltungen und Vernetzungen genannt, das Erstel-len eines Schaltplanes u.a.

Das Problem wurde in der Mathematik 1930 zum ersten Mal aufgegriffen bzw genannt und im Anschluß machten sich viele Mathematiker daran, optimierte Lösungswege zu erstellen oder bestehende Lösungen zu verfeinern und zu verbessern. Es wurden neue Verfahren entwickelt, die, wie weiter oben erwähnt, auch auf andere Optimierungsprobleme angewandt wer-den und werden können.

Das Traveling Salesman Problem nimmt eben die Logik einer bestehenden Problematik bereits vorweg: Es gilt eine gestellte Aufgabe zu bewältigen – in diesem Fall eine Reise zu mehreren Knotenpunkten, und gebunden an die Rückkehr zum Ausgangspunkt, so effizient und optimiert wie nur möglich im Vorfeld zu gestalten. Dieses liegt zu Grunde. Als Basispunkte finden sich hier etwa verschiedene Städte/ Zielorte, die miteinander verbunden eine möglichst effektive Route ergeben sollen. Auf den ersten Blick wird hierbei die jeweilige Entfernung der einzelnen Punkte zu einander betrachtet und berechnet. So zum Beispiel liegen sechs Punkte vor: A, B, C, D, E und F. Dies bedeutet, es wird die jeweilig mögliche Strecke bzw Entfernung von jedem einzelnen Punkt zu jedem anderen gekennzeichnet, also von A nach B, von A nach F, von B nach D, von E nach C usw. Jede Eventualität wird bedacht.

Hieraus gilt es, eine Route zu berechnen und zu erstellen, die alle Punkte beinhaltet, zum Ausgangspunkt am Ende der Rundreise zurückführt (also eine Art geschlossenes System) und die optimalste Strecke beinhaltet. So einfach dies klingen, so kompliziert wird dies in der Umsetzung. Auf den ersten Blick sind natürlich die Distanzen zwischen jeweils zwei Punkten zu beachten und die kleinstmögliche Summe aus den einzelnen Distanzen zu errechnen. Da das TSP jedoch nicht nur dem Prinzip folgt „die kürzeste Verbindung zwischen zwei Punkten ist eine Gerade“, sondern bereits in der Anfangsberechnung diese Theorie nicht immer greifen kann, stellt sich bereits vorab die Frage, was den jeweils kürzesten Weg von etwa A nach B wirklich ausmacht.

Einige Überlegungen konnten bisher von Mathematikern in Gleichungen anschaulich gemacht werden und ebenso fixiert. Heutzutage dienen allerdings einige der entwickelten Standardme-thoden des TSP eher zur Erstellung neuer Formeln und Überlegungen, mit denen Optimie-rungsvorgänge für anderweitige Bereiche und Branchen entwickelt werden können und Um-setzung finden. Das ursprüngliche TSP dient insofern mittlerweile mehr als Basis oder ge-stellte Grundfrage einer Vielzahl von Anwendungsmöglichkeiten, auf der aufbauend neue Thesen, Theorien und Überlegungen angestellt werden.

So dienen als Faktoren in der mathematischen Berechnung folgende Eckdaten: Die Anzahl der Knoten, die Länge der jeweiligen Strecke, im mathematischen Kante genannt, zwischen zwei Punkten. Zur Vereinfachung wird als Schema in der Mathematik ein Graph aus den Eckdaten erstellt und dieser nach Bedarf mit potentiellen Daten vervollständigt dargestellt, um alle Daten mit einzubeziehen zu können. So können längere Strecken/ Kanten als Diago-nalen eingetragen werden, wodurch ein Dreieck (vgl. Dreiecksungleichung) entsteht, allein, um die Anschaulichkeit zu vervollständigen und alle möglichen Variablen zur Errechnung der zurückzulegenden Gesamtstrecke. Ein Hinzufügen zum Beispiel zwei weiterer Knoten hat also bei vorhergehenden sechs Knoten führt nun also zu weitaus mehr zu bedenkenden Variablen einer effizienten Routenplanung. Die Menge der Knotenpunktebestimmt insofern die Vielzahl an potentiellen Kanten und wiederum deren möglichen Varianten an Verknüpfungen in der Summe.

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 )

w

Verbinde mit %s