Benutzer:RVahrenkamp/Modellierung von Logistiknetzwerken
Für die Modellierung von Logistiknetzwerken in den globalen Lieferketten der See– und Luftfracht[1] sowie für die Versorgung von Haushalten auf der letzten Meile hat das Operations Research verschiedene Verfahren entwickelt basierend auf Problemstellungen aus der theoretischen Informatik. Neben den Algorithmen zur Standortwahl in Netzwerken (Median– und Center-Probleme) sind in Verkehrs-Netzwerken vier verschiedene Probleme zu unterscheiden:
- das kürzeste Wege Problem,
- das Travelling Salesman Problem,
- das Tourenplanungsproblem und
- das Transportproblem
Diese Problemstellungen sind durchaus unterschiedlich und haben wenig miteinander zu tun. Lediglich das Tourenplanungsproblem kann implizit auf dem Travelling Salesman Problem aufbauen. Während das Operations Research die Modelle zur Verfügung stellte, waren empirische Forschungen zum Verkehr Gegenstand der Verkehrswissenschaften, aber nicht des Operations Research.
Probleme
[Bearbeiten | Quelltext bearbeiten]Kürzeste Wege Problem
[Bearbeiten | Quelltext bearbeiten]
Das Kürzeste-Wege-Problem sucht in einem Netzwerk den kürzesten Weg von A nach B. Der niederländische Informatiker Edsger W. Dijkstra entwickelte 1959 dieses Problem[2] und fand den ersten einfachen und schnellen Algorithmus (den Dijkstra-Algorithmus), der mit wenigen Zeilen Code programmiert werden kann. 1968 wurde von Peter Hart, Nils J. Nilsson und Bertram Raphael erstmals der A*-Algorithmus beschrieben, welcher als Verallgemeinerung und Erweiterung des Dijkstra-Algorithmus gilt. Im Gegensatz zu uninformierten Suchalgorithmen verwendet der A*-Algorithmus eine Schätzfunktion (Heuristik), um zielgerichtet zu suchen und damit die Laufzeit zeu verringern.[3] Man kann durch Millionen von Knoten augenblicklich den kürzesten Weg bestimmen, was heute in Routenplanern verwendet wird.
Travelling Salesman Problem
[Bearbeiten | Quelltext bearbeiten]Das Handlungsreisenden Problem oder das Travelling Salesman Problem (TSP) ist ein kombinatorisches Optimierungsproblem und sucht eine geschlossene Rundreise durch alle vorgegebenen Knoten mit der kleinsten Summe der zurückgelegten Entfernungen unter allen alternativen Routen. Man unterscheidet zwischen optimalen Lösungen und relativen Approximationen mittels heuristischer Verfahren, welche schneller Ergebnisse liefern, die um einen konstanten Faktor oberhalb der optimalen (kürzesten) Tour liegen können. Folgt man Herbert Simons Ansatz der beschränkten Rationalität, was Daten und Berechnungsleistungen anbelangt,[4] so spricht dieser Ansatz eher für Heuristiken zur Lösung des TSP, zumal Verkehrsdaten wegen temporärer Baustellen und Unfällen einen großen Unsicherheitsbereich aufweisen.
Tourenplanungsproblem
[Bearbeiten | Quelltext bearbeiten]Beim Tourenplanungsproblem plant man, wie in einer Stadt ein Lastkraftwagen von einem Großhandels-Stützpunkt aus verschiedene Läden beliefert. Als Restriktion ist zu bedenken, dass die Auslieferungs-Fahrzeuge keine großen mittelschweren 18-Tonnen-Lkw oder gar schwere 40-Tonnen-Lkw sind, sondern kleine wendige 7,5-Tonnen– oder 12-Tonnen-Lkw, die auch in der Innenstadt gut manövrieren und in enge Hofeinfahrten hineinfahren können. Dieser kleinere Lkw-Typ bedeutet aber, dass die Ladefläche des Lkw so klein ist, dass nur Bestellungen für 5 – 10 Läden transportiert werden können und pro Tour also nur 5 – 10 Läden angefahren werden können. (Dasselbe ist der Fall bei Auslieferungs-Touren von Stückgut-Speditionen). Wegen des hier erkennbar kleinen Dimensionsumfangs des Travelling Salesman Problem kann man es sehr gut mit einfachen Methoden heuristisch lösen, wenn das Liefergebiet auf das Straßennetz der Stadt projiziert wird. Hier gibt es nicht viele verschiedene Möglichkeiten, eine Tour abzufahren aufgrund der Gegebenheiten des Straßennetzes. Man kann also mit einfachen heuristischen Methoden Auslieferungs-Touren von 5 – 10 Läden im Stadtgebiet zusammenstellen. Auch bei Auslieferungsfahrten von Paketdiensten können einfach Algorithmen verwendet werden. Die Auslieferungsfahrten haben pro Tour zirka 100 Stopps, die straßenweise von Haus zu Haus abgefahren werden. Daher können hier einfache Algorithmen, zum Beispiel basierend auf der Nearest-Neighbor-Heuristik oder metaheuristische Verfahren, angewendet werden.
Transportproblem
[Bearbeiten | Quelltext bearbeiten]Das Transportproblem sucht nach einem kostenminimalen Plan der Lieferungen von Anbietern zu Nachfragenden und kann durch linearen Optimierung gelöst werden.
Anwendung
[Bearbeiten | Quelltext bearbeiten]Die Anwendung von Software zur Tourenplanung konnte sich nur langsam durchsetzen. Im Jahre 1990 wunderte sich Lewis Bodin über den geringe Anwendungsgrad dieser Software, obwohl doch bereits 20 Jahre lang die wissenschaftliche Gemeinde über Tourenplanung geforscht hätte.[5] Erst ab den 1980er Jahren waren mit ca. 300 Kilobyte die Hauptspeicher der in den Unternehmen in der BRD verfügbaren Digitalcomputer groß genug, um Tourenplanungssoftware, wie zum Beispiel das Paket TRAFFIC von Siemens, anwenden zu können. Vor allem in den Vertriebsorganisationen der kapitalstarken Unternehmen in der Getränkeindustrie und der Milchverarbeitung wurde diese Software eingesetzt, um Gaststätten und Einzelhandelsläden in Städten zu beliefern. In der BRD traten bei der Tourenplanung Probleme mit der Abstraktifizierung auf. Die von den Lieferfahrzeugen versorgten Läden wollten in den wiederkehrenden Touren stets vom gleichen Fahrer bedient werden – ein Wunsch, den die Tourenplanungssoftware nicht berücksichtigte. Auch gab es Probleme, Läden mit unterschiedlichen Belieferungsrhythmen in eine gemeinsame Tour aufzunehmen.[6] In den Tourenplanungspaketen wurde die eigentliche Tourenplanung wesentlich erweitert zu einem LKW-Flottenmanagementsystem, das Abrechnungen über Touren, Fahrzeugkosten und Personaleinsatz umfasste. Hohe Lizenzkosten der Softwarehersteller behinderten allerdings eine breite Anwendung bis in die 1990er Jahre.[7] Die vorsichtige Geschäftsstrategie der Softwarehäuser basierte im Wesentlichen auf Eigenkapital und nicht auf Venture Capital, das erst ab dem Jahr 2000 mit hohen Anfangsverlusten Märkte durch Niedrigpreise erobern konnte.
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ Vahrenkamp, Richard: Globale Luftfrachtnetzwerke – Laufzeiten und Struktur, erweiterte Neuauflage, Igel Verlag, Hamburg 2014.
- ↑ Edsger Dijkstra: A note on two problems in connexion with graphs, in: Numerische Mathematik. 1, 1959, S. 269–271.
- ↑ Tim Zeitz, Dorothea Wagner: Algorithmen für Routenplanung. 4. Mai 2020, abgerufen am 9. April 2021.
- ↑ Herbert Simon: Theories of decision making in economics and behavioural science. In: American Economic Review. Vol. 49, No. 3, 1959, S. 253–283.
- ↑ Bodin, Lewis: Twenty Years of Routing and Scheduling, in: Operations Research, 38 (1990), Heft 4, S. 571–579.
- ↑ Lück, Wolfgang: Logistik und Materialwirtschaft, Berlin 1984, S. 437–473. Zum Problem des gleichen Fahrers siehe ebd., S. 458.
- ↑ Vahrenkamp, Richard: Markstudie Tourenplanungssoftware, in: Deutsche Verkehrszeitung vom 17. Oktober 2006.
Kategorie:Modellierung und Simulation Kategorie:Transportproblem