ZAIK
Zentrum für Angewandte Informatik

Arbeitsgruppe Faigle/Schrader


Universität zu Köln

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

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

[OptiLRV] [Verteilproblem] [Komplettladungen] [Umladeproblem]

Das Verteilproblem
Gegeben:
  • ein Depot
  • maximale Fahrzeugkapazität
  • ein Zeitfenster pro Kunde
  • viele Probleminstanzen besitzen keine gültige Lösung

Routenplanung mit mehreren Knotengewichtsfunktionen
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
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

Clusterung auf Basis des Minimal Aufspannenden Baumes
  • Zerlegung des MST unter den Nebenbedingungen wird mit Hilfe eines dynamischen Programmierungsansatzes exakt bestimmt:

Dynamischer Programierungsschritt
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 Zeitfenster
    (-> 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:

3-Opt-Verbesserungsverfahren
  • 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
#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

e-mail: contact@zpr.uni-koeln.de
Last modified: Mon Jun 28 16:21:57 MET DST 2004