ZAIK
Zentrum für Angewandte Informatik

Arbeitsgruppe Faigle/Schrader

Diese Arbeit wird vom Bundes-
ministerium für Bildung, Wissen-
schaft, Forschung und Technik (BMBF)unterstützt.

Weitere Informationen: Vehicle Routing

ZAIK / AFS
Universität zu Köln
Weyertal 80
50931 Köln

OptiLRV
 Optimale Linienführung und Routenplanung in Verkehrssystemen
 Zentrum für Paralleles Rechnen, Universität zu Köln, Prof.Dr.A.Bachem, Dipl.-Math.Anja Hamacher, Weyertal 80, 50931 Köln, Tel.:0221/470-6030, E-Mail: contact@zpr.uni-koeln.de

Plattformübergreifendes Dispositionssystem 		Projektpartner: Gerresheimer Glas AG

Ziel des Projektes OptiLRV ist die Entwicklung und Implementierung von kombinatorischen Verfahren zur zentralen Disposition von Transportaufträgen.
Behandelt wurden mehrere Teilproblematiken. Für Dispositionen im Verteilverkehr wurden Clusterverfahren entwickelt, da die regionale Begrenzung der Auslieferungsgebiete für jedes Fahrzeug oberstes Planungsziel war. Die Clusterung basiert auf einem exakten Verfahren zur Zerlegung von Bäumen unter Nebenbedingungen, die mit Hilfe von Knotengewichtsfunktionen formuliert werden. Weiterhin wurden die theoretischen Grundlagen sowie erste Heuristiken für Vehicle-Routing-
Probleme mit Umlademöglichkeit geschaffen. Komplettladungs-Transporte werden mit Hilfe eines Matchingansatzes gelöst. Für dieses Lösungsverfahren sind fest vorgegebenen Anlieferzeiten Voraussetzung.
Im Software-Engineering-Bereich wurde der Prototyp für ein plattformunabhängiges, fensterorientiertes Dispositionssystem implementiert.

Das Verteilproblem
Routenplanung mit mehreren Knotengewichtsfunktionen 		Gegeben:
  • ein Depot
  • maximale Fahrzeugkapazität
  • ein Zeitfenster pro Kunde
  • viele Probleminstanzen besitzen keine gültige Lösung
Gesucht:
 Tourenplan, für den gilt:
  • jeder Kunde wird von genau einem Fahrzeug beliefert
  • regional begrenzte Touren
  • kreuzungsfreie Touren
  • Zeitfensterverletzungen möglich bei
    1. Einverständnis des Kunden (telefonische Nachfrage)
    2. Entscheidung des Disponenten (umsatzabhängig)
Lösungsansatz:
  • Cluster first - Route second

Clusterung auf Basis des Minimal Aufspannenden Baumes
Clusterung

Baumzerlegungen unter Nebenbedingungen:

  • Bilde den Minimal Aufspannenden Baum auf der Kundenmenge
  • Bestimme Knotengewichte für jeden Knoten
    1. Bestellmenge
    2. km-Anteil an der Tour
    3. Kunde mit Vormit-
      tagszeitfenster (0=nein, 1 = ja)
    4. Kunde mit sehr engem Zeitfenster unter 3h (0=nein, 1 = ja)
    und deren Obergrenzen:
    1. Fahrzeugmaximal-
      kapazität
    2. Tourhöchstdauer
    3. max. Anzahl Vormittagskunden
    4. max. Anzahl Kunden mit engen Zeitfenstern
  • Zerlegung des MST unter den Nebenbedingungen wird mit Hilfe eines dynamischen Programmierungsansatzes exakt bestimmt

Dynamischer Programierungsschritt
3-Opt-Verbesserungsverfahren 		Routing

Ziel: In jedem Cluster möglichst viele Kunden in time beliefern

  1. Sortiere Stops nach: (a)Aufsteigender Zeitfensterdauer (b)Aufsteigendem Zeitfensterbeginn
  2. Bestimme Stops mit disjunkten Zeitfenstern (-> Routing in festgelegter Reihenfolge)
  3. Einfügen der Stops in sortierter Reihenfolge
    • Bestimme günstigste gültige Einfügeposition, falls möglich SONST:
    • Lösche einen der schon gerouteten Stops und füge den aktuellen Stop ein, falls Tour verbessert wird
    • Tourverbesserung durch speziellen 3-Opt, der die Reihenfolge innerhalb der Teiltouren nicht umkehrt
Ergebnisse

#Cluster km nicht verplant
n ex. gr. m. ex. gr. ex. gr.
914 39 42 47 16311 17479 58 55
818 34 34 46 15090 14599 50 51
910 40 42 48 17157 17604 59 51
848 36 38 46 15727 15699 62 61
973 48 54 48 18472 19620 68 47

  • Praxisdaten
  • Parameter-Tuning wichtig, um realistische Touren zu generieren
  • Restkunden werden manuell geplant
    • durch Zeitfensterverletzungen, evtl. bei schon verplanten Kunden
    • ohne neue Touren zu eröffnen
  • durchschnittlich 3 Fahrzeuge täglich eingespart
Komplettladungen
Probleminstanz:
 		Matchinglösung:
Ziel: Minimierung der Leerfahrten
  • Vorgegeben sind feste Anlieferzeitpunkte
  • Distanzen basieren auf zeitabhängigen kürzesten Wegen durch variierende Verkehrslage zu verschiedenen Tageszeiten
  • Bei gegebenen Fahrtzeiten ist das Matchingproblem polynomiell lösbar
Das Umladeproblem
Probleminstanz:
 		Umladelösung:
Ziel: Kilometerminimierung durch Umladen von Waren zwischen Fahrzeugen an vorgegebenen Umladepunkten
Lösungsansätze:
  • Mehrgüterflußformulierung
     (Nachteil: nur mit Zeitdimensionformulierbar, sonst mögliche Deadlocks)
  • Pickup-and-Delivery-Formulierung mit Umladeverfeinerungen
e-mail: contact@zpr.uni-koeln.de
Last modified: Mon Jun 28 16:26:06 MET DST 2004