The Travelling Salesman

Der Begriff "Travelling Salesman" beschreibt in der wirtschaftsmathematischen Disziplin ein klassisches lineares Optimierungsproblem. Dabei sei einem reisenden Vertreter die Aufgabe gestellt, eine Anzahl geographisch verstreuter Orte so aufzusuchen, dass jeder Ort besucht und die Wegstrecke insgesamt minimiert wird.

Da die Orte beim Travelling Salesman Problem nicht in einer Reihe liegen, sind mehrere Reiserouten denkbar. Mit steigender Anzahl Orte steigt die Anzahl möglicher Reiserouten und damit Komplexität des Problems exponentiell an. Im einfachsten Fall (d.h. ausschließlich Direktverbindungen zwischen den Orten) bleiben dem Reisenden an jedem besuchten Ort noch diejenigen Orte übrig, an denen er bisher nicht war. Bei fünf Orten sind 5! = 5 * 4 * 3 * 2 * 1 = 120 Touren möglich, bei 10 Orten schon 10! = 3.628.800, also weit mehr als die doppelte Anzahl. Das Ausrufezeichen steht für den mathematischen Operator "Fakultät"; die zugehörige Rechenanweisung ist oben dargelegt. Im Normalfall (d.h. nicht nur Direktverbindungen) werden zum Abarbeiten aller Orte viele Wege mehrfach gefahren werden müssen. 

Für die Wissenschaft ist an dem Problem spannend, dass es nicht über eine Formel aufzulösen ist; es existiert kein geschlossener Lösungsalgorithmus. Stattdessen kann die optimale Lösung, also die kürzeste Wegstrecke, nur versuchsweise ermittelt werden.

An diesen Travelling Salesman fühlte ich mich heute erinnert. Am Arbeitsplatz (Ort A) hatte ich eine Wartezeit zu überbrücken, die ich für ein paar Besorgungen nutzen wollte. Beim Teilehändler (B) warteten zwei 20 L-Kanister Getriebeöl darauf, in die Werkstatt (C) gebracht zu werden. Davon konnte ich nur jeweils einen pro Fahrt auf dem Rad transportieren. Zuhause (D) befand sich ein Kanister mit Altöl für den Teilehändler. Außerdem eine Jacke, die ins Büro sollte und eine Dose Altlack für das nur heute im Dörfli anwesende Schadstoffmobil (E).

Ich hätte vom Arbeitsplatz aus direkt zum Teilehändler fahren können oder nach Hause. Von zu Hause aus wären der Teilehändler, die Werkstatt und das Schadstoffmobil unmittelbar zu erreichen gewesen. Alle Strecken sind ungefähr gleich lang. Das Optimierungsproblem lautete folglich: In welcher Reihenfolge wären alle Besorgungen zu erledigen, unter der Nebenbedingung, die Abwesenheitszeit (=Wegstrecke) zu minimieren?

Bei der Lösung des Problems half mir der im Studium erworbene Optimierungsfetisch wenig. Richtig war im nachhinein, zuerst nach Hause zu fahren, denn dort stand der Paketdienst mit den Kalendern vor der Tür. Der Teilehändler hatte dann zwar Ware, aber keinen Preis für mein Öl. Um kein Drittes Mal zum Bezahlen hinfahren zu müssen, holte ich heute nur einen Kanister Getriebeöl ab. Schließlich entschied ich mich dafür, den Altlack aufzubewahren, falls wir ihn mal bräuchten.

Und die Moral von der Geschicht? In der Praxis hilft ein Studium nicht!

Euer Christian aka Oschi

Mehr zum Thema Travelling Salesman?

-> Pah, ein alter Hut. Gib mir mehr! -> klick

-> Alter, was willst Du von mir? -> klick



Kommentar schreiben

Kommentare: 0