SPEZIALGEBIETE
LOGISTIK

GRAPHEN, DISTANZEN,
KÜRZESTE WEGE

Allgemein

  • Heuristik vs. optimale Verfahren
  • euklidische, Manhattan-Distanz
    ad Heuristik: Geschwindigkeit, Lösungsgüte, Flexibilität, Einfachheit

Min. spannender Baum
=> Kruskal
kürzeste Kante ohne Zyklus zu erzeugen

Kürzeste Wege

VEHICLE ROUTING PROBLEM

Problem des Maximalen Flusses

  • ausgehende und eingehende Flüsse
  • Strecke suchen - geht nach min. möglicher Kapazität

Dijkstra
kürzeste Wege ev. über mehrere Knoten
kürzer als der direkte Weg

Tripelalgorithmus

  • Distanz- & Vorgängermatrix
  • je Knoten 1 Iteration = n Iterationen
  • Distanz & Vorgänger anpassen, wenn Verbesserung

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

TSP (Traveling
Salesman Problem)

Ungarische Methode (Vorbereitung für Probleme)

  • zur Lösung eines linearen Zuordnungsproblems
  1. Zeilenmin. abziehen
  2. Spaltenmin. nach Schritt 1 abziehen
  3. je Zeile und Spalte 1 Null auswählen => fertig
  4. so wenig Zeilen und Spalten wie möglich streichen
  5. Min. aller nicht gestrichenen Zahlen suchen und neue Tabelle:
    • einfach gestrichene Zahlen unverändert übernehmen
    • doppelt gestr. Zahlen um das Min. erhöhen
    • nicht gestrichene Zahlen um das Min. verringern
  6. weiter bei Punkt 3.
    Ziel: Matrix mit je 1 0er je Kunde

Heuristik von Christofides

  1. Min. spannenden Baum ermitteln
  2. Knoten mit ungeradem Grad zu einem Graph ZF & Zuordnungsproblem lösen; erhaltene Kanten zum Baum hinzufügen (ggf. verdoppeln)
  3. beliebige Rundreise im Graph wählen, sodass jeder Knoten 1 x besucht wird

Heuristik von Karp

  1. lin. Zuordnungsproblem lösen
  2. Hamiltonscher Zyklus? => fertig
  3. beiden größte Kurzzyklen kostenmin. verknüpfen
  4. Hamiltonscher Zyklus? => fertig, sonst 3. Schritt

Sweep-Algorithmus
cluster first - route second

  1. eukl. Distanzen zwischen Kunden
  2. Kunden nach ansteigendem Polar-Winkel sortieren
  3. mit Kunde 1 beginnen; nächste Kunden bis Kapazität Q hinzufügen
  4. exakte Lösung des TSP, wenn Tour voll ist
  5. 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?

  1. für jeden Kunden eine Pendel-Tour bilden
  2. Strecken zum Depot > Strecke zwischen Kunden => Ersparnis, in Matrix eintragen
  3. 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.
  1. Berechnung der Kosten je Kunden für Clusterzuweisung
  2. Kundenzuweisung: zu Seed mit geringeren Kosten im Vgl. (c01 + c13 + c30) - (c03 + c30) => abzgl. Kosten vom Seed
  3. Routing: für jeden Cluster ein TSP lösen

ROUTE FIRST - CLUSTER SECOND


Giant-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

  1. viele zulässige Touren bilden (inkl. Nebenbedingungen) - auf Basis Nearest Neighbor, Sweep ...)
  2. 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

  1. Regel, nach der die Lösung verändert wird
  2. Anwenden (first fit/best fit)
  3. 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

  1. Zyklus durch unbesuchte Kanten bilden
  2. nicht besuchte Kanten an 1. anschließen (neuen Zyklus bilden)
  3. bis alle Kanten besucht wurden

Briefträger-Probleme

UPP
exakte Lösung des UPP; ungerichtete Kanten

  1. Knoten mit ungeradem Grad bestimmen
  2. vollständigen Graph bilden
  3. optimales Matching dafür (Ungar. Methode)
  4. jede Kante aller gewählten kürzesten Wege eine Kopie hinzufügen
  5. Euler-Tour bilden

DPP

  1. ausgehend - eingehend > 0: Spalte (Lieferant)
    ausgehend - eingehend < 0: Zeile (Kunde)
  2. z. B. Spaltenmin. zur Lsg. nehmen
  3. Pfeil auf dem kürzesten Weg von i nach j hinzufügen
  4. Euler-Tour

Fredericksons Heuristik

  1. min. Spannbaum
  2. Knoten mit ungeradem Grad => Matching-Problem lösen
  3. augm. Graphen aus Kanten des orig. Graphen erstellen
  4. Euler-Tour

EXAKT: Branch & Bound
mittels des Verfahrens von Little et al.

  1. Zeilenmin. aufsummieren & abziehen, dann Spaltenmin. aufsummieren => Summe aus beidem = untere Schranke
  2. Summe von nächstkleinster Zahl in Zeile & Spalte
  3. Max. aus 2. sind zus. Kosten, wenn die Kante verboten wird => x42 = 0
    x42 = 1 => Matrix exkl. 4 und 2 schreiben, x24 auf unendlich setzen (Rücktour verbieten) + zus. Kosten dazuzählen (Min. aus Zeile, + dann Spalte)
  4. min. Zweig wählen und weitermachen

Carpaneto & Toth

  1. untere Schranke: mittels. Ungar. Methode exakt lösen
  2. kürzesten Zyklus: Kante unendlich setzen & ungar. Methode anwenden