Zugriffe

Anzahl Beitragshäufigkeit
502657

Tourenplanung

 

Komplexitätsproblem

Viele Problemstellungen der Logistik zeichnen sich durch ihre Komplexität aus. Diese Grundeigenschaft ist auch in der Tourenplanung zu finden. Während es bei 2 Kundenstandorten noch recht einfach ist eine optimale Tour zu finden, sieht das Problem bei nur 6 Standorten schon ganz anders aus. Aber selbst diese 6 sind überschaubar, wenn man sich die riesigen Mengen vor Augen führt die ein Paket-Expressdienst täglich transportiert. Da die genaue Erläuterung der Komplexität viel zu weit führt, hier nur soviel:

Die genaue Anzahl aller möglichen Lösungen lässt sich mit folgender Formel berechnen.

Das Ausrufezeichen bedeutet "Berechnung mit Fakultät" und meint, dass der Multiplikator vorher mit allen kleineren natürlichen Zahlen und sich selbst multipliziert wird. So zum Beispiel: 6! = 1*2*3*4*5*6 = 720

 


Ein Gedankenspiel zeigt wie schnell das Problem der Tourenplanung unübersichtlich werden kann.

Es gibt einen zentralen Standort von dem aus die Bedarfe aller Kundenstandorte gedeckt werden sollen. Der Einfachheit halber soll gelten, dass ein Stopp den gesamten Bedarf des Kunden deckt. Jeder Kunde darf nur einmal angefahren werden. Start und Endpunkt ist immer das Lager, alle möglichen Kombinationen sind zulässig.

  • 2 Kunden (A+B) = 4 Tourenmöglichkeiten
    • Lager -> A -> Lager -> B -> Lager
    • Lager -> B -> Lager -> A -> Lager
    • Lager -> A -> B -> Lager
    • Lager -> B -> A -> Lager
  • 3 Kunden (A+B+C) = 42 Tourenmöglichkeiten
    • Lager -> A -> Lager ->B -> Lager -> C
    • Lager -> B -> Lager ->C -> Lager -> A
    • Lager -> C -> Lager ->A -> Lager -> B
    • Lager -> A -> B -> Lager -> C
    • Lager -> A -> C -> Lager -> B
    • Lager -> A -> B -> C -> Lager
    • Lager -> A -> C -> B -> Lager
    • Lager -> B -> A -> C -> Lager
    • Lager -> B -> C -> A -> Lager
    • Lager -> C -> A -> B -> Lager
    • Lager -> C -> B -> A -> Lager
    • etc.
  • 6 Kunden (A+B+C+D+E+F+G) = 45.630 Möglichkeiten (!!!)

Es ist keineswegs gesagt, dass jede dieser Lösungsmöglichkeiten sinnvoll ist. Sondern lediglich dass es sie gibt. Vom Lottoschein des letzten Wochenendes, der mal wieder nicht den Hauptgewinn gebracht hat,  wird ja auch niemand behaupten dass er sinnvoll war. Trotzdem hat man genau diese Kombination gewählt. Dort ist das Problem also sehr ähnlich. Die Aufgabe besteht nun darin mittels geeigneter Modelle die beste Lösungsoption aus allen vorhandenen Alternativen zu ermitteln. Dazu gibt es einige heuristische Lösungsansätze, die man durchaus als Standardverfahren ansehen kann.

 

kleiner Hinweis

Hinweise, Anregungen und vor allem Kritik - egal ob positiv oder negativ - sind immer willkommen und ausdrücklich erwünscht.

Beste Grüße aus Hamburg
Carsten Schmidt