Logistik: Transport 1 - Grundlagen, lineare Transport und Umladeprobleme.

Die Bände zur Logistik beinhalten Problemformulierungen und Lösungsverfahren für die Transport-, Rundreise-, Touren- und Standortplanung. Sie sollen Studierende der Wirtschafts- und Ingenieurwissenschaften an quantitative Methoden zur Lösung logistischer Probleme heranführen. Er/sie soll lernen, Modelle so zu formulieren und Daten so aufzubereiten, dass sie den Anforderungen eines verfügbaren Verfahrens (bzw. Computer-Programmes) genügen.

Er/sie soll ferner dazu angeregt werden, einfachere Verfahren selbst möglichst effizient zu programmieren. Zu jedem der beschriebenen Verfahren wird ein Beispiel gerechnet. Die Aufgaben am Ende jedes Kapitels sind so angelegt, dass sie in der Regel einen kleinen Schritt über den behandelten Stoff hinausführen. Dem Praktiker und dem OR-Fachmann wird neben bewährten, klassischen Verfahren der neueste Stand der Forschung bei der Lösung der betrachteten Probleme vermittelt.

Das Buch richtet sich an Studierende der Wirtschafts- und Ingenieurwissenschaften.

Kapitel 2: Modellierungen und Lösungsprinzipien (S. 31-32)

In den weiteren Kapiteln dieses Bandes sowie in Teilen der Bände II und III beschäftigen wir uns mit Problemen, die man als Netzwerkkonstruktionsprobleme bezeichnen kann. In diesem Band handelt es sich um Probleme der Bestimmung minimaler spannender Bäume von Graphen, um Kürzeste-Wege-Probleme sowie um lineare Transport-, Umlade- und Maximalflussprobleme. In Band II sind dies z.B. binäre lineare, nichtlineare und Bottleneck-Transportprobleme, in Band III Standortprobleme in Netzen, so genannte Warehouse Location- oder Facility Location - Probleme.

Als Netzwerkkonstruktionsprobleme kann man sie bezeichnen, weil – ausgehend von einem potentiellen Netzwerk oder Digraphen G – jeweils ein Teilgraph mit bestimmten Eigenschaften, z.B. ein minimaler spannender Baum, ein Baum kürzester Wege oder ein Baum einer zulässigen Basislösung, gesucht wird.

Als Lösungsmöglichkeiten bieten sich v.a. für Transport- und Umladeprobleme unterschiedliche Vorgehensweisen an. Dabei handelt es sich einerseits um primale, primal-duale oder duale Verfahren der linearen Optimierung und andererseits um graphentheoretische Methoden zur Lösung der Probleme als q-s-Flussprobleme oder Zirkulationsflussprobleme. Wir wollen beide Typen von Vorgehensweisen etwas näher charakterisieren.

LP-Verfahren (LP abgeleitet von linearer Programmierung) oder Simplex-Verfahren: Hierbei handelt es sich um Spezialisierungen des primalen oder des dualen Simplex-Algorithmus. Als wichtigstes Merkmal wollen wir hervorheben, dass die mit Hilfe dieser Verfahren ermittelte optimale Lösung stets eine Basislösung des betrachteten Problems ist. Primale LPVerfahren für Transport- und Umladeprobleme beschreiben wir in den Kapiteln 5 und 6, eine primal-duale Vorgehensweise für Transportprobleme findet man in Kap. 5.2.3.3.

Graphentheoretische Verfahren: Hierzu zählen v.a. Inkrementgraphen-Algorithmen zur Lösung von q-s-Flussproblemen (siehe Kap. 8) sowie der Out-of-Kilter-Algorithmus von Fulkerson (1961) zur Lösung von Zirkulationsflussproblemen (siehe Kap. 9.2.1). Der Out-of- Kilter-Algorithmus ist ein primal-duales Verfahren, das sich von den LP-Verfahren dadurch unterscheidet, dass es nicht in jedem Falle (für jede Probleminstanz) eine Basislösung liefert. In Kap. 2.1 beschreiben wir zunächst ein allgemeines Netzwerkkonstruktionsproblem und leiten die meisten der später behandelten Spezialprobleme daraus ab. Zugleich geben wir mathematische Formulierungen an, die bei der Lösung der Probleme mit Hilfe von Vorgehensweisen der linearen Optimierung zugrunde liegen.

In Kap. 2.2 definieren wir, was man unter einem q-s- und einem Zirkulationsflussproblem versteht. Ferner formulieren wir Transport- und Umladeprobleme als q-s-Fluss- bzw. Zirkulationsflussprobleme.

Zum Abschluss geben wir in Kap. 2.3 wichtige Sätze der linearen Optimierung an und skizzieren das Prinzip primaler, primal-dualer und dualer Vorgehensweisen. Zu ausführlicheren Darstellungen von Methoden der linearen Optimierung verweisen wir z.B. auf Dantzig und Thapa (1997), Hillier und Lieberman (1997) oder Domschke und Drexl (2007).

2.1 Problembeschreibungen
Wie eingangs angekündigt, betrachten wir zunächst ein allgemeines Netzwerkkonstruktionsproblem. Innerhalb des Graphen oder Netzwerks soll der Transport eines homogenen Gutes (bzw. mehrerer Güter, die hinsichtlich ihrer Transportmöglichkeiten wie ein einheitliches Gut – z.B. Stückgut – behandelt werden können) erfolgen.1 Daraus leiten wir viele der in den drei Logistikbüchern betrachteten Probleme als Teilprobleme ab. Wir geben mathematische und für Transport- und Umladeprobleme auch die dazu dualen Formulierungen an.