Please enable JavaScript.
Coggle requires JavaScript to display documents.
SPEZIALGEBIETE
LOGISTIK (VEHICLE ROUTING PROBLEM (Problem des Maximalen…
SPEZIALGEBIETE
LOGISTIK
GRAPHEN, DISTANZEN,
KÜRZESTE WEGE
Allgemein
- Heuristik vs. optimale Verfahren
- euklidische, Manhattan-Distanz
ad Heuristik: Geschwindigkeit, Lösungsgüte, Flexibilität, Einfachheit
-
Kürzeste Wege
-
Tripelalgorithmus
- Distanz- & Vorgängermatrix
- je Knoten 1 Iteration = n Iterationen
- Distanz & Vorgänger anpassen, wenn Verbesserung
VEHICLE ROUTING PROBLEM
Problem des Maximalen Flusses
- ausgehende und eingehende Flüsse
- Strecke suchen - geht nach min. möglicher Kapazität
VRP
- ein Depot, von dort aus startet und endet jede Tour
- alle Kunden sind bekannt, 1 Besuch je Kunde
- fixe Anzahl homogener Fahrzeuge
- Fahrzeuge haben max. Ladekapazität
- min. der Gesamtsumme der Entfernungen
=> Entscheidung der Zuteilung der Kunden (Clustering) & der Route (Routing)
Erweiterungen: Zeitfenster, mehrere Depots, Rückladungen
Sweep-Algorithmus
cluster first - route second
- eukl. Distanzen zwischen Kunden
- Kunden nach ansteigendem Polar-Winkel sortieren
- mit Kunde 1 beginnen; nächste Kunden bis Kapazität Q hinzufügen
- exakte Lösung des TSP, wenn Tour voll ist
- nächste Tour öffnen bis zur Kapazität Q usw.
Savings-Algorithmus
clustering & routing simultan
Wie viel wird gespart, wenn zwei Kunden auf einer gemeinsamen Tour beliefert werden im Vgl. zu separat?
- für jeden Kunden eine Pendel-Tour bilden
- Strecken zum Depot > Strecke zwischen Kunden => Ersparnis, in Matrix eintragen
- höchste Ersparnisse zuerst - diese Kunden miteinander kombinieren, wenn die Kunden die ersten oder letzten auf der Tour sind & Kapazitäts- & Tourenbeschr. dies zulassen
Fisher and Jaikumar
cluster first - route second
- jeder Kunde wird einem Seed zugeordnet, sodass Gesamtkosten min. sind und Kap.restriktionen berücksichtigt sind.
- Berechnung der Kosten je Kunden für Clusterzuweisung
- Kundenzuweisung: zu Seed mit geringeren Kosten im Vgl. (c01 + c13 + c30) - (c03 + c30) => abzgl. Kosten vom Seed
- Routing: für jeden Cluster ein TSP lösen
ROUTE FIRST - CLUSTER SECONDGiant-Tour
- eine einzige, große Tour bilden
- danach Kap.restriktionen beachten und Tour aufteilen
=> für Touren z. B. Dijkstra, Wagner-Whithin
Petal Heuristic
Idee aus Sweep-Algorithmus
- viele zulässige Touren bilden (inkl. Nebenbedingungen) - auf Basis Nearest Neighbor, Sweep ...)
- aus den generierten Touren ein optimales Set wählen (jeder Kunde muss 1 x besucht werden)
Lokale Suche für das VRP
- Lösung vorhanden (über Sweep, Savings, Fisher & Jaikumar etc. ermittelt)
- Qualität unbekannt - eher nicht gut => besser Lsg. finden
=> Vorgehensweise
- Regel, nach der die Lösung verändert wird
- Anwenden (first fit/best fit)
- Iterieren
=> intra-route vs. inter-route
- 2-opt (Sequenzlänge 2, 3, 4 usw. - max. n - 2)
- Cross: zwei Routen aufbrechen & vertauschen (A:1, B:0, A:2, B:0 bis max. Kap., dann A:1, B:1, A:1, B:2 usw.)
- 3-opt
-
ARC ROUTING PROBLEM
Motivation
- ganze Straßen befahren, nicht nur einzelne Kunden
- Straßenabschnitte als Einheit betrachten
- z. B. Müllabfuhr, Straßenreinigung, Schneeräumung, Post
Euler Tour
jede Kante eines Graphen wird einmal befahren
- ungerichteter Graph: jeder Knoten besitzt geraden Grad
- gerichtet: Anzahl ausgeh. = Anzahl eingeh. Knoten
- gemischt: ungerichtet ≥ | eingeh. - ausgeh. |
End-Pairing Algorithmus
- Zyklus durch unbesuchte Kanten bilden
- nicht besuchte Kanten an 1. anschließen (neuen Zyklus bilden)
- bis alle Kanten besucht wurden
Briefträger-Probleme
UPP
exakte Lösung des UPP; ungerichtete Kanten
- Knoten mit ungeradem Grad bestimmen
- vollständigen Graph bilden
- optimales Matching dafür (Ungar. Methode)
- jede Kante aller gewählten kürzesten Wege eine Kopie hinzufügen
- Euler-Tour bilden
DPP
- ausgehend - eingehend > 0: Spalte (Lieferant)
ausgehend - eingehend < 0: Zeile (Kunde)
- z. B. Spaltenmin. zur Lsg. nehmen
- Pfeil auf dem kürzesten Weg von i nach j hinzufügen
- Euler-Tour
Fredericksons Heuristik
- min. Spannbaum
- Knoten mit ungeradem Grad => Matching-Problem lösen
- augm. Graphen aus Kanten des orig. Graphen erstellen
- Euler-Tour