City-Logistik-Serviceprovider müssen verstärkt Anforderungen an die Servicequalität in ihren Planungsprozessen berücksichtigen, um neue Geschäftsmodelle des E-Commerce kostengünstig und kundenfreundlich unterstützen zu können. Ein entscheidender Bestandteil der Dienstleistung ist die verlässliche Auslieferung von verderblichen Waren, bei der der Endkunde vor Ort sein muss. In diesem Beitrag wird die Tourenplanung auf Basis tageszeitabhängiger Fahrzeiten vorgestellt, die eine Analyse und Aggregation umfangreicher Reisezeitinformationen voraussetzt. Zum Einsatz kommen flächendeckend erhobene Floating Car Data, die – mit Methoden des Data Mining aggregiert – für tageszeitabhängige Optimierungsmodelle aufbereitet werden. Anhand einer Fallstudie für den Großraum Stuttgart werden zeitabhängige Heuristiken der Tourenplanung vorgestellt sowie Aufwand und Nutzen der zeitabhängigen Tourenplanung diskutiert.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

E-Commerce-Anbieter stehen verstärkt im Wettbewerb hinsichtlich Preis und Servicequalität. Ein wesentlicher Teil der Servicequalität wird definiert durch die schnelle und verlässliche Auslieferung der Produkte, jüngst auch im Bereich verderblicher Ware, die Online-Händler wie amazon.de anbieten [1]. Große Herausforderungen bestehen in der effizienten Auslieferung auf der „letzten Meile“ zum Kunden, denn hier müssen Logistikdienstleister die Kundenversprechen der E-Commerce-Anbieter realisieren und gleichzeitig die Kosten der Auslieferung begrenzen [2].

In diesem Beitrag wird die verlässliche Planung und Realisierung der Auslieferung in der City Logistik diskutiert. Logistikdienstleister müssen verstärkt Anforderungen an die Servicequalität in ihren Planungsprozessen berücksichtigen, z.B. kürzere Lieferzeiten, eine höhere Verlässlichkeit der Tourenpläne und größere Flexibilität in der Auslieferung [3]. In städtischen Gebieten konkurrieren Logistikdienstleister jedoch mit anderen Verkehrsteilnehmern um knappe Verkehrsflächen. Die Verkehrsinfrastruktur ist zeitweise bis an die Kapazitätsgrenze ausgelastet (Stau), so dass die Servicequalität sinkt bzw. höhere Kosten für Logistikdienstleister entstehen [4].

Um die Servicequalität explizit im Planungsprozess zu berücksichtigen, sind zwei Grundvoraussetzungen zu erfüllen: die Bereitstellung von detaillierten Planungsdaten sowie der Einsatz dieser Daten in erweiterten, zeitabhängigen Methoden der Tourenplanung.

Eine effiziente, zeitabhängige Tourenplanung in der City Logistik basiert auf empirischen Verkehrsdaten, die für die zeitabhängige Optimierung eingesetzt werden können. Typische Reisezeiten werden durch tageszeitabhängige Fahrzeiten abgeschätzt. Als Grundlage dienen umfangreiche Reisezeitinformationen, die mittels empirischer Verkehrsdaten in Form von Floating Car Data (FCD) erhoben werden können. Die empirisch erhobenen Reisezeiten sind so aufzubereiten, dass sie in Form von tageszeitabhängigen Fahrzeiten in zeitabhängigen Verfahren der Tourenplanung eingesetzt werden können, um Kundenversprechen effizient zu realisieren.

Während zahlreiche Veröffentlichungen zur klassischen, statischen Tourenplanung  vorliegen [5], birgt die Analyse typischer Fahrzeitmuster und deren Integration in die zeitabhängige Tourenplanung noch umfangreiches Potential. Dies liegt vor allem darin begründet, dass sowohl Datenaufbereitung als auch zeitabhängige Optimierung einen höheren Aufwand erfordern als die klassische, auf einer mittleren Fahrzeit basierende Tourenplanung [6].

Wir fokussieren im Folgenden auf die Bereitstellung und den Einsatz tageszeitabhängiger Fahrzeiten für die Tourenplanung in der City Logistik. Dazu gehen wir zunächst auf die Bereitstellung verschiedener Typen von tageszeitabhängigen Fahrzeiten ein. Der Schwerpunkt liegt dann auf der Modellierung und dem Einsatz dieser Fahrzeiten in zeitabhängigen Verfahren der Tourenplanung. Anhand eines Anwendungsbeispiels für den Großraum Stuttgart werden Aufwand für die Bereitstellung und Nutzen von tageszeitabhängigen Fahrzeiten für die Planung diskutiert.

2 Bereitstellung tageszeitabhängiger Fahrzeiten

Schwankende Verkehrsflüsse implizieren ein tageszeitabhängiges Routing im Stadtverkehr. Informationen über typische Verkehrszustände in Form von tageszeitabhängigen Fahrzeiten unterstützen die Ermittlung verlässlicher Tourenpläne. Im Gegensatz zu Tourenplänen, die auf durchschnittlichen Fahrzeiten oder auf kürzesten Distanzen basieren, erlauben tageszeitabhängige Fahrzeiten die Antizipation typischer Phänomene im Stadtverkehr und damit eine verlässlichere deterministische Planung. Kundenversprechen in Form von Lieferzeitpunkten oder Kundenzeitfenstern lassen sich so effizienter realisieren. Wir fassen im Folgenden die erforderlichen Schritte der Datenerhebung und -verarbeitung zusammen.

2.1 Datenverarbeitungsprozess

In der Vergangenheit waren vor allem Reisezeiten aus Dauerzählstellen auf Bundesautobahnen verfügbar [7], während sich die Ermittlung von Reisezeiten im Stadtverkehr als technisch aufwändig und methodisch schwierig darstellte [8]. Seit einigen Jahren erlauben Telematik-basierte Datenerhebungsmethoden eine kostengünstige und flächendeckende Erhebung von Reisezeiten.

Für die Bereitstellung tageszeitabhängiger Fahrzeiten verwenden wir historische Reisezeiten auf Basis von FCD. Der entsprechende Datenverarbeitungsprozess ist in Bild 1 dargestellt. Er erstreckt sich von der FCD-Rohdatenerhebung bis zum Einsatz von FCD-Aggregaten in zeitabhängigen Routingverfahren. Ein verlässliches Routing wird ermöglicht durch die Transformation von FCD-Rohdaten in Planungsdatensätze unterschiedlichen Aggregationsgerades.

Bild 1: Erhebung und Bereitstellung von tageszeitabhängigen Fahrzeiten

Im Einzelnen sind die folgenden Schritte erforderlich:

- Rohdaten: Taxi-FCD stellen umfangreiche Mengen empirischer Verkehrsdaten für städtische Gebiete bereit. Die GPS-basierte Datenerhebungsmethode basiert auf dem Einsatz von Taxis als im Verkehr mitschwimmenden Datenquellen. Insbesondere das Deutsche Zentrum für Luft und Raumfahrt (DLR) hat den Einsatz von Taxis zur Reisezeiterhebung in jüngerer Zeit erforscht und validiert ([9],[10]). Aus den GPS- Positionen der einzelnen Fahrzeuge werden Reisezeiten für die zurückgelegten Streckenabschnitte abgeleitet.

- Data Cleaning: Fehlerhafte FCD-Datensätze sind zu identifizieren und zu entfernen, zum Beispiel unrealistisch hohe Geschwindigkeitswerte aufgrund von GPS- Abschattungseffekten. Aufgrund der überaus großen Menge an Rohdaten stellt dieser Schritt eine methodische Herausforderung dar. Data-Cleaning-Methoden untersuchen Verlässlichkeit und Repräsentativität der Messungen und filtern Ausreißer heraus (für methodische Details vgl. [11]).

- Data Integration: Die erhobenen Taxi-FCD (empirische Verkehrsdaten) werden um eine digitale Straßenkarte ergänzt (Infrastrukturdaten). Die entsprechenden Daten werden in einer Reisezeitdatenbank zusammengeführt und zu Analyse- und Planungszwecken aggregiert (erste Aggregationsstufe, vgl. Abschnitt 2.2).

- Data Mining: Aggregierte Taxi-FCD werden mittels Clusteranalyse weiter verdichtet. Die Clusteranalyse stellt den Kernschritt zur Bereitstellung tageszeitabhängiger Fahrzeiten  dar (zweite Aggregationsstufe, vgl. Abschnitt 2.3).

- Datenevaluation: Die tageszeitabhängigen Fahrzeiten sind zu evaluieren und ihrem Einsatzzweck entsprechend aufzubereiten. Neben der Darstellung in Form von Tagesganglinien ist der Einsatz geographischer Informationssysteme wie „Google Earth“ hilfreich, um räumlich-zeitliche Hypothesen zur Fahrzeitentwicklung zu überprüfen und eine realistische Approximation typischer Verkehrszustände für die tageszeitabhängige Tourenplanung sicherzustellen.

- Anwendung: Der letzte Schritt ist der Einsatz tageszeitabhängiger Fahrzeiten in City- Logistik-Anwendungen. Hierfür sind tageszeitabhängige Fahrzeiten in angepasste, zeitabhängige Optimierungsverfahren zu integrieren.

2.2 Erste Aggregationsstufe

In der ersten Aggregationsstufe werden empirische Verkehrsdaten in Planungsdaten transformiert. Im Falle von Taxi-FCD sind mittlere Geschwindigkeiten für jeden Link l zu ermitteln, indem das arithmetische Mittel aus n Einzelmessungen im Zeitintervall w gebildet wird. Das Ergebnis ist eine mittlere, tageszeitabhängige Geschwindigkeit für jeden Link l und jedes Zeitintervall w. Eine Alternative zur Mittelwertberechnung ist die Verwendung des Medians eines Zeitintervalls w als statistisch robuste Größe.

Die Berechnung der Mittelwerte setzt die gewünschte Gesamtzahl W der Zeitintervalle voraus. Je nach Datenverfügbarkeit lassen sich beispielsweise Mittelwerte für jede Stunde eines Wochentages bilden (hier: W = 24 x 7), um die erwarteten Schwankungen der Fahrzeiten an den einzelnen Wochentagen zu verschiedenen Tageszeiten abzubilden. Der resultierende Datensatz wird im Folgenden als „FH“ bezeichnet (FCD Hourly Average).

Tourenplanungsverfahren, die FH-Datensätze berücksichtigen, müssen eine große Datenmenge effizient verarbeiten können. Aus diesem Grund wird im folgenden Abschnitt diskutiert, inwiefern die Beschränkung des Hauptspeichers sowie die Komplexität der zeitabhängigen Tourenplanungsverfahren und der Wunsch nach schneller und verlässlicher Tourenplanung bei der Bereitstellung von tageszeitabhängigen Fahrzeiten berücksichtigt werden können.

2.3 Zweite Aggregationsstufe

Die zweite Aggregationsstufe basiert auf dem Einsatz von Data-Mining-Verfahren. Eine wochentagsabhängige Clusteranalyse von normalisierten FH-Datensätzen führt zu einem kompakten und speichereffizienten Planungsdatensatz. Die sich ergebenden Cluster dienen zur Charakterisierung der enthaltenen Links, die sich durch möglichst ähnliche relative Schwankungen der Geschwindigkeit auszeichnen.

Kern der Clusteranalyse ist die Gruppierung normalisierter FH-Daten mit dem k-means- Algorithmus [12]. Der Algorithmus minimiert iterativ die Fehlersumme des Abstandes der Datenobjekte zum jeweiligen Clustermittelpunkt. Die Anzahl der gewünschten Cluster k wird mit Indizes bestimmt, die die Güte einer Clusteranalyse (z.B. anhand der Fehlersumme) beschreiben. Ziel ist es, k so klein wie möglich zu halten, um den Aufwand für die zeitabhängige Tourenplanung zu begrenzen. Gleichzeitig ist sicherzustellen, dass k ausreichend groß gewählt wird, um eine zufriedenstellende Repräsentation der Geschwindigkeitsschwankungen mit k Clustern zu gewährleisten. Experimente mit k = 4, 5, 6 führen zu akzeptablen Ergebnissen [13]. Eine höhere Anzahl von Gruppen erzielt erst mit großem k eine entscheidende Verbesserung der Gruppenzuordnungen.

Die Clusteranalyse resultiert in tageszeitabhängigen Gewichtungsfaktoren für jedes Cluster. Diese repräsentieren typische Geschwindigkeitsschwankungen, aus welchen Schätzungen der tatsächlichen Geschwindigkeit abgeleitet werden können. Dafür wird jeweils der tageszeitabhängige Gewichtungsfaktor für einen Link ermittelt und mit einem robusten Geschwindigkeitsmaß verrechnet (wie beispielsweise der durchschnittlichen mittleren oder maximalen Geschwindigkeit). Dies führt zu großen Effizienzgewinnen bei der Generierung von Distanzmatrizen und einer Reduktion der Hauptspeicherbelastung. Dieser kompakte Datensatz wird im Folgenden als „FW“ bezeichnet (FCD Weighted Averages).

Bild 2: Tageszeitabhängige Gewichtungsfaktoren für Donnerstage (k = 6)

In Bild 2 ist ein beispielhaftes Ergebnis der Clusteranalyse für Donnerstage in Form von relativen Tagesgängen angegeben. Jedes Cluster repräsentiert die zugehörigen Links in Form von Gewichtungsfaktoren, die zu verschiedenen Tageszeiten eine mehr oder weniger starke Abweichung von der mittleren Geschwindigkeit angeben. Links des Clusters 2 weisen beispielsweise relativ konstante Geschwindigkeiten auf, während bei Links des Clusters 5 deutliche Einbrüche in der Früh- und Spätspitze erkennbar sind.

3 Bereitstellung zeitabhängiger Distanzmatrizen

Die tageszeitabhängige Optimierung erfordert zeitabhängige Distanzmatrizen. In diesem Abschnitt beschreiben wir die Erweiterung einer klassischen, statischen Straßennetztypologie zu einer zeitabhängigen, digitalen Karte. Aus dieser tageszeitabhängigen Typologie lassen sich – die FIFO-Bedingung vorausgesetzt – zeitabhängige kürzeste Wege bestimmen, die in Form von Distanzmatrizen Eingang in die tageszeitabhängige Optimierung finden.

3.1 Konzeption einer tageszeitabhängigen Typologie

Die klassische Tourenplanung abstrahiert vom Straßennetz, indem sie auf eine graphentheoretische Abbildung von Kunden als Knoten zurückgreift. Die Kunden werden mittels Kanten verbunden, welchen statische „Kosten“ in Form von Distanzen, Fahrtdauern o.ä. zugeordnet sind [14]. Sie repräsentieren kürzeste Wege hinsichtlich Distanzen und/oder Fahrzeiten, die auf einer statischen Typologie des Straßennetzes ermittelt worden sind. So werden statische Distanzmatrizen bereitgestellt, die bei der Ermittlung der kostengünstigsten Tour zum Einsatz kommen.

Im Gegensatz zur klassischen, statischen Tourenplanung sind im zeitabhängigen Kontext variierende Kosten für jede Kante zu modellieren. Diese werden in Form von tageszeitabhängigen Distanzmatrizen in der zeitabhängigen Tourenplanung berücksichtigt. Voraussetzung für die Bereitstellung tageszeitabhängiger Distanzmatrizen ist die tageszeitabhängige Berechnung kürzester Wege auf Basis einer Typologie des Straßennetzes, welche variierende Fahrzeiten abbilden kann. Üblicherweise werden den Kanten in solch zeitabhängigen Netzwerken Reise- bzw. Fahrzeitfunktionen zugeordnet, die die Ankunftszeit am Zielknoten abhängig von der Startzeit auf der Kante angeben. In der Literatur finden sich sowohl diskrete als auch kontinuierliche Modellierungsansätze für Fahrzeitfunktionen [15]. Ein Beispiel für die Ermittlung kontinuierlicher Fahrzeitfunktionen aus FCD ist die Single Value Decomposition [16]. Wir nutzen im Folgenden einen diskreten Ansatz: Hier werden stückweise-lineare Fahrzeitfunktionen zur Modellierung einer zeitabhängigen Straßennetztypologie verwendet.

3.2 FIFO-Bedingung

Voraussetzung für die Ermittlung zeitabhängiger kürzester Wege ist die Sicherstellung der FIFO-Bedingung. Die Diskretisierung des Zeithorizonts kann dazu führen, dass ein früher abfahrendes Fahrzeug sein Ziel später erreicht als ein später abfahrendes. In FIFO- konformen Netzwerken können sich Fahrzeuge nicht „überholen“, d.h., dass (fiktive) Fahrzeuge in der zeitlichen Reihenfolge das Ziel einer Kante erreichen, in der sie die Kante begonnen haben („non-passing condition“, [17], [18]).

Folgende Eigenschaften reduzieren die Komplexität der zeitabhängigen Wegeberechnung erheblich [15]:

- In FIFO-Netzwerken verzögert das Warten an Knoten die Ankunftszeit am Ende der Tour.

- In FIFO-Netzwerken findet man immer einen kürzesten, azyklischen Pfad.

- In FIFO-Netzwerken findet man immer kürzeste Wege, deren Teilwege wieder kürzeste Wege sind.

FIFO-Netzwerke erlauben die zeitabhängige Berechnung kürzester Wege mittels leicht angepasster, effizienter Labeling-Verfahren wie Dijkstras Algorithmus [19].

FH- und FW-Datensätze erfüllen die FIFO-Bedingung nicht notwendigerweise, da sie aus empirischen Reisezeiten abgeleitet worden sind. Diese verletzten gegebenenfalls dann die FIFO-Bedingung, wenn einem Zeitintervall mit langer Fahrzeit ein Zeitintervall mit kurzer Fahrzeit folgt. Somit weist die resultierende Fahrzeitfunktion für einen Link möglicherweise große „Sprünge“ zwischen zwei Zeitintervallen auf. Um diesem Problem zu begegnen, folgen wir dem Ansatz von Fleischmann et al. [6]: Hier werden Nicht-FIFO-Netzwerke in FIFO- konforme Netzwerke überführt, indem Sprünge der Fahrzeitfunktion linearisiert werden.

Bild 3: Konstruktion der stückweise linearen Fahrzeitfunktion mit Linearisierung an den Sprungstellen z1 und z2

Bild 3 veranschaulicht die Ableitung der Fahrzeiten τli aus mittleren Geschwindigkeiten vli für einen Link l. Die Fahrzeitfunktion τl(t) ergibt sich aus den FH- bzw. FW-Datensätzen und weist vereinzelt Sprünge bei zi auf. Beispielsweise wechselt die mittlere Geschwindigkeit bei z1 von relativ gering nach relativ hoch, was zu einer eher längeren bzw. eher kürzeren Fahrzeit führt. Dieser Wechsel ist nicht FIFO-konsistent; ein Fahrzeug, welches kurz vor dem Zeitpunkt z1 startet, würde von einem Fahrzeug überholt, welches kurz nach dem Zeitpunkt z1 startet. Fleischmann et al. lösen dieses Problem durch die Linearisierung der Fahrzeitfunktion im Abschnitt [zi – δli; zi + δli]. δli bestimmt die Steigung s0, welche nicht größer als s = 1 werden darf, um die FIFO-Bedingung zu erfüllen. Bei ansteigenden Fahrzeiten kann die Steigung frei gewählt werden (hier: δli = 1).

In der resultierenden FIFO-konformen Typologie ist nun der Einsatz von leicht angepassten klassischen Kürzeste-Wege-Verfahren möglich.

3.3 Ermittlung tageszeitabhängiger Distanzmatrizen

FIFO-konforme, tageszeitabhängige Straßennetztopologien erlauben die Ableitung tageszeitabhängiger Distanzmatrizen. Für die zeitabhängige Tourenplanung sind nun für jede mögliche Abfahrtszeit die kürzesten Wege zu bestimmen. Um den Rechenaufwand zu begrenzen, beschränken wir uns auf mögliche Abfahrtszeitpunkte zu jeder vollen Viertelstunde. Damit sind 7 x 24 x 4 statische Distanzmatrizen zu ermitteln, die zeitabhängige Schwankungen der Fahrzeit sowie zugrundeliegende kürzeste Wege repräsentieren. Während die Kompaktheit des FW-Datensatzes zu einem Berechnungsaufwand ähnlich einer statischen Typologie führt, weist der FH-Datensatz 672 verschiedene Typologien und einen dementsprechend hohen Speicherplatzbedarf auf.

4 Zeitabhängige Tourenplanung

Um den Einsatz und den Nutzen zeitabhängiger Tourenplanung zu verdeutlichen, diskutieren wir das zeitabhängige Traveling Salesman Problem (TDTSP) unter Berücksichtigung von zeitabhängigen Distanzmatrizen. Wir erweitern, implementieren und vergleichen fünf Heuristiken und präsentieren deren Einsatz im Rahmen einer City-Logistik-Fallstudie für den Großraum Stuttgart.

Das TDTSP stellt eine Erweiterung des bekannten Traveling Salesman Problems dar [20]. Es ist wie folgt definiert: Finde eine Tour minimaler Fahrzeit, die am Depot zu vorgegebener Zeit beginnt. Besuche dabei jeden Kunden genau einmal, und kehre dann ins Depot zurück. Die Fahrzeit (und ggf. auch die Route) zwischen den Kunden bzw. zwischen dem Depot und einem Kunden hängt von der jeweiligen Tageszeit ab. Kapazitätsrestriktionen werden an dieser Stelle außer Acht gelassen; wir nehmen an, dass Fahrzeuge der City-Logistik ausreichend Kapazität für tendenziell kleine, standardisierte Ladungseinheiten aufweisen. Als Erweiterung des TSP gehört das TDTSP zur Klasse der NP-vollständigen Probleme, für die es unwahrscheinlich ist, dass ein Algorithmus mit polynomieller Laufzeit entwickelt werden kann. Für Probleme praktischer Größe kommen deswegen vorwiegend Heuristiken zum Einsatz, die in endlicher Zeit eine möglichst gute, aber nicht zwingender Weise optimale Lösung ermitteln.

Wir passen im Folgenden klassische Heuristiken zur Lösung des TSP für das TDTSP auf Basis von zeitabhängigen Distanzmatrizen an.

4.1 Verfahren des Nächsten Nachbarn (NN)

Eine einfache Heuristik stellt das Verfahren des Nächsten Nachbarn (NN) dar. Hierbei werden – ausgehend vom Abfahrtszeitpunkt am Startdepot – die noch nicht bedienten Kunden zu einer Rundreise hinzugefügt. Dabei wird jeweils der Kunde ausgewählt, der zum aktuellen Zeitpunkt am schnellsten vom aktuellen Knoten zu erreichen ist („nächster Nachbar“). Der entsprechende Kandidat lässt sich mit Hilfe der tageszeitabhängigen Distanzmatrix leicht ermitteln. NN berücksichtigt schwankende Fahrzeiten ohne nennenswerte konzeptionelle Anpassungen [21], unterliegt jedoch dem Nachteil seiner myopischen Vorgehensweise. „Schwierige“ Kunden, die aufgrund ihrer Entfernung tendenziell weit von der aktuellen Teilroute entfernt liegen, werden solange aufgeschoben, bis ihre Einbeziehung unvermeidbar und fahrzeitintensiv wird. Auch wird jeweils nur die derzeitige Fahrzeit zu den nächsten Kunden berücksichtigt. Die Ergebnisse eines klassischen Nächsten-Nachbar-Verfahren liegen erfahrungsgemäß ca. 15% vom Optimum entfernt [14].

Um den konzeptionellen Nachteilen des NN zu begegnen, kommen Tourenverbesserungsverfahren wie Kantentauschverfahren zum Einsatz. Beim 2-opt- Verfahren werden beispielsweise immer wieder zwei nicht benachbarte Kanten vertauscht, bis keine Verbesserung hinsichtlich der Gesamtdauer mehr zu erzielen ist [14]. Es ist zu berücksichtigen, dass sich hierbei nicht nur die Bedienungsreihenfolge der Kunden im Tauschbereich ändert, sondern sich auch Änderungen von Abfahrts- und Ankunftszeiten im und nach dem Tauschbereich ergeben.

4.2 Nächster Nachbar auf Basis Dynamischer Programmierung (NNDYN)

Um die Nachteile der myopischen Vorgehensweise des NN abzumildern, stellen wir eine von Malandraki und Dial [22] vorgeschlagene Variante des NN auf Basis der Dynamischen Programmierung vor (NNDYN). Die Dynamische Programmierung ist den exakten Optimierungsverfahren zuzuordnen und ermittelt kostenoptimale Entscheidungen auf Basis von Zuständen und Zustandsübergängen. Jeder Übergang von einem Zustand in einen Folgezustand verursacht Kosten. Das TSP kann als entsprechendes Entscheidungsproblem modelliert werden, bei dem die Entscheidung, einen bestimmten Kunden als nächsten zu bedienen, vom aktuellen in den Folgezustand führt und entsprechende Kosten (z.B. zusätzliche Fahrzeiten) verursacht. Ziel ist, die Gesamtkosten aus Zustandsübergängen zu minimieren. Dieses entspricht der Zielfunktion des TSP [14].

Die exakte Berechnung des TSP mit Dynamischer Programmierung führt zu einer Explosion der Laufzeit und der Speicheranforderungen, da im Prinzip alle möglichen Entscheidungen abgebildet werden müssen, um die kostenoptimale Reihenfolge der Kunden zu ermitteln. Daher führen Malandraki und Dial [22] eine Heuristik ein, die nur eine Teilmenge des für das TDTSP relevanten Entscheidungsbaums berücksichtigt. Ausgehend vom Startdepot werden Teiltouren zu allen Kunden initialisiert und im nächsten Schritt weiter bearbeitet. Der Idee von NN folgend, werden in jedem Zustand nur die H vielversprechendsten Teiltouren mit den frühesten Ankunftszeiten weiter verfolgt. Im Fall von H = 1 entspricht dieses Vorgehen dem NN-Prinzip. NNDYN verfolgt also nicht nur die beste Entscheidung, sondern die derzeit H besten Alternativen. Größenordnungen von H = 100 000 Teiltouren lassen sich mit einem Desktop-PC verarbeiten.

4.3 Zeitabhängiges Einfügeverfahren (RC)

Einfügeheuristiken stellen eine erfolgreiche und weit verbreitete Methodik zur Ermittlung heuristischer Lösungen von TSPs dar [23]. Wir implementieren die zeitabhängige Variante „RC“ wie folgt: Ausgehend vom Startdepot wird eine Pendeltour zum derzeit weit entferntesten Kunden konstruiert. In jedem folgenden Bearbeitungsschritt wird die aktuelle Tour mit demjenigen Kunden erweitert, der die Tour an entsprechender Position kostenminimal erweitert. Aufgrund der Zeitabhängigkeit der zugrundeliegenden Topologie sind die Fahrzeiten beginnend von der Einfügeposition eines weiteren Kunden neu zu ermitteln.

Einfügeverfahren führen zu tendenziell besseren Lösungen als NN, da „teurere“ Kunden von Beginn an kostenminimal berücksichtigt werden. Trotzdem besteht noch Potential für Tourenverbesserungsverfahren wie 2-opt, welche wir nach gefundener Startlösung auf RC- Lösungen anwenden.

4.4 Kombination von RC und NNDYN (RCDYN)

Während RC noch nicht bediente Kunden nach einem intelligenten Mechanismus einfügt, sucht NNDYN den entsprechenden Suchraum relativ gründlich ab. Wir schlagen deshalb eine Kombinationsheuristik vor, die beide Prinzipien miteinander vereinigt (RCDYN). Wie im Falle von RC werden zunächst Pendeltouren ausgehend vom Startdepot erzeugt. Es wird jedoch nicht nur die Pendeltour zum „teuersten“ Kunden weiterverfolgt, sondern es werden zunächst Pendeltouren zu allen Kunden ermittelt. Die Pendeltouren werden dann – dem NNDYN-Prinzip folgend – durch Hinzufügen von jeweils einem weiteren, bisher noch nicht enthaltenen Kunden an kostenminimaler Position erweitert. Das Hinzufügen eines weiteren Kunden wird als Zustandsübergang interpretiert. Führt der Übergang zu einem Folgezustand mit mehr als H Teiltouren, werden nur die H kürzesten Teiltouren für die Weiterbearbeitung  in Betracht gezogen. Da in jeder der H Teiltouren die kostenoptimale Einfügeposition aus allen übrigen Kunden ermittelt wird, ist H mit Bedacht zu wählen, um eine Explosion der Laufzeit zu vermeiden.

4.5 Angepasstes Savings-Verfahren (SAF)

Ein klassisches Verfahren zur Berechnung von Touren ist das Savings-Verfahren [14]. Die Idee ist, zunächst jeden Kunden in einer individuellen Pendeltour vom Depot aus zu bedienen, und diese Touren dann mit größt möglicher Einsparung („Savings“) zu verschmelzen. Die Verschmelzung erfolgt aufgrund einer vorberechneten Savings-Liste, welche nach Vorteilhaftigkeit sortierte Savings enthält. Eine Einsparung ergibt sich jeweils aus der Fahrzeit vom aktuellen Kunden zum Depot sowie der Fahrzeit vom Depot zum nächsten Kunden, abzüglich der zusätzlichen Fahrzeit vom aktuellen zum neuen Kunden.

Gietz [21] schlägt eine Savings-Variante für den Einsatz bei tageszeitabhängigen Fahrzeiten und vorgegebenen Kundenzeitfenstern vor. Um den Einfluss tageszeitabhängiger Fahrzeit  zu fokussieren, verzichten wir an dieser Stelle auf die Vorgabe fixer Kundenzeitfenster. Damit wird das Savings-Prinzip wertlos, da die tatsächliche Realisierung der Einsparung von der Tageszeit abhängt, diese aber wiederum die Einsparung determiniert.

Die hier verwendete Savings-Variante ermittelt einen mittleren Savings-Wert, der sich aus einer Abschätzung des Planungshorizontes ergibt. Für die Abschätzung verwenden wir das NN-Verfahren, welches eine Art obere Schranke für die Gesamtfahrzeit der Tour darstellt. Aus den von der Tour betroffenen Distanzmatrizen wird ein mittlerer Savings-Wert berechnet. Die Pendeltouren werden dann entsprechend dieser Savings-Liste miteinander verschmolzen.

5 Fallstudie Großraum Stuttgart

Anhand einer Fallstudie für den Großraum Stuttgart werden Einsatz und Nutzen tageszeitabhängiger Fahrzeiten für die Tourenplanung verdeutlicht. Die Fallstudie basiert auf einem Optimierungsframework, welches sowohl aufbereitete FCD als auch die vorgestellten Heuristiken umfasst. Es wird hinsichtlich des Aufwandes der Datenanalyse, Speicheranforderungen und der Lösungsqualität der Heuristiken analysiert. Wie bereits in Kapitel 4 beschrieben, beschränken wir uns hier auf optimale Tourenpläne für ein Fahrzeug. Im Folgenden beschreiben wir zunächst den Aufbau des Experiments und stellen dann die Ergebnisse sowohl aus räumlicher als auch aus zeitlicher Perspektive vor. Mit Beobachtungen zur Performance der Algorithmen und zur Lösungsqualität wird die Fallstudie abgeschlossen.

5.1 Experiment

Die folgenden Berechnungen werden für einen fiktiven City-Logistik-Dienstleister durchgeführt, der 20 ausgesuchte Kunden mit einem Fahrzeug im Großraum Stuttgart beliefert. Das Depot befindet sich in einem Industriegebiet am Stadtrand; die Kunden konzentrieren sich einerseits auf die Innenstadt, andererseits auf Vororte. Die Servicezeit beläuft sich auf 10 Minuten je Kunde.

Bild 4: Relative Standardabweichung von FCD im vorliegenden Straßennetz sowie Vergrößerung des Ausschnitts der Stadt Stuttgart. (Sehr hoch, hoch, mittel, gering)

Als Datengrundlage stehen FH- und FW- aufbereitete FCD zur Verfügung, die in den Jahren 2003-2005 im Großraum Stuttgart vom DLR erhoben worden sind. Der Umfang des Rohdatensatzes beläuft sich auf ca. 230 Millionen FCD, die sich auf ein Gebiet von ca. 35x35 km² bzw. etwa 100 000 Links beziehen (vgl. Bild 4, Großraum Stuttgart). Für die Tourenplanung beschränken wir uns auf den Bereich der Stadt Stuttgart, der grob durch einen weißen Rahmen gekennzeichnet ist. Hier liegen die meisten FCD-Messungen vor. Ferner sind die Links in diesem Bereich durch hohe relative Standardabweichungen gekennzeichnet und bieten sich daher für eine zeitabhängige Tourenplanung an.

Die empirisch durch FCD erhobenen Reisezeiten wurden entsprechend des in Kapitel 2 vorgestellten Datenverarbeitungsprozesses analysiert und aggregiert. Aus den aggregierten Reisezeiten wurden FIFO-konforme FH- und FW-Datensätze abgeleitet, die zur Bereitstellung von tageszeitabhängigen Distanzmatrizen genutzt wurden. Für jeden Datensatz wurden 21 x 20 x 672 kürzeste Wege vorberechnet.

Die zeitabhängige Tourenplanung erfolgt für den FH- als auch für den FW-Datensatz unter Einsatz der fünf vorgestellten Heuristiken. Um den Einfluss der Zeitabhängigkeit zu demonstrieren, werden jeweils 7 x 24 Touren (also für alle Wochentage und Stundenintervalle) berechnet. Die Abfahrtszeit am Depot wird dafür jeweils um eine Stunde verschoben, beginnend mit Montag, 00:30 Uhr. Insgesamt ergeben sich daraus 2 x 5 x 7 x 24 = 1680 Tourenpläne.

Zunächst betrachten wir generelle Einflüsse der tageszeitabhängigen Fahrzeiten auf die Routenwahl am Beispiel zweier Touren am Montag (räumliche Analyse). Darauffolgend wird die Qualität der Heuristiken und die absolute Dauer der Touren diskutiert (zeitliche Analyse). Beobachtungen zur Performance der Algorithmen schließen die rechnerischen Ergebnisse ab.

5.2 Räumliche Analyse

Die zeitabhängige Tourenplanung sollte typische Phänomene des Stadtverkehrs antizipieren und bei der Ermittlung der optimalen Reihenfolge der zu beliefernden Kunden berücksichtigen. Bild 5 verdeutlicht beispielhaft das Ergebnis der Tourenplanung, hier ermittelt mit dem NNDYN-Verfahren auf Basis von FH-Distanzmatrizen für eine Abfahrt vom Depot an einem typischen Montag um 13:30 Uhr.

Bild 5: Beispieltour für Abfahrt Montag, 13:30 (NNDYN / FH). Abfahrtszeiten am Depot bzw. Ankunftszeiten bei den einzelnen Kunden sind in [eckigen Klammern] angegeben. (Runde Klammern) zeigen die Position des Kunden in der Tour an.

Das Depot ist an Position „(0)“ bzw. „(21)“ im Tourenplan erkennbar. Es befindet sich am nördlichen Stadtrand von Stuttgart. Die Kunden werden im Uhrzeigersinn bedient, so dass das Fahrzeug um 18:16 Uhr im Depot zurückerwartet wird. Zunächst werden Kunden in den Vororten angefahren; in der auf Zufahrtsstrecken typischen Rush-Hour liegt die Bedienung von Kunden der Innenstadt im Fokus. Die reine Fahrzeit abzüglich der Servicezeit beim Kunden beträgt 86 Minuten.

In Bild 6 ist nun der von NNDYN ermittelte Tourenplan für eine Abfahrt am Montagabend um 19:30 Uhr angegeben. Aufgrund der hinterlegten Distanzmatrizen ergibt sich hier ein komplett anderer Tourenplan, denn die Kunden werden nun entgegen des Uhrzeigersinns beliefert, beginnend mit Kunden in der Innenstadt. Da die Belieferung außerhalb verkehrsstarker Zeiten stattfindet, verkürzt sich die gesamte Fahrzeit auf 78 Minuten.

Bild 6: Beispieltour für Abfahrt Montag, 19:30 Uhr (NNDYN / FH). Abfahrtszeiten am Depot bzw. Ankunftszeiten bei den einzelnen Kunden sind in [eckigen Klammern] angegeben. (Runde Klammern) zeigen die Position des Kunden in der Tour an.

Die genannten Beispiele verdeutlichen die Komplexität der Tourenplanung allgemein sowie im Stadtverkehr. Die Berücksichtigung tageszeitabhängiger Fahrzeiten führt zu deutlich sichtbaren Unterschieden in der Gesamtfahrzeit als auch in der Routenwahl.

5.3 Zeitliche Analyse

Eine zeitliche Analyse der tageszeitabhängigen Tourenpläne erlaubt Vergleiche der einzelnen Heuristiken untereinander als auch die Analyse des Nutzens, der sich aus der erweiterten Tourenplanung ergibt. In Bild 7 (linke Seite) sind zunächst die Gesamtdauern der Tourenpläne (ohne Servicezeiten) abgebildet, die auf dem FH-Datensatz basieren. Die einzelnen Wochentage werden durch graue Markierungen angedeutet. Angegeben ist  jeweils die Abfahrtszeit am Depot und die sich ergebende Gesamtdauer des Tourenplans, ermittelt von der entsprechenden Heuristik.

Auf den ersten Blick erkennbar sind die zeitlichen Schwankungen in der Gesamtdauer, die sich abhängig vom Startzeitpunkt am Depot ergeben. Die Gesamtdauer steigt bei Abfahrten bis in die Mittagszeit hinein und fällt dann bis zu den Abfahrten am Abend und nachts wieder ab. Am Wochenende sind diese Schwankungen nicht so stark ausgeprägt. Die Gesamtdauer der Touren mit der jeweils kürzesten Fahrzeit schwankt zwischen 69 Minuten (Abfahrt Sonntag, 3:30 Uhr) und 89 Minuten (Abfahrt Freitag, 9:30 Uhr).

Im Vergleich der Heuristiken untereinander zeigt der NN-Ansatz seine Schwächen mit Tourenplänen, welche die im Vergleich längste Dauer aufweisen. RC und RCDYN sind durchgängig in der Lage, bessere Lösungen zu ermitteln. SAF bewegt sich im Mittelfeld. Zur Information ist die statische Lösung des RC angegeben, die – wie erwartet – die Gesamtdauern von Touren tagsüber unter- und nachts überschätzt.

Ein ähnliches Bild ergibt sich unter Verwendung von zeitabhängigen Distanzmatrizen auf Basis des kompakten FW-Datensatzes. Im Vergleich verdeutlicht Bild 7 (rechte Seite) eine geglättete Darstellung aufgrund der zusätzlichen Aggregation, die sich aus der Clusteranalyse ergibt. Die Dauern der Touren unterscheiden sich ähnlich wie im FH-Fall; NN liefert erneut die Touren mit den längsten Gesamtdauern, SAF bewegt sich im Mittelfeld und RCDYN/NNDYN ermitteln die Touren mit der relativ kürzesten Dauer.

Einige Beobachtungen zur Performance und zur Lösungsqualität der Heuristiken fasst der folgende Abschnitt abschließend zusammen.

5.4 Lösungsqualität und Performance der Algorithmen

Heuristiken der zeitabhängigen Tourenplanung sollen gute Ergebnisse in akzeptabler Laufzeit bereitstellen. Um die vorgestellten Verfahren hinsichtlich ihrer Lösungsqualität und Performance zu analysieren, nehmen wir einen relativen Vergleich der mittleren Abweichung von der uns bekannten besten Lösung und der relativen Laufzeit vor. Ferner geben wir an, wie oft das entsprechende Verfahren tatsächlich die beste uns bekannte Lösung ermitteln konnte.

Tabelle 1: Performance der Heuristiken auf FH-/FW-Distanzmatrizen

Bild 7: Tourenpläne im Wochenverlauf auf Basis des FH- (links) bzw. des FW-Datensatzes (rechts)

In Tabelle 1 sind die Performancekriterien hinsichtlich der Tourenplanung mit FH- und FW- Distanzmatrizen angegeben. Während beispielsweise das NN-Verfahren niemals die beste uns bekannte Lösung ermitteln konnte und im Mittel 13.3 % bzw. 14.8 % von der uns bekannten besten Lösung entfernt ist, führt das Kombinationsverfahren RCDYN in 61.3 % bzw. 98.8 % aller Fälle zur besten bekannten Lösung. Eine gute Wahl ist die Einfügeheuristik RC: selbst bei geringer Laufzeit werden hier akzeptable Ergebnisse erzielt. Im FW-Fall verschiebt sich die Skalierung aufgrund der vereinfachten Modellierung des Netzes mit Geschwindigkeitsfaktoren.

6 Zusammenfassung und Ausblick

Die kostengünstige als auch kundenfreundliche Auslieferung von E-Commerce-Produkten stellt umfangreiche Herausforderungen an Logistikserviceprovider. In diesem Beitrag wurde aufgezeigt, welche Voraussetzungen planungsseitig erforderlich sind, um sowohl Kundenversprechen als auch betriebswirtschaftliche sinnvolle Auslieferkonzepte zu realisieren. Telematik-basierte Verkehrsdatenerhebung einerseits sowie fortgeschrittene Methoden der Massendatenanalyse andererseits erlauben die Bereitstellung von tageszeitabhängigen Fahrzeiten, die typische Phänomene des Stadtverkehrs abbilden. Deterministische Verfahren der Tourenplanung können geeignet erweitert werden, um tageszeitabhängige Fahrzeiten effizient zu verarbeiten.

Der Fokus in diesem Beitrag lag auf der Modellierung einer tageszeitabhängigen Typologie auf Basis von weithin verfügbaren FCD-Rohdaten. Methoden der Clusteranalyse erlauben die Ableitung von Gewichtungsfaktoren, die zur Bereitstellung von tageszeitabhängigen Distanzmatrizen genutzt werden können. Um Informationen der Straßennetztypologie konsistent in tourenplanungsspezifische Optimierungsmodelle überführen zu können, ist die Sicherstellung der FIFO-Bedingung notwendig. Auf dieser Basis wurde ein Optimierungsframework implementiert, welches sowohl bekannte als auch neue Heuristiken der zeitabhängigen Tourenplanung beinhaltet. Anhand einer Fallstudie für den Großraum Stuttgart konnten sowohl Aufwand als auch Nutzen der tageszeitabhängigen Optimierung aufgezeigt werden.

Die zukünftigen Bemühungen fokussieren auf die Erweiterung des Optimierungsframeworks für eine Flotte von Fahrzeugen (Vehicle Routing Problem mit Zeitfenstern). Es soll untersucht werden, inwiefern die Berücksichtigung von Kundenzeitfenstern den Vorteil tageszeitabhängiger Fahrzeiten hinsichtlich der Flexibilität von Touren abmildert bzw. die Verlässlichkeit der Kundenzeitfenster erhöht. Metaheuristiken zeigen hier vielversprechende Ansätze, die es aufzugreifen und zu erweitern gilt. Ferner ist die strukturelle Qualität der ermittelten Touren im Stadtverkehr detailliert zu analysieren, z.B. hinsichtlich Verlässlichkeit der gewählten Strecken und der Adaptivität der eingesetzten Heuristiken in Bezug auf tageszeitabhängige Fahrzeiten.

7 Literatur

[1]    SCHLAUTMANN, C. (30.12.2010): Lebensmittel aus dem Internet: Die Zukunft des Einkaufens. Handelsblatt.

[2]    AGATZ, N.; CAMPBELL, A.; FLEISCHMANN, M.; SAVELSBERGH, M. (2008). Challenges and Opportunities in Attended Home Delivery. In: GOLDEN, B.; RAGHAVEN, R.; WASIL, E. (Hrsg.): The Vehicle Routing Problem: Latest Advances and New Challenges, Springer.

[3]    WINDT, K.; HÜLSMANN, M. (2007). Changing Paradigms in Logistics – Understanding the Shift from Conventional Control to Autonomous Cooperation and Control. In: HÜLSMANN, M.; WINDT, K. (Hrsg.): Understanding Autonomous Cooperation and Control in Logistics, S. 1-72, Springer.

[4]    EGLESE, R.; MADEN, W.; SLATER, A. (2006). A road timetable to aid vehicle routing and scheduling. Computers and Operations Research 12, S. 3508-3519.

[5]    BRÄYSY, O.; GENDREAU, M. (2005). Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science 39, 1, S. 104-118.

[6]    FLEISCHMANN, B.; GIETZ, M.; GNUTZMANN, S. (2004). Time-Varying Travel Times in Vehicle Routing. Transportation Science 2, 2004, S. 160-173.

[7]    KLEINHANS, M. (2002). Klassifikation von Verkehrsdaten mit Clusterverfahren. Diplomarbeit, Mathematisches Institut der Universität Köln. URL: http://www.zaik.uni- koeln.de/~paper/unzip.html?file=diplom_MarkusKleinhans.pdf.

[8]    EHMKE, J. F.; MEISEL, S. (2008): Charakterisierung des städtischen Straßenverkehrs mit Floating Car Data und Data Mining. Straßenverkehrstechnik 10/2008, S. 613-320.

[9]    BROCKFELD, E.; LORKOWSKI, S.; MIETH, P.; WAGNER, P. (2007): Benefits and limits of recent floating car data technology – an evaluation study. Präsentiert auf der 11. WCTR Conference, Berkeley, USA. URL: http://elib.dlr.de/49618/.

[10]    BROCKFELD, E.; PASSFELD, B.; WAGNER, P. (2007): Validating travel times calculated on the basis of taxi floating car data with test drives. Proceedings of 14th ITS Conference, October 9th-13th, 2007. Beijing, China. URL: http://elib.dlr.de/50208/.

[11]    EHMKE, J. F.; MEISEL, S.; ENGELMANN, S.; MATTFELD, D. C. (2009): Data Chain Management for Planning in City Logistics. International Journal of Data Mining, Modelling and Management, Vol. 1, Nr. 4, S. 335-356.

[12]    MACQUEEN, J. (1967): Some methods for classification and analysis of multivariate observations. In: LE CAM, L. M.; NEYMAN, J. (Hrsg.): Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, S. 281-287.

[13]    EHMKE, J. F.; MEISEL, S.; MATTFELD, D. C. (2010). Floating Car Data Based Analysis of Urban Travel Times for the Provision of Traffic Quality. In: BARCELÓ, J.; KUWAHARA, M. (Hrsg.): Traffic Data Collection and its Standardization, Springer.

[14]    VAHRENKAMP, R.; MATTFELD, D. C. (2007). Logistiknetzwerke. Gabler, Wiesbaden.

[15]    DEAN, B. C. (1999). Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms.    Massachusetts    Institute    Of    Technology.    URL: http://www.cs.clemso.edu/~bcdean/paper18.html.

[16]    SOHR, A.; WAGNER, P.; BROCKFELD, E. (2009). Floating Car Data based Traveltime Prediction With Lomb Periodogram. Arbeitspapier, DLR Berlin.

[17]    KAUFMAN, D. E.; SMITH, R. L. (1993). Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. In: IVHS 1, S. 1–11.

[18]    ICHOUA, S.; GENDREAU, M.; POTVIN, J.-Y. (2003). Vehicle dispatching with time- dependent travel times. European Journal of Operational Research 144(2), S. 379-396.

[19]    DIJKSTRA, E. W. (1959). A note on two problems in connexion with graphs.  Numerische Mathematik 1, S. 269-271.

[20]    SCHNEIDER, J. (2002). The time-dependent traveling salesman problem. Physica A: Statistical Mechanics and its Applications 314, S. 151-155.

[21]    GIETZ, M. (1994). Computergestützte Tourenplanung mit zeitkritischen Restriktionen. Physica.

[22]    MALANDRAKI, C.; DIAL, R. B. (1996). A restricted dynamic programming heuristic algorithm for the time-dependent traveling salesman problem. European Journal of Operational Research 90, S. 45-55.

[23]    SOLOMON, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 2, Vol. 35 Issue 2, S. 254-265.