Diese Seite geht auf einige Details und theoretische Hintergründe des LRP Programms ein. Für weitere Informationen gerne über kontakt@fysn9.de nachfragen.
Location-Routing-Problem
Das Location-Routing-Problem, kurz LRP, oder auf deutsch Standort-Routen-Problem befasst sich mit der kombinierten Standort- und Routenplanung.
Standortplanung beschreibt auf strategischer Ebene die Wahl einer oder mehrerer Standorte aus einer Menge von möglichen Standorten, um möglichst kostengünstig eine Menge von Kunden zu bedienen. Wenn etwa ein Backwarenproduzent ganz viele Produktionsstätten (~Standort) über seine Region verteilt, dann hat er meist kürzere Wege zu seinen Verkaufsfilialen (~Kunden) und spart so Lieferkosten – umgekehrt erzeugt jede Produktionsstätte allerdings Fixkosten. Hier ist also die Entscheidung aus eröffneten Standorten und erzeugten Fahrtkosten zu optimieren.
Routenplanung beschreibt auf eher taktischer Ebene die Reihenfolge, in welcher Kunden, die bereits einem Standort zugewiesen wurden, bedient werden, und soll die dabei erzeugten Fahrtkosten minimieren. In unserem Beispiel möchte der Backwarenproduzent seine täglichen Belieferungen der vielen Filialen möglichst schnell oder mit kürzester Wegstrecke bewältigen.
Eine Kombination der beiden Probleme erlaubt eine langfristig günstigere Erfüllung der Lieferaufgabe.
Stochastischer Bedarf
Das Standard-LRP geht davon aus, dass der exakte Bedarf aller Kunden bei der Tourenplanung bekannt ist. Im Beispiel unseres Backwarenproduzenten könnte es aber sein, dass unterschiedliche Filialen schwankenden Bedarf an Backwaren haben. Der Bedarf von Brezen könnte höher ausfallen, als ursprünglich geplant. Dieser erhöhte Bedarf wird aber erst bekannt, wenn das Lieferfahrzeug bei der Filiale ankommt. Nun könnte zunächst der erhöhte Bedarf einer Filiale bedient werden, das Fahrzeug hat anschließend weniger Brezen für die nächste Filiale als ursprünglich geplant. Wenn wir aber annehmen, dass wir alle Brezenbedarfe befriedigen wollen, müsste das Fahrzeug, bevor es zur nächsten Filiale fahren kann, zurück zur Produktionsstätte (~Standort), um die Brezen aufzufüllen. Dieser Umweg ist aber aufgrund der zusätzlichen Fahrtstrecke recht teuer. Entsprechend ist es sinnvoll, solche stochastischen (Brezel-)Bedarfe frühzeitig zu berücksichtigen, etwa indem mehr Standorte näher an den Filialen oder kürzere Touren mit mehr (Brezel-)Puffer eingeplant werden.
Hinweis: Stochastischer Bedarf wird derzeit NICHT in der hier veröffentlichten Testversion berücksichtigt.
Simulated Iterated Local Search
Das LRP ist ein sogenanntes np-schweres Problem, was im Wesentlichen heißt, dass es ziemlich schwer ist, eine garantiert optimale Lösung zu finden. Daher werden in wissenschaftlicher Literatur häufig Metaheuristiken herangezogen, um LRP zu lösen. Eine solche Metaheuristik ist die Simulated Iterated Local Search (SimILS) von Quintero-Araujo, Guimarans und Juan (2021). Diese Metaheuristik ist der wesentliche Treiber zur Bestimmung der hier erzeugten Lösungen.