Übung 5: Transportplanung (Erklärung & Beispielaufgaben)

Methoden ermöglichen Unternehmen, ihre Transport- und Logistiknetzwerke effizient zu planen und zu optimieren, um kostengünstig oder schnelle Wege zur Warenbewegung zu identifizieren.

• Graph: Besteht aus Knoten und Kanten. Kanten (Transportwege) gerichtet (von einem Knoten zu einem anderen) oder ungerichtet (einfach eine Verbindung zwischen zwei Knoten ohne Richtung).

  • Kantengewichte: Kosten, Entfernung oder Dauer des Transports über einer Kante

  • Verwendung von Graphen zur vereinfachten Abbildung realer Netzwerke

Graphentheorie:

1. Zusammenhängender Graph: Graph, wenn es zwischen jedem Paar von Knoten einen Pfad gibt. Das bedeutet, dass es keine isolierten Knoten gibt und jeder Knoten über Kanten mit jedem anderen Knoten verbunden ist.

1. Baum: ist ein zusammenhängender Graph, der keine Kreise enthält. Es gibt keine geschlossenen Pfade in einem Baum. Ein Baum mit n Knoten hat immer genau n−1 Kanten.

2. Spannbaum: Spannbaum eines Graphen ist ein Teilgraph, der ein Baum ist und alle Knoten des ursprünglichen Graphen enthält.

3. Wald: enthält keine Kreise und besteht aus einer oder mehreren unabhängigen Bäumen.

Kürzeste Wege in gerichteten Graphen:

• Dijkstra-Algorithmus: Kürzeste Entfernung und Wege zwischen einem Startknoten 𝒂 und allen anderen Knoten

• Tripel-Algorithmus: Kürzeste Entfernung und Wege zwischen jedem Knotenpaar eines Graphen

Minimaler Spannbaum:

• Kruskal-Algorithmus: Konstruktion eines Spannbaums ohne Verzweigungen mit minimalem Gewicht

Gegeben:

• Ein Digraph mit Knoten und Bewertungen 𝑐𝑖𝑗 ≥ 0 für alle Pfeile

• 𝐷: Kürzeste Entfernungen vom Startknoten zum Knoten

• 𝑅: Vorgänger auf dem kürzesten Weg zum Knoten

• 𝑀𝐾 ≔ Menge markierter Knoten

Gesucht:

• Kürzeste Entfernung und Wege zwischen einem Startknoten 𝒂 und allen anderen Knoten

Anwendungen:

• Routenplanung für physische Produkte (ohne zusammengelegte Touren)

• Routing von Datenpaketen in Internetprotokollen (z. B. Open Shortest Path First)

Gegeben sei folgender gerichteter gewichteter Graph:

1. Initialisierung:

   • A: 0

   • B: ∞

   • C: ∞

   • D: ∞

   • E: ∞

   • F: ∞

2. Für jeden benachbarten Knoten von A:

   • B: Entfernung von A nach B = 10

   • D: Entfernung von A nach D = 2

   Aktualisiere die Distanz:

   • B: 10

   • D: 2

3. Markiere A als besucht.

4. Wähle Knoten mit der kleinsten Distanz, das ist D.

5. Für jeden benachbarten Knoten von D:

   • B: Entfernung von D nach B = 1

   • E: Entfernung von D nach E = 1

6. Da alle Knoten besucht wurden, ist der Algorithmus abgeschlossen.

Nach Abschluss des Algorithmus sind die kürzesten Wege vom Startknoten A zu allen anderen Knoten wie folgt:

• A -> B: 3

• A -> C: 11

• A -> D: 2

• A -> E: 3

• A -> F: 5

• 1962 von Robert Floyd und Stephen Warshall entwickelt

• Floyd beschäftigte sich mit den minimalen Distanzen und Warshall mit der optimalen Wegführung.

• Findet die kürzesten Pfade zwischen allen Paaren von Knoten eines Graphen und berechnet deren Länge (APSP, allpairs shortest path).

• Iteratives Vorgehen durch Aufnahme zusätzlicher Knoten und damit Zulassen von indirekten Wegen zwischen den Knoten

• Es wird untersucht, ob bei Aufnahme des Knotens 𝑗 für ein Tripel 𝑖,𝑗, 𝑘 der Weg von 𝑖 nach 𝑗 und anschließend von 𝑗 nach 𝑘 kleiner ist als der direkte Weg von 𝑖 zu 𝑘

• Basiert auf dem Optimalitätsprinzip von Bellman (1957): Wenn der kürzeste Weg von 𝑖 nach 𝑘 über 𝑗 führt, muss auch der Teilpfad von 𝑖 nach 𝑗 der kürzeste Weg von 𝑖 nach 𝑗 sein.

• Laufzeit: 𝒪 𝑉 3)

Gegeben:

• Verkehrsnetz, das durch einen gemischten Graphen beschrieben wird:

  • Kanten: beide Richtungen befahrbar

  • Pfeile: Einbahnstraßen

  • Knoten: Straßenkreuzungen

• Die Bewertung der Kanten und Pfeile entspricht der Länge der Straßen.

Gesucht:

• Getränkefirma beabsichtigt, an derjenigen Straßenkreuzung ein Auslieferlager einzurichten, von der aus die Summe der Entfernungen zu allen übrigen Kreuzungen am kleinsten ist

Initialisierung:

• Wenn es eine direkte Verbindung (Kante) zwischen zwei Knoten gibt, wird das Kantengewicht 𝑑𝑖𝑗 in einer Distanzmatrix 𝐷 eingetragen

• Falls es keine direkte Verbindung gibt, ist ∞ einzutragen.

• Direkte Vorgänger auf dem kürzesten Weg werden in einer Vorgängermatrix 𝑃 eingetragen.

𝑑𝑖𝑗 ≔ Distanz vom Knoten 𝑖 zum Knoten j

Danach werden nacheinander alle Knoten 𝑘 = 1, … , 𝑛 als Zwischenstationen zugelassen. Ist der Weg über die Zwischenstation 𝑘 kürzer als der bisher eingetragene, wird der neue Weg eingetragen.

Auswahl (für Standortplanung):

• Ausgewählt wird der Knoten, der in der letzten Matrix die kleinste (Zeilen-)Summe der Entfernungen hat.

• Die Getränkefirma sollte ihr Auslieferungslager am Standort 3 errichten (Gesamtdistanz 14).