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 heißt "Berechnung mit Fakultät" und bedeutet, 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.

Die eben erwähnten Standardlösungsverfahren sollen hier nicht tiefgehend erläutert, aber einige kurz beschrieben werden. Allen gemeinsam ist, dass sie

• mit realistischem Rechenaufwand lösbar sind
• die Lösungen durchschnittlich in der Nähe des Optimums liegen (also suboptimal sind!)
• sie sind problembezogen aber in gewissen Grenzen allgemeingültig, sie sind keineswegs als genereller "Speziallösungsweg" zu sehen.
• Zielsetzung ist Satifizierung, nicht Optimierung - es reicht eine Lösung die besser ist als der aktuelle Zustand
• unvollständige oder ungenaue Daten führen zu Fehlern die größer sind als die Verfahrensfehler. - soll heißen: ein solches Verfahren kann (nicht muss) unter Umständen eine Lösung liefern die 90%ig optimal ist. Ungenaue Daten liefern aber eventuell nur Lösungen die zu 60% optimal sind.