Quantitative Modellierung der Tourenplanung für Auslieferungen auf der Letzten Meile
Abbildungsverzeichnis
Tabellenverzeichnis
Abkürzungsverzeichnis
Symbolverzeichnis
1 Einleitung
1.1 Motivation
1.2 Problemstellung und Zielsetzung
1.3 Aufbau der Arbeit
2 Theoretische Grundlagen der Letzten Meile und der Tourenplanung
2.1 Logistik der Letzten Meile
2.1.1 Definition und Problematik der Logistik der Letzten Meile
2.1.2 Theoretische Gestaltungsformen der Letzten Meile
2.1.3 Praktische Anwendungen auf der Letzten Meile
2.1.4 Eigene Begriffsdefinitionen im Rahmen der Letzten Meile
2.2 Tourenplanung
2.2.1 Begriffe der Tourenplanung
2.2.2 Klassifikation von Tourenproblemen
2.2.3 Standardprobleme der Tourenplanung
2.2.4 Modellierung ausgewählter Tourenprobleme
2.3 Stand der Forschung zur Tourenplanung auf der Letzten Meile
3 Quantitative Modellierung der Auslieferungsplanung auf der Letzten Meile
3.1 Tourenplanung mit Hauszustellung (Grundmodell)
3.1.1 Rahmenbedingungen und Klassifikation
3.1.2 Modellanalyse
3.2 Tourenplanung mit Hauszustellung (Modifikation)
3.2.1 Veränderte Rahmenbedingungen und Klassifikation
3.2.2 Modifikation des Modells
3.3 Tourenplanung mit Schließfachsystemen
3.3.1 Rahmenbedingungen und Klassifikation
3.3.2 Modellentwicklung
4 Anwendungsbeispiel
4.1 Ausgangssituation
4.1.1 Gemeinsame Datenbasis
4.1.2 Ergänzende Daten für Hauszustellung
4.1.3 Ergänzende Daten für Schließfachsysteme
4.2 Berechnung und Ergebnisdarstellung
4.2.1 Tourenplanung mit Hauszustellung
4.2.2 Tourenplanung mit Schließfachsystemen
4.2.3 Sensitivität der Lösungen
4.3 Handlungsempfehlungen für die Logistik
5 Zusammenfassung und Ausblick
Literaturverzeichnis
Anhang
Anhang A: Excel-Tabellen
Anhang B: Gusek-Modelle
Quantitative Modellierung der Tourenplanung für Auslieferungen auf der Letzten Meile
Die Logistik der Letzten Meile mit konventionellen Zustellmethoden macht mehr als die Hälfte der gesamten Transportkosten aus. Aufgrund dieses hohen Anteils werden vermehrt Kostenoptimierungen durch alternative Zustellformen angestrebt. Ziel dieser Arbeit ist der quantitative Vergleich zweier Gestaltungsformen der Letzten Meile: Hauszustellung mit persönlicher Anwesenheit des Empfängers und Zustellung an gemeinsam genutzte Schließfachsysteme. Dazu wird ein bestehendes Modell für Tourenplanung mit Hauszustellung analysiert und dahingehend modifiziert, dass es eine Belieferung an Schließfachsysteme abbildet. Beide Modellvarianten werden auf ein Fallbeispiel angewendet. Die Ergebnisse zeigen, dass die Verwendung von Schließfachsystemen zu einer Reduktion der Logistikkosten auf der Letzten Meile führt, insbesondere bei einer hohen Anzahl von Kunden je Tour. Im Anwendungsbeispiel werden bei sieben Kunden je Tour bereits Kosteneinsparungen in Höhe von 37 % erzielt.
Quantitative vehicle routing models for last mile deliveries
The last mile logistics with conventional delivery methods accounts for more than half of the transport costs. This is why alternative delivery options are sought. The aim of this paper is the quantitative comparison of two last mile delivery concepts: attended home delivery and shared reception boxes. An existing model for vehicle routing with home delivery is being analysed and modified for the use of reception boxes. A case study is then calculated with both model variants. The results show that the use of receptions boxes leads to a reduction of last mile logistics costs, especially for a high amount of customers per tour. In the case study, cost savings of 37 % are achieved with seven customers each tour already.
Abbildung 1-1: Aufbau der Arbeit (eigene Darstellung)
Abbildung 2-1: Gestaltungsformen der Letzten Meile (eigene Darstellung)
Abbildung 2-2: Lockbox (Lockbox 23.03.2015)
Abbildung 2-3: Dabbawalas von Mumbai (MACKY 2015)
Abbildung 2-4: Paket-Drohne (Fuest 2013)
Abbildung 2-5: Innenstadtbelieferung aus Wechselbrücke (eigenes Foto 2015)
Abbildung 2-6: Cargohopper (Randelhoff 2015b)
Abbildung 2-7: Schwimmendes Verteilzentrum (Randelhoff 2015a)
Abbildung 2-8: Erweiterte Gestaltungsformen der Letzten Meile (eigene Darstellung)
Abbildung 2-9: Arten von Graphen (eigene Darstellung i. A. a. Domschke und Drexl 2005, S. 65)
Abbildung 2-10: Ungerichteter, nicht zusammenhängender Graph (eigene Darstellung)
Abbildung 3-1: Erklärung, warum bei Berücksichtigung von Ankunftszeiten keine Subtouren auftreten (eigene Darstellung)
Abbildung 4-1: Anordnung von Depot und Kunden (eigene Darstellung)
Abbildung 4-2: Anordnung von Depot, Kunden und Boxen (eigene Darstellung)
Abbildung 4-3: Touren im Anwendungsbeispiel mit Hauszustellung (eigene Darstellung)
Abbildung 4-4: Touren im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Abbildung 4-5: Zuordnung von Kunden zu Boxen und Fahrzeugen im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Abbildung 4-6: Anordnung von Depot, Kunden und Boxen mit verringertem Datensatz (eigene Darstellung)
Abbildung 4-7: Touren Hauszustellung (eigene Darstellung)
Abbildung 4-8: Touren sowie Zuordnung von Kunden zu Boxen und Fahrzeugen Schließfachsysteme (eigene Darstellung)
Abbildung 4-9: Touren bei verschieden großen Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Abbildung 4-10: Touren bei hoher Fahrzeugkapazität und verschieden großen Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Abbildung 4-11: Touren sowie Zuordnung von Kunden zu Boxen hohe Fahrzeugkapazität Schließfachsysteme (eigene Darstellung)
Abbildung 4-12: Touren sowie Zuordnung von Kunden zu Boxen und Fahrzeugen ohne Abholkosten Schließfachsysteme (eigene Darstellung)
Tabelle 2-1: Morphologischer Kasten zur Klassifikation von Tourenproblemen (eigene Darstellung)
Tabelle 4-1: Farbliche Kennzeichnung der Parameter und Variablen (eigene Darstellung)
Tabelle 4-2: Entfernungsmatrix Depot und Kunden (eigene Darstellung)
Tabelle 4-3: Nachfrage der Kunden (eigene Darstellung)
Tabelle 4-4: Bediendauer, Lieferzeitfenster und Verspätungskosten bei den Kunden und am Depot (eigene Darstellung)
Tabelle 4-5: Entfernungsmatrix Depot, Kunden und Boxen (eigene Darstellung)
Tabelle 4-6: Für die Boxen benötigte Parameter (eigene Darstellung)
Tabelle 4-7: Fahrzeugverwendung und Tourendauern im Anwendungsbeispiel mit Hauszustellung (eigene Darstellung)
Tabelle 4-8: Befahrene Kanten im Anwendungsbeispiel mit Hauszustellung (eigene Darstellung)
Tabelle 4-9: Verteilung der Fahrzeugkapazität im Anwendungsbeispiel mit Hauszustellung (eigene Darstellung)
Tabelle 4-10: Zeitliche Größen im Anwendungsbeispiel mit Hauszustellung (eigene Darstellung)
Tabelle 4-11: Kostenstruktur im Anwendungsbeispiel mit Hauszustellung (eigene Darstellung)
Tabelle 4-12: Fahrzeugverwendung und Tourendauern im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-13: Boxenverwendung im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-14: Befahrene Kanten im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-15: Zuordnung von Kunden zu Boxen und Fahrzeugen im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-16: Verteilung der Fahrzeugkapazität im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-17: Verteilung der Boxenkapazität im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-18: Zeitliche Größen im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-19: Kostenstruktur im Anwendungsbeispiel mit Schließfachsystemen (eigene Darstellung)
Tabelle 4-20: Vergleich der tatsächlich anfallenden Kosten im Anwendungsbeispiel (eigene Darstellung)
Tabelle 4-21: Tourendauern Hauszustellung (eigene Darstellung)
Tabelle 4-22: Tourendauern Schließfachsysteme (eigene Darstellung)
Tabelle 4-23: Zeitliche Größen bei größeren Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Tabelle 4-24: Zeitliche Größen bei kleineren Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Tabelle 4-25: Tourendauern bei verschieden großen Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Tabelle 4-26: Verteilung der Zeiten bei verschieden großen Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Tabelle 4-27: Zeitliche Größen bei hoher Fahrzeugkapazität und größeren Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Tabelle 4-28: Zeitliche Größen bei hoher Fahrzeugkapazität und kleineren Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Tabelle 4-29: Verteilung der Zeiten bei hoher Fahrzeugkapazität und verschieden großen Lieferzeitfenstern Hauszustellung (eigene Darstellung)
Tabelle 4-30: Tatsächliche Kosten bei verschiedener Fahrzeugkapazität und Lieferzeitfenstergröße Hauszustellung (eigene Darstellung)
Tabelle 4-31: Tourendauern bei verschiedener Fahrzeugkapazität Schließfachsysteme (eigene Darstellung)
Tabelle 4-32: Zusammensetzung der Gesamtkosten bei verschiedener Fahrzeugkapazität Schließfachsysteme (eigene Darstellung)
Tabelle 4-33: Tatsächliche Kosten bei verschieden hoher Fahrzeugkapazität (eigene Darstellung)
Tabelle 4-34: Tatsächliche Kosten bei verschiedener Anzahl von Kunden je Tour (eigene Darstellung)
Tabelle A-1: Datengrundlage für das Anwendungsbeispiel Teil 1/2 (eigene Darstellung)
Tabelle A-2: Datengrundlage für das Anwendungsbeispiel Teil 2/2 (eigene Darstellung)
Tabelle A-3: Optimale Lösung des Anwendungsbeispiels mit Hauszustellung (eigene Darstellung)
Tabelle A-4: Optimale Lösung des Anwendungsbeispiels mit Schließfachsystemen (eigene Darstellung)
Tabelle A-5: Datengrundlage für die Sensitivität der Lösungen (eigene Darstellung)
Abbildung in dieser Leseprobe nicht enthalten
Abbildung in dieser Leseprobe nicht enthalten
Der Versandhandel in Deutschland steht unter einem enormen Kostendruck. Trotz hoher Anforderungen an die Zuverlässigkeit der Lieferung erwarten zwei Drittel der Kunden kostenlose Zustellungen im Onlinehandel. Um dem Empfänger ein hohes Maß an Flexibilität zu ermöglichen, bieten viele Logistiker inzwischen die freie Wahl des Lieferzeitfensters an. Eine taggleiche Lieferung ist ebenfalls bei einigen Lieferdiensten möglich. (Rose 2013)
Einer Veröffentlichung des Forschungsinstituts für Rationalisierung (FIR) an der RWTH Aachen zufolge werden konventionelle Zustellungsmethoden aufgrund der folgend aufgeführten Trends immer mehr in Frage gestellt (Mucha et al. 2002, S. 3):
- vermehrtes Interesse am Online-Shopping
- zunehmende Erwerbstätigkeit beider Ehepartner
- steigende Anzahl von Single-Haushalten
- abnehmende Bedeutung der Nachbarschaft
Durch die starke Verbreitung von Laptops, Tablets und Smartphones erfährt der Internethandel ein steigendes Wachstum. 60 % der deutschen Verbraucher haben im Jahr 2013 mindestens einmal Produkte online erworben. (Morganti et al. 2014, S. 178 f.) Für viele Berufstätige ist es bequemer im Internet jenseits von Ladenöffnungszeiten einzukaufen. Gerade diese Zielgruppe ist jedoch zum Zeitpunkt der Zustellung oftmals nicht zu Hause anzutreffen. Die zunehmende Anonymität innerhalb der Nachbarschaft in Großstädten erschwert die Zustellung der Pakete zusätzlich. (Mucha et al. 2002, S. 3)
Für den Logistikdienstleister ist diese konventionelle Form der Zustellung mit hohen Kosten verbunden. Die Logistik der Letzten Meile im Paketversand macht etwa 55 % der Transportkosten aus. (Auffermann und Lange 2008, S. 532) Die starke Bedeutung des Themas wird auch dadurch deutlich, dass in Hamburg im Herbst 2014 ein Logistik-Beratungshaus speziell für die Letzte Meile gegründet wurde. Das Unternehmen mit dem Namen first mile entwickelt Lösungen für Hersteller, Einzelhandel, Städte und Kommunen sowie Transportdienstleister. (Herzog 2014)
Aufgrund der oben beschriebenen Problematik werden vermehrt alternative Gestaltungsformen der Letzten Meile angestrebt. Die Ansätze werden unterschieden in Zustellung mit und ohne Anwesenheit des Empfängers. Bei letztgenannter Variante können 60 % der Logistikkosten eingespart werden. (Punakivi et al. 2001, S. 433) Die Zustellung erfolgt dabei z. B. an auf dem Grundstück des Empfängers installierte Empfangsstationen. Die damit verbundenen Investitionskosten sind jedoch relativ hoch. (Punakivi et al. 2001, S. 428) Eine Alternative, die mit weniger Kosten für den Kunden verbunden ist, stellt die sogenannte Abholpunktbelieferung dar. Die Pakete werden in Kundennähe gebündelt und für die Abholung zur Verfügung gestellt. Durch die Konsolidierung von Sendungen können die Logistikkosten stark reduziert werden. Eine Zustellung ohne Anwesenheit des Empfängers bedeutet für den Kunden außerdem den Vorteil der höheren zeitlichen Flexibilität. (Auffermann und Lange 2008, S. 532)
In der Literatur existieren verschiedene Ausarbeitungen über die Logistik der Letzten Meile. Einige behandeln den Vergleich der oben vorgestellten Alternativen. Zumeist werden Kosteneinsparungen durch die Verwendung von Abholpunktbelieferung identifiziert. Es wird in der Literaturanalyse lediglich ein Werk gefunden, welches einen Vergleich auf Basis von quantitativer Modellierung vornimmt. Es handelt sich dabei um die Ausarbeitung von Wang et al. (2014). Die Autoren vergleichen drei verschiedene Gestaltungsformen der Letzten Meile bei unterschiedlich hoher Bevölkerungsdichte sowie Anzahl von Bestellungen. In der Arbeit wird allerdings lediglich eins der drei berücksichtigten Modelle vorgestellt.
In der vorliegenden Arbeit werden daher zwei Gestaltungsformen der Letzten Meile quantitativ modelliert und anschließend anhand eines Fallbeispiels miteinander verglichen. Ein bestehendes Modell aus der Literatur für Tourenplanung mit Hauszustellung bei persönlicher Anwesenheit des Empfängers wird analysiert und weiterentwickelt. Zum einen werden die Bezeichnungen für die Mengen, Variablen und Parameter in eine einheitliche und intuitive Form umgewandelt. Zum anderen werden weitere relevante Komponenten in das Modell integriert, wie z. B. die Berücksichtigung von Personalkosten für die Dauer einer Tour. Auf diese Weise wird der Vergleich der beiden Modellvarianten vereinfacht, da die Tourendauern in der Lösung möglichst kurz gehalten werden und direkt abgelesen werden können.
Im nächsten Schritt wird das Modell dahingehend modifiziert, dass es die Gestaltung der Letzten Meile mit einer Abholpunktbelieferung abbildet. Es wird dabei die Variante von gemeinsam genutzten Schließfachsystemen an öffentlich zugänglichen Plätzen gewählt. Diese bedeuten die höchste zeitliche Autonomie für den Empfänger, da er bei der Abholung an keinerlei Öffnungszeiten gebunden ist. (Wannenwetsch 2005, S. 323 ff.) Die räumliche Position der Kunden ist weiterhin wichtiger Bestandteil des Modells. Die Zuordnung von Kunden zu Schließfachsystemen erfolgt als Entscheidungsvariable. Dabei werden die Fahrtkosten der Kunden ebenfalls in der Zielfunktion berücksichtigt.
Beide Modellvarianten werden auf ein fiktives Fallbeispiel angewendet. Anschließend wird die Sensitivität der Lösungen auf die Variation einzelner Parameter geprüft. Dabei wird der Einfluss einzelner Größen, wie Lieferzeitfenster und Fahrzeugkapazität, auf das Ergebnis dargestellt. Aus den Untersuchungen werden Handlungsempfehlungen für die Logistik abgeleitet.
In Kapitel 2 dieser Arbeit werden die theoretischen Grundlagen erarbeitet. Zunächst werden die Logistik der Letzten Meile sowie ihre Gestaltungsmöglichkeiten analysiert. Zudem werden praktische Anwendungen auf der Letzten Meile vorgestellt. Anschließend folgt eine Einführung in das Thema der Tourenplanung. Nach einer Erläuterung der grundlegenden Begriffe wird ein Klassifikationsschema für Tourenplanungsprobleme erarbeitet. Anhand des Klassifikationsschemas werden einige Standardprobleme definiert und modelliert. Das Kapitel schließt mit einem Überblick über den Stand der Forschung zur Tourenplanung auf der Letzten Meile.
Kapitel 3 befasst sich mit der quantitativen Modellierung der Auslieferungsplanung auf der Letzten Meile. Es wird zunächst ein bestehendes Modell für Hauszustellung mit persönlicher Anwesenheit des Empfängers analysiert und den Standardproblemen aus Kapitel 2 gegenübergestellt. Das Modell wird dann an die gewünschten Anforderungen angepasst und anschließend so modifiziert, dass es eine Zustellung an Schließfachsysteme abbildet.
In Kapitel 4 erfolgt der Vergleich der beiden Gestaltungsformen anhand eines Fallbeispiels. Zunächst wird die Ausgangssituation definiert. Anschließend werden die Modelle implementiert und auf das Anwendungsbeispiel angewendet. Nach der Interpretation der Ergebnisse wird die Sensitivität der Lösungen untersucht. Dazu werden einzelne Parameter variiert. Aus den Ergebnissen werden Handlungsempfehlungen für die Logistik abgeleitet.
Die Arbeit schließt mit einer Zusammenfassung sowie einem Ausblick auf zukünftige Untersuchungen in Kapitel 5.
Abbildung 1-1 fasst den Aufbau der Arbeit zusammen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1-1: Aufbau der Arbeit (eigene Darstellung)
Dieses Kapitel umfasst die für diese Arbeit relevanten theoretischen Grundlagen. Als erstes wird die Logistik der Letzten Meile genauer analysiert. Der anschließende Abschnitt befasst sich mit Problemen der Tourenplanung. Neben einer Klassifizierung werden Standardprobleme vorgestellt und modelliert. Abschließend erfolgt ein Überblick über den Stand der Forschung zur Tourenplanung auf der Letzten Meile.
In diesem Abschnitt wird die Logistik der Letzten Meile definiert und ihre Problematik aufgezeigt. Anschließend werden die Gestaltungsformen der Letzten Meile aus der Literatur vorgestellt. Aufgrund der hohen Aktualität des Themas sind einige praktische Anwendungsfelder für Auslieferungen auf der Letzten Meile zum Zeitpunkt der Recherche nicht in der Literatur zu finden. Diese werden in einem eigenen Unterkapitel behandelt. Schließlich wird die Verwendung von Begriffen im Rahmen dieser Arbeit festgelegt.
Die Logistik der Letzten Meile behandelt das finale Segment der Lieferkette, also die Zustellung der Waren vom letzten regionalen Verteildepot zum Endkunden. (Wannenwetsch 2005, S. 322) Damit unterscheidet sich die Letzte Meile vom stationären Handel, bei welchem der Kunde den Transport der Waren selbst durchführt. (Petrovic et al. 2013, S. 53)
Wegen der Atomisierung von Sendungen bedingt durch den E-Commerce stehen hohe Transportkosten einem geringen Auftragsvolumen gegenüber. Während die herkömmliche Logistik für wenige Sendungen mit hoher Stückzahl ausgelegt ist, erfolgen bei der Logistik der Letzten Meile Klein- und Kleinstsendungen an weit verstreute Senken. Die Lieferungen werden in der Regel mit Kurier-, Express- und Paketdiensten (KEP) ausgeführt. Die Kosten der Letzten Meile machen im KEP-Markt etwa 55 % der Transportkosten aus. Dies ist zum einen durch die Atomisierung von Sendungen und die daraus resultierende hohe Stoppzahl begründet. Zum anderen erfordert die Zustellung viel Zeit für Parkplatzsuche, Suche der richtigen Adresse, Klingeln, Warten, Treppensteigen, Aushändigen der Sendung und Quittieren durch den Empfänger. Ein weiterer Einflussfaktor auf die Kosten ist die Tatsache, dass Kunden bei der Anlieferung an die Haustür häufig nicht anzutreffen sind und somit mehrere Zustellversuche erforderlich sind. Aus diesem Grund werden Alternativen zur Anlieferung an die Haustür gesucht. (Auffermann und Lange 2008, S. 531 f.) Diese Alternativen sowie die Hauszustellung selbst behandelt das folgende Kapitel.
Bei der Gestaltung der Logistik der Letzten Meile wird zwischen Hausbelieferung und Abholpunktbelieferung unterschieden. Hausbelieferung oder auch Heimlieferung bezeichnet die Zustellung von Produkten in den Haushalt des Endkunden. Dies setzt die Anwesenheit des Kunden voraus. Daher wird häufig ein Lieferzeitfenster vereinbart. Eine Alternative zur Lieferung an die Haustür bietet der gesicherte Abstellplatz. Hierbei handelt es sich um eine gesicherte Box auf dem Grundstück des Empfängers, zu der der Lieferant Zugriff hat. Auch ein verschließbarer Raum, wie eine Garage oder ein Schuppen im Garten, kann als gesicherter Abstellplatz fungieren. (Klaus et al. 2012, S. 311 f.; Klaus et al. 2012, S. 225)
Bei der Abholpunktbelieferung werden die Waren an einen zuvor vereinbarten Ort geliefert. Der Kunde holt die Sendung zu einem selbstgewählten Zeitpunkt ab. Durch die Bündelung der Verkehre werden die Logistikkosten der Letzten Meile stark reduziert. Darüber hinaus ist eine erfolgreiche Zustellung im ersten Anlauf gewährleistet. Für den Kunden ergibt sich der Vorteil der zeitlichen Souveränität, da er den Abholzeitpunkt selbst bestimmen kann. (Klaus et al. 2012, S. 311; Auffermann und Lange 2008, S. 532)
Die Abholpunktbelieferung selbst wird wieder in zwei Gestaltungsformen unterteilt. Hierbei handelt es sich um Paketshops und um Schließfachsysteme. Paketshops sind öffentlich zugängliche Einrichtungen wie Tankstellen oder Kioske, die die Lieferung für den Kunden entgegennehmen. Diese Lösung zeichnet sich durch eine einfache Implementierung aus, bedeutet für den Kunden aber eine Bindung an die Öffnungszeiten des Paketshops. Schließfachsysteme befinden sich an öffentlich zugänglichen Stellen. Die Kunden erhalten in der Regel mittels einer Geheimnummer Zugang zu ihrer Lieferung. Diese Variante bedeutet für den Kunden die größte zeitliche Autonomie, da er an keine Öffnungszeiten gebunden ist. Jedoch sind die Investitionskosten für ein Schließfachsystem relativ hoch. (Wannenwetsch 2005, S. 323 ff.) Das größte Netz von Schließfachsystemen bildet die Deutsche Post DHL mit der Packstation. (Morganti et al. 2014, S. 185)
In Abbildung 2-1 werden die oben vorgestellten Gestaltungsformen noch einmal zusammengefasst.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-1: Gestaltungsformen der Letzten Meile (eigene Darstellung)
Weitere Gestaltungsformen der Letzten Meile, die zum Zeitpunkt der Recherche nicht in der Literatur zu finden sind, werden im folgenden Unterkapitel vorgestellt.
Dieser Abschnitt behandelt einige Projekte, die die Logistik der Letzten Meile thematisieren. Der Realisierungsgrad der einzelnen Projekte reicht von bereits etablierten Verfahren über Pilotprojekte bis hin zu Zukunftsvisionen. Die Auswahl der vorgestellten Projekte erhebt keinen Anspruch auf Vollständigkeit. Vielmehr verdeutlicht die Vielzahl von unterschiedlichen Herangehensweisen an die Logistik der Letzten Meile die starke Bedeutung dieses Themas.
Die Projekte lassen sich hinsichtlich ihrer Zielsetzungen in zwei grundlegende Richtungen gruppieren. Zum einen gibt es jene Projekte, die die Steigerung der Kundenzufriedenheit fokussieren. Die Abwicklung der Letzten Meile soll für den Kunden so bequem oder so schnell wie möglich gestaltet werden. So werden Wege gesucht, die für den Kunden wenig Aufwand, hohe zeitliche Flexibilität oder eine besonders schnelle Lieferung bedeuten. Zur zweiten Kategorie zählen solche Projekte, die eine Verbesserung der Verkehrssituation im Stadtverkehr zum Ziel haben. Bei diesen Projekten werden Sendungen gebündelt und auf alternative Weise, z. B. zu Fuß oder per Lastenrad, verteilt.
Es werden zunächst die Projekte der beiden Kategorien vorgestellt. Dabei werden jeweils die Unterscheidungsmerkmale gegenüber den theoretischen Gestaltungsformen der Letzten Meile aus der Literatur hervorgehoben. Im Anschluss werden die neu erarbeiteten Gestaltungsformen in die Übersicht aus Abbildung 2-1 aufgenommen.
Projekte zur Verbesserung der Kundenzufriedenheit
Für den Kunden bedeutet die Lieferung an die Haustür den geringsten Aufwand. Allerdings erfordert dies eine Abstimmung und zeitliche Bindung. Um die Lieferung flexibel zu gestalten und Fehlzustellungen zu vermeiden, haben einige Unternehmen an der Haustür installierte Empfangsstationen entwickelt. Dabei handelt es sich z. B. um das Unternehmen Lockbox, bei dem eine Kiste mithilfe eines Metallankers an der Wohnungstür fixiert wird. Das Konzept wird in Abbildung 2-2 dargestellt. Der Anker lässt sich nur bei geöffneter Wohnungstür entfernen. Auch die Deutsche Post DHL erprobt ein solches Konzept: Der Paketbutler ist eine faltbare Box, die mit einem Sicherheitsgurt an der Tür befestigt wird. (Hüsing 2015; Lockbox 23.03.2015; Lebensmittel Zeitung 2014)
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-2: Lockbox (Lockbox 23.03.2015)
Bezogen auf die in Kapitel 2.1.2 vorgestellten Gestaltungsformen der Letzten Meile lassen sich Projekte dieser Art zwischen Lieferung an die Haustür und gesicherter Abstellplatz einsortieren. Zwar werden die Waren an die Haustür geliefert, jedoch ist die Anwesenheit des Empfängers nicht erforderlich. Die an der Haustür installierten Empfangsstationen unterscheiden sich ebenfalls vom gesicherten Abstellplatz, da bei diesem lediglich ein bereits bestehender Raum umfunktioniert wird und keine eigene Installation erfolgt. Weiter ist die Variante des gesicherten Abstellplatzes eher für Einfamilienhäuser geeignet, während an der Haustür installierte Empfangsstationen auch in Mehrfamilienhäusern realisiert werden können.
Der Paketkasten stellt eine größere Variante von an der Haustür installierten Empfangsstationen dar. Seit Mai 2014 installiert die deutsche Post DHL auf Wunsch Paket-Briefkästen auf den Grundstücken ihrer Kunden. Der DHL-Paketkasten kann gegen Gebühr gemietet oder käuflich erworben werden. Zur Zielgruppe gehören überwiegend Ein- und Zweifamilienhäuser. (Deutsche Post DHL 12.05.2014) Während der Paketkasten ausschließlich für Zusteller von DHL verfügbar ist, entwickeln Hermes, DPD und GLS zurzeit ein anbieterunabhängiges System. Ab Sommer 2016 sollen Kunden einen neutralen Paketkasten namens Parcellock auf ihrem Grundstück installieren können. Auf diesen können neben allen Paketdiensten auch Privatpersonen oder beispielsweise Pizza-Lieferdienste zugreifen können. (Kannenberg 2015)
Das Unternehmen Cardrops fokussiert mit seinem Konzept ebenfalls die Steigerung der Kundenflexibilität. So werden Kunden in den Kofferraum des eigenen Autos beliefert. Dafür ist ein Softwareschlüssel erforderlich, mit dem der Lieferant den Kofferraum einmalig öffnen kann. Der Standort des Fahrzeugs wird mit GPS-Daten geortet. Der Kunde kann also an einem beliebigen Ort beliefert werden, z. B. an seinem Arbeitsplatz. Dies geht ohne Beeinträchtigung der Arbeitszeit vonstatten. (Biggs 2012) Der Automobilhersteller Volvo absolvierte ebenfalls erfolgreich ein Pilotprojekt zur Kofferraumbelieferung. (Weißenborn 2014) Diese Projekte zählen im weitesten Sinne zur Abholpunktbelieferung. Sie werden als eigene Unterkategorie Kofferraumbelieferung aufgenommen.
Das nächste Projekt gehört in die Kategorie der Schließfachsysteme. Bei emmasbox handelt es sich um Abholstationen mit drei verschiedenen Kühlzonen. Kunden können online bestellte Lebensmittel an diese Stationen liefern lassen. Nach einer Pilotphase im Herbst 2014 ist die Markteinführung für Frühjahr 2016 geplant. Die ersten Stationen von emmasbox sollen in Linz und Wien in Österreich errichtet werden. (Steindorfer 2015) Die Kategorie Schließfachsysteme wird um eine weitere Unterkategorie gekühlte Schließfachsysteme erweitert.
Die bisher vorgestellten Projekte sind überwiegend auf den Versand- oder Onlinehandel ausgelegt. Das nächste Projekt hingegen dient der Unterstützung des stationären Handels. Die Firma Atalanda verspricht schnellere Lieferungen als im Onlinehandel. Dabei nutzt sie die Tatsache, dass die Produkte in den Geschäften einer Stadt bereits vorhanden sind, während sie im Onlinehandel teilweise weite Wege aus dem nächsten Distributionszentrum zurücklegen müssen. Im Local-Shopping-Portal Atalanda können die Produkte lokaler Händler online erworben werden. Die Lieferung erfolgt dann taggleich durch die Logistikplattform Atalogics. Dabei werden die Fahrten in einem Netzwerk aus Kurieren, ähnlich wie bei der App Mytaxi, angeboten. (Hell 2014a) Der Dienst wird bisher in Deutschland in Hamburg und Wuppertal sowie in Österreich in Salzburg angeboten. (Atalanda o. J.)
Ein ähnliches Konzept bietet das Start-up Tiramizoo an. Dieser Dienst liefert in 18 Städten in Deutschland aus dem lokalen Handel und verspricht Lieferungen innerhalb von 90 Minuten. (Hell 2014b) Bezüglich der Gestaltungsformen der Letzten Meile lassen sich diese Projekte als Lieferung an die Haustür klassifizieren. Der Unterschied liegt darin, dass die Lieferung taggleich und aus dem stationären Handel erfolgt. In die Liste der Gestaltungsformen wird eine weitere Unterscheidung nach der Quelle der Auslieferung aufgenommen. Regulär erfolgt die Lieferung aus einem regionalen Verteildepot. (Wannenwetsch 2005, S. 320) Es wird folgend zusätzlich die Lieferung aus dem stationären Handel unterschieden.
In einem weiteren Projekt wird die Lieferung von Elektronikartikeln mit dem Taxi getestet. Die Betreiber der Mytaxi-App kooperieren in Hamburg mit dem Elektronikhändler Media Markt. Kunden können bei ihrer Onlinebestellung die taggleiche Lieferung mit einem Taxi wählen. Die Taxifahrer können die Aufträge dann in der App entgegennehmen. (Donath 2013) Bei diesem Konzept handelt es sich um die Gestaltungsform Lieferung an die Haustür. Es unterscheidet sich jedoch durch die Art der Lieferungsausführung. Die Kategorie Lieferung an die Haustür wird um die zusätzliche Angabe der Art der Auslieferung erweitert. Für dieses Projekt und alle folgenden, bei denen die Auslieferung anders als regulär per Lkw erfolgt, wird die Art der Auslieferung auch ohne explizite Erwähnung in die Gestaltungsformen aufgenommen.
Das Start-up SHIPPIES organisiert die Letzte Meile wiederum auf eine andere Art. Ähnlich wie bei Portalen zur Mitfahrgelegenheit werden bei diesem Mitbringservice Lieferungen von Privatpersonen ausgeführt. Der Dienst startet zunächst als Pilotprojekt in Frankfurt am Main. In Österreich und Schweden gibt es mit Checkrobin und Myways bereits ähnlich Dienste. (Bach 2014) Dieses Projekt gehört ebenfalls zur Lieferung an die Haustür mit einer weiteren Art der Auslieferung, in diesem Fall per Privatperson.
Eine ungewöhnliche Art der Lieferung nutzt der Onlinehändler Amazon in New York. Können die Expresslieferzeiten von einer oder zwei Stunden im Autoverkehr nicht eingehalten werden, so nutzen Zusteller stattdessen die U-Bahn. Laut den Verkehrsbetrieben werde dies akzeptiert, solange andere Fahrgäste nicht beeinträchtigt werden. (Donath 2015)
Der indische Onlinehändler Flipkart wählt wiederum einen anderen Ansatz für die Gestaltung der Letzten Meile. Er nutzt das in Mumbai einzigartige System der Dabbawalas. (Chandran 2015) Dabbawalas versorgen seit über hundert Jahren täglich etwa 200.000 Studenten, Büroangestellte und Fabrikarbeiter mit Mittagessen. Vormittags sammeln die Dabbawalas das von den Hausfrauen zubereitete Essen in Metallbehältern ein. (Roncaglia 2013, S. xv) Dabei sollen sie ab sofort gleichzeitig Waren für Flipkart ausliefern. (Chandran 2015) Abbildung 2-3 zeigt zwei Dabbawalas im Straßenverkehr von Mumbai.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-3: Dabbawalas von Mumbai (MACKY 2015)
Beim letzten Projekt in dieser Kategorie handelt es sich um eine Zukunftsvision. Im Dezember 2013 kündigte der Onlinehändler Amazon bereits Paketlieferungen mit einer Drohne an. Von der Öffentlichkeit wurde diese Nachricht als PR-Aktion zur Weihnachtszeit aufgenommen. Kurz darauf führte die Deutsche Post DHL in Bonn erste Versuche zur Belieferung mit Drohnen durch. Ein knapp ein Kilogramm schweres Paket mit Medikamenten wurde über eine Distanz von zwei Kilometern ausgeliefert. Ein Auto hätte für diese Lieferung sechs Kilometer im Stadtverkehr zurücklegen müssen und deutlich länger gebraucht. Paket-Drohnen eignen sich für den Apothekenversand, da sich dieser durch geringe Gewichte und meist kurze Distanzen auszeichnet. Rechtliche Fragen sind noch ungeklärt, insbesondere den Versand von rezeptpflichtigen Medikamenten betreffend. (Fuest 2013) Dennoch wird die Paketzustellung mit Drohnen in Testgebieten bereits realisiert. So erfolgt die Medikamentenversorgung der deutschen Nordseeinsel Juist seit Ende 2014 per Paket-Drohne. Auch in Finnland werden seit September 2015 bis zu drei Kilogramm schwere Pakete per Drohne auf die Insel Suomenlinna geliefert. (Stern 2015) In Abbildung 2-4 ist eine Paket-Drohne von DHL zu sehen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-4: Paket-Drohne (Fuest 2013)
Projekte zur Verbesserung der Verkehrssituation
Bei den folgend vorgestellten Projekten gilt die überwiegende Zielsetzung den Stadtverkehr zu entlasten. So haben z. B. die Stadt Hamburg und das Logistikunternehmen UPS ein Konzept zur Innenstadtbelieferung entwickelt. Seit 2012 stellt UPS jeden Morgen eine mit Paketen beladene Wechselbrücke in der Innenstadt auf. Von dort aus verteilen UPS-Mitarbeiter die Pakete zu Fuß mit einer Sackkarre oder mit einem Lastenrad. Auf diese Weise können täglich drei bis vier Lkw-Liefertouren mit rund 350 Stopps eingespart werden. (Randelhoff 2015a) Abbildung 2-5 zeigt das Konzept zur Belieferung der Hamburger Innenstadt. Für die Gestaltungsformen der Letzten Meile ergeben sich zwei weitere Auslieferungsformen der Lieferung an die Haustür: per Sackkarre und per Lastenrad. Die Wechselbrücke als vorgeschaltetes Sammel- und Verteilzentrum wird als weitere Quelle der Auslieferung aufgenommen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-5: Innenstadtbelieferung aus Wechselbrücke (eigenes Foto 2015)
Ein ähnliches Konzept wird mit der BentoBox in Berlin realisiert. Dabei handelt es sich um ein Schließfachsystem mit modularen Kleincontainern, aus welchem die Auslieferungen per Lastenrad erfolgen. Der Unterschied zum Konzept der Stadt Hamburg und UPS besteht darin, dass die BentoBox ein betreiberunabhängiges System ist. Unternehmen sowie Privatpersonen können Lieferungen über die BentoBox versenden oder empfangen. (CITYLOG 2012) Je nach Anwendung gehört dieses Konzept in die Kategorie Lieferung an die Haustür aus einer vorgeschalteten Sammelstelle, in diesem Fall einem Schließfachsystem. Nutzt eine Privatperson die BentoBox, um dort Lieferungen zu empfangen, so handelt es sich um eine Abholpunktbelieferung über ein Schließfachsystem.
In der niederländischen Stadt Utrecht gibt es ein solches Verteilzentrum am Stadtrand bereits seit 1996. Lieferungen in den Innenstadtbereich werden vom Sammelpunkt aus mit einem Elektroschleppzug verteilt. Dieser als Cargohopper bezeichnete Elektroschleppzug ist in Abbildung 2-6 zu sehen. Motivation für dieses Projekt war die Einrichtung einer Umweltzone in Kombination mit Gewichtsbeschränkungen im Stadtgebiet. Durch die Distribution mit dem Cargohopper werden jährlich über 100.000 km Lkw-Fahrten im Innenstadtbereich eingespart. (Randelhoff 2015b)
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-6: Cargohopper (Randelhoff 2015b)
In Amsterdam nutzt DHL ein Boot zur Verteilung von Briefen und Paketen im Innenstadtbereich. Im Jahre 1997 wurde das Fahrverbot für Güterschiffe auf den Grachten aufgehoben. Seitdem setzt DHL ein schwimmendes Verteilzentrum ein, wie in Abbildung 2-7 zu sehen. Das Boot befährt die insgesamt 80 km langen Kanäle, die die Innenstadt in mehreren Ringen erschließen. Die Feindistribution erfolgt dann mit Fahrradkurieren. Von den zehn zuvor eingesetzten Lieferfahrzeugen im Innenstadtbereich können durch die Verwendung des Bootes acht Stück eingespart werden. (Randelhoff 2015a) Das schwimmende Verteilzentrum wird als weitere Quelle der Auslieferung aufgenommen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-7: Schwimmendes Verteilzentrum (Randelhoff 2015a)
Die bisher vorgestellten Projekte dieser Kategorie betreffen überwiegend den Versand- oder Onlinehandel. Abschließend folgen zwei Projekte, die sich auf den stationären Handel beziehen. Die Besonderheit liegt darin, dass die Kunden die Waren zwar vor Ort erwerben, diese ihnen jedoch anschließend vom Händler zugestellt werden. Dabei kommen Lastenfahrräder zum Einsatz. So liefert beispielsweise IKEA in Hamburg-Altona die Einkäufe der Kunden auf Wunsch innerhalb eines definierten Gebiets mit dem Lastenrad aus. (IKEA Deutschland 2014) Ebenso können Kunden im INTERSPAR in Salzburg ihre Einkäufe in einer Lieferbox deponieren. Die Einkäufe werden ihnen dann von Jugendlichen, welchen auf diese Weise Zugang zum Arbeitsmarkt geboten wird, per Lastenrad nach Hause geliefert. (INTERSPAR 07.03.2013)
In Abbildung 2-8 werden die Gestaltungsformen der Letzten Meile aus der Literatur um die in diesem Abschnitt erarbeiteten praktischen Anwendungen ergänzt. Dabei sind die Änderungen gegenüber den Gestaltungsformen aus der Literatur in blau hervorgehoben.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-8: Erweiterte Gestaltungsformen der Letzten Meile (eigene Darstellung)
Die große Anzahl an unterschiedlichen Herangehensweisen zeigt das Potential der Gestaltung der Letzten Meile auf.
An dieser Stelle erfolgt eine Übersicht, wie die Ausdrücke im Rahmen der vorliegenden Arbeit verstanden werden. Grund dafür ist, dass die Definitionen einiger Begriffe in der Literatur voneinander abweichen, bzw. in unterschiedlichen Sprachen vorliegen und daher nicht einwandfrei zugeordnet werden können.
Mit dem Begriff Letzte Meile ist die Logistik der Letzten Meile gemeint, welche die Auslieferung von Waren thematisiert. Andere Gebiete, in denen dieser Begriff verwendet wird, werden nicht betrachtet. Hierzu zählen z. B. Strom- und Gasversorgung, Telekomunikation oder Personenbeförderung.
Im Modellierungsteil dieser Arbeit in Kapitel 3 sowie im Anwendungsbeispiel in Kapitel 4 werden zwei verschiedene Gestaltungsformen der Letzten Meile untersucht. Es handelt sich dabei um die in Kapitel 2.1.2 vorgestellten Varianten Lieferung an die Haustür und Schließfachsysteme. Bei der Lieferung an die Haustür wird die persönliche Anwesenheit des Empfängers vorausgesetzt. Es wird dafür im Folgenden der Begriff Hauszustellung verwendet. Grund dafür ist, dass dieser Ausdruck kürzer und daher für eine häufige Verwendung besser geeignet ist. Daher wird auch auf die zusätzliche Benennung der persönlichen Anwesenheit verzichtet. Unter dem Begriff Hauszustellung wird in der vorliegenden Arbeit Lieferung an die Haustür mit persönlicher Anwesenheit des Empfängers verstanden.
Mit Schließfachsystemen sind gemeinsam genutzte Schließfachsysteme an öffentlich zugänglichen Orten gemeint, wie in Kapitel 2.1.2 beschrieben. Im Modellierungsteil dieser Arbeit wird für Schließfachsystem auch der kürzere Ausdruck Box verwendet. Dieser leitet sich von dem in der englischsprachigen Literatur verwendeten Begriff reception box ab. Für die Mengen, Parameter und Variablen, die die Schließfachsysteme betreffen, wird daher der Buchstabe B verwendet.
„Die Aufgabenstellung der Tourenplanung besteht darin, innerhalb einer vorgegebenen Planungsperiode Transportaufträge mit geringen Sendungsmengen ... hinsichtlich einer Zielvorgabe zu Touren zusammenzufassen, so dass jede Tour mit einem am Depot positionierten Fahrzeug durchgeführt werden kann.“ (Rieck 2008, S. 7) Dabei ist für jede Tour die optimale Bearbeitungsreihenfolge der Aufträge zu ermitteln. (Rieck 2008, S. 7) Die Logistik der Letzten Meile erfordert die Organisation einer Fahrzeugflotte mittels Tourenplanung. (Masmoudi et al. 2014, S. 360)
Es werden zunächst einige Begriffe definiert, die für die Tourenplanung benötigt werden. Weiter erfolgt eine Klassifikation von Problemen der Tourenplanung. Anschließend werden unter Berücksichtigung des Klassifikationsschemas einige Standardprobleme vorgestellt. Schließlich erfolgt eine quantitative Formulierung zweier Standardprobleme als Grundlage für die Modellierung in Kapitel 3.
Die Begriffe Problem und Modell werden in der Literatur häufig synonym verwendet. Auch wenn keine praktischen Probleme, sondern deren vereinfachte Modelle gemeint sind, haben sich Begriffe wie Transportprobleme oder Probleme der Tourenplanung etabliert. (Domschke 2007, S. 18) Für Probleme der Tourenplanung wird im Folgenden auch der kürzere Ausdruck Tourenprobleme verwendet. Dies geschieht in Anlehnung an Domschke und Scholl (2010, S. 197).
Die untersuchten Tourenprobleme basieren jeweils auf einem zusammenhängenden, bewerteten Graphen G = (V, E), bestehend aus einer Knotenmenge V = {0, 1,..., n} und einer Kanten- oder Pfeilmenge E. Die Buchstaben V und E leiten sich von den englischen Begriffen vertices für Knoten und edges für Kanten ab. Jedem Element aus E wird genau ein Knotenpaar i und j aus V zugeordnet. G kann ungerichtet, gerichtet oder gemischt sein. Ein Graph wird als ungerichtet bezeichnet, wenn die Knotenpaare nicht angeordnet sind. Die Elemente von E heißen dann Kanten. Eine Kante verbindet zwei Knoten miteinander, ohne eine Richtung vorzugeben. Bei einem gerichteten Graphen hingegen sind die Knotenpaare geordnet. Dadurch wird eine Richtung von i nach j festgelegt. Die Elemente von E heißen dann Pfeile. (Domschke und Scholl 2010, S. 198; Domschke und Drexl 2005, S. 65; Werners 2013, S. 177 f.) Schließlich wird ein Graph als gemischt bezeichnet, wenn er sowohl Kanten als auch Pfeile aufweist. (Domschke und Scholl 2010, S. 169) Abbildung 2-9 zeigt je ein Beispiel für einen ungerichteten, einen gerichteten und einen gemischten Graphen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-9: Arten von Graphen (eigene Darstellung i. A. a. Domschke und Drexl 2005, S. 65)
Ein ungerichteter oder gerichteter Graph heißt zusammenhängend, wenn je zwei beliebige Knoten i und j miteinander verbunden sind. (Domschke 2007, S. 3) Ein gerichteter Graph heißt schwach zusammenhängend, wenn je zwei Knoten i und j miteinander verbunden sind, stark zusammenhängend, wenn sowohl j von i aus als auch i von j aus erreichbar ist. (Werners 2013, S. 187) Die Graphen in Abbildung 2-9 sind zusammenhängend bzw. schwach zusammenhängend. Abbildung 2-10 zeigt ein Beispiel für einen ungerichteten Graphen, welcher nicht zusammenhängend ist. Knoten 7 ist isoliert und von keinem anderen Knoten aus erreichbar. Daher ließe sich ein für diesen Graphen formuliertes Tourenproblem nicht lösen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2-10: Ungerichteter, nicht zusammenhängender Graph (eigene Darstellung)
Die den Tourenproblemen zugrundeliegenden Graphen weisen Kanten- oder Pfeilbewertungen cij auf. Diese liefern Informationen über die Längen, Fahrzeiten oder Fahrtkosten auf den einzelnen Kanten bzw. Pfeilen. Die Graphen besitzen außerdem Knotenbewertungen. Möglich sind hierbei z. B. Bedarfe bi oder Servicezeiten szi von Kunden. (Domschke und Scholl 2010, S. 198)
Im Graphen gibt es einen Knoten, der den Start- und Endpunkt für die Auslieferungs- oder Sammelfahrten bildet. Dieser wird als Depot bezeichnet. In der Regel repräsentiert Knoten 0 das Depot und hat keinen Bedarf (b0 = 0). Mögliche Verwendungszwecke von Depots sind Auslieferungslager, Sammellager oder Fahrzeugdepots. Bei einem Eindepotproblem wird vorausgesetzt, dass alle Fahrten am Depot beginnen und enden. (Domschke und Scholl 2010, S. 198)
Eine Tour wird durch die Menge aller Kunden und Kanten bzw. Pfeile gebildet, die auf einer im Depot beginnenden und endenden Fahrt bedient werden. Die Reihenfolge, in der die Kunden einer Tour angefahren werden, heißt Route. Ein Tourenplan ist eine zulässige Lösung des Tourenproblems. Er besteht aus der Menge von Touren und damit einhergehenden Routen, bei der alle Bedingungen des Problems erfüllt sind. (Domschke und Scholl 2010, S. 198 f.)
In diesem Kapitel wird ein Klassifikationsschema zur Beschreibung von Tourenproblemen vorgestellt. Das Schema basiert auf den Ausführungen von Domschke und Scholl (2010) unter Berücksichtigung der Arbeit von Desrochers et al. (1990).
Zur Klassifikation werden die folgenden vier Hauptcharakteristiken unterschieden (Domschke und Scholl 2010, S. 200):
α Depot- und Kundencharakteristik
β Fahrzeugcharakteristik
γ Problem- oder Zusatzcharakteristik
δ Zielsetzung
Darüber hinaus schlagen Desrochers et al. (1990) die Aufnahme einer fünften Kategorie vor. Diese liefere zusätzliche Informationen über die Umstände des Problems. So könne z. B. die durchschnittliche Anzahl der von einem Fahrzeug zu bedienenden Kunden angegeben werden. Eine genauere Darstellung dieser Kategorie stellen die Autoren jedoch zurück, bis die Entwicklung des Systems weiter fortgeschritten sei. (Desrochers et al. 1990, S. 323) Da diese fünfte, noch unausgereifte Kategorie in dem jüngeren Werk von Domschke und Scholl (2010) keine Anwendung findet, wird auch im Rahmen der vorliegenden Arbeit darauf verzichtet.
Jede der vier Hauptcharakteristiken verfügt über eine Menge von Attributen bzw. Merkmalen. Für die Merkmale gibt es verschiedene Ausprägungsformen. Diese werden durch Symbole oder Kürzel repräsentiert. Für die Ausprägung mit dem häufigsten Vorkommen wird dabei jeweils das Symbol ○ verwendet. Durch die Angabe der einzelnen Attributausprägungen lässt sich jedes Tourenproblem beschreiben. Dabei wird ein 4-Tupel der Form [α│β│γ│δ] verwendet. Die Einträge ○ werden jeweils ausgelassen. (Domschke und Scholl 2010, S. 200) Bei mehreren Angaben innerhalb einer Charakteristik werden Kommata als Trennzeichen verwendet.
Es folgt eine Vorstellung der Merkmale und Ausprägungen der vier Hauptcharakteristiken. Anschließend werden die Informationen in Tabelle 2-1 zusammengefasst.
Depot- und Kundencharakteristik
In dieser Kategorie werden sieben Merkmale unterschieden. Das erste Merkmal betrifft die Anzahl der vorhandenen Depots (α1). Möglich sind ein Depot oder eine gegebene Anzahl von p Depots. Im zweiten Merkmal wird die Art des Bedarfs (α2) untersucht. In der Standardausprägung ○ entsteht der Bedarf in den Knoten des Graphen. In dem Fall liegt ein knotenorientiertes Problem vor. Entsteht der Bedarf auf den Kanten des Graphen, so handelt es sich um ein kantenorientiertes Problem. Eine Kombination aus Bedarf in den Knoten und auf den Kanten ist ebenfalls möglich. Schließlich sind in der vierten Ausprägungsform Güter von einem Ort zu einem anderen Ort zu transportieren. (Domschke und Scholl 2010, S. 200)
Das nächste Attribut α3 gibt Auskunft darüber, ob die Nachfrage eines Kunden mit einer einzigen Bedienung erfüllt werden muss oder ob Teillieferungen erlaubt sind. Mit α4 wird die Art der Bedienung differenziert. In der Standardausprägung werden Güter zu Kunden geliefert oder bei ihnen abgeholt. Die zweite Ausprägungsform weist eine Kombination aus Belieferung und Abholung auf. Diese Form wird in der englischsprachigen Literatur als pickup and delivery bezeichnet. (Domschke und Scholl 2010, S. 200)
Das Merkmal α5 gibt Auskunft über zeitliche Beschränkungen hinsichtlich der Bedienung. Die Standardausprägung sieht keine zeitlichen Restriktionen vor. Möglich ist hingegen auch ein fest vorgeschriebener Bedienzeitpunkt (fixed schedule) oder ein vorgegebenes Zeitfenster (time window), innerhalb dessen ein Kunde bedient werden muss. Bei einem weichen Zeitfenster (soft time window) ist eine Bedienung außerhalb des Zeitfensters möglich, hat aber Strafkosten zur Folge. Schließlich ist die Verwendung mehrerer Zeitfenster (multiple time windows) möglich. (Domschke und Scholl 2010, S. 201)
Ferner wird mit α6 unterschieden, ob die Kunden in einer vorgegebenen Reihenfolge bedient werden müssen oder nicht. Schließlich werden Tourenprobleme bezüglich der Depot- und Kundencharakteristik dahingehend unterschieden, ob alle Kunden oder nur eine Auswahl bedient werden müssen. Hierzu werden die Attribute α7 bei knotenorientierten und α7' bei kantenorientierten Problemen betrachtet. In beiden Klassen sind entweder alle Knoten bzw. Kanten oder nur eine Teilmenge zu bedienen. Eine weitere mögliche Ausprägungsform bei knotenorientierten Problemen ist, dass nur eine Auswahl der Kunden bedient wird und die Bedienung der übrigen Kunden abgelehnt oder in eine spätere Periode verschoben wird. Alternativ können räumlich nah beieinanderliegende Kunden in Cluster zusammengefasst werden. Innerhalb eines Clusters ist dann genau ein Kunde zu bedienen. (Domschke und Scholl 2010, S. 201)
In der Ausarbeitung von Desrochers et al. (1990) wird ein weiteres Merkmal in der Depot- und Kundencharakteristik untersucht. Dabei handelt es sich um die Unterscheidung von deterministischem und stochastischem Bedarf. (Desrochers et al. 1990, S. 324) Jedoch verzichten Domschke und Scholl (2010) ausdrücklich auf diese Klassifikation. Es werde bei allen betrachteten Problemen von deterministischem, also zum Planungszeitpunkt bekannten, Bedarf ausgegangen. Daher werde dieses Attribut nicht in das Klassifikationsschema aufgenommen. Ebenfalls keine Berücksichtigung findet die Differenzierung von offline- und online-Problemen. Im Fall von offline-Problemen sind sämtliche Planungsdaten im Vorfeld bekannt. Bei online-Problemen hingegen treffen während der Ausführung weitere Daten (z. B. neue Aufträge) ein. Die Autoren behandeln ausschließlich offline-Probleme, weswegen diese Klassifikation hinfällig sei. (Domschke und Scholl 2010, S. 202) Der Argumentation von Domschke und Scholl folgend werden diese beiden Merkmale auch in der vorliegenden Arbeit nicht weiter behandelt.
Fahrzeugcharakteristik
Das erste zu untersuchende Attribut in der Kategorie Fahrzeugcharakteristik betrifft die Anzahl der Fahrzeuge (β1). Bei Domschke und Scholl (2010) werden zwei Fälle unterschieden. Die Fahrzeuge stehen entweder in beliebiger Anzahl zur Verfügung oder sind auf eine vorgegebene Anzahl m begrenzt. (Domschke und Scholl 2010, S. 202) In dem Schema von Desrochers et al. (1990) erfolgt zusätzlich eine Auskunft darüber, ob die Anzahl der verwendeten Fahrzeuge innerhalb des gegebenen Rahmens beliebig ist oder ob alle zur Verfügung stehenden Fahrzeuge eingesetzt werden müssen. (Desrochers et al. 1990, S. 325) Diese Unterteilung wird mit dem Attribut β1' vorgenommen.
Mit dem nächsten Attribut wird die Kapazität der Fahrzeuge (β2) klassifiziert. In der Standardausprägung liegen keine Kapazitätsrestriktionen vor. Sofern Kapazitätsrestriktionen gelten, können diese entweder für alle Fahrzeuge identisch (homogen) oder je Fahrzeug verschieden (heterogen) sein. (Domschke und Scholl 2010, S. 202) Weiterhin können Restriktionen hinsichtlich der Güterbeförderung unterschieden werden. Neben der Ausprägungsform, die keine Güterrestriktionen vorsieht, können die Fahrzeuge über verschiedene Abteile verfügen. Diese können entweder austauschbar sein und dazu dienen, inkompatible Güter (wie z. B. Hühner und Füchse) voneinander zu trennen. Alternativ werden dedizierte Abteile verwendet, die für den Transport bestimmter Waren (z. B. Kühlgut) vorgesehen sind. (Desrochers et al. 1990, S. 325 f.) Die Güterrestriktionen werden mit dem Attribut β2' bezeichnet.
Als nächstes folgen Angaben über Zeitbeschränkungen hinsichtlich der Fahrzeiten (β3). Für den Fall, dass Beschränkungen in Form von Zeitfenstern (z. B. Lenkzeitintervalle) vorliegen, können diese, ebenso wie die Fahrzeugkapazität, homogen oder heterogen sein. Dasselbe gilt für Beschränkungen der maximalen Dauer einer Tour oder Route (β4). Schließlich wird mit dem Attribut β5 die Anzahl der erlaubten Touren oder Routen je Fahrzeug im Planungszeitraum angegeben. (Domschke und Scholl 2010, S. 202)
Problem- oder Zusatzcharakteristik
In dieser Kategorie werden Attribute analysiert, die nicht mit einzelnen Knoten oder Fahrzeugen in Verbindung gebracht werden können. (Desrochers et al. 1990, S. 323) Das Attribut γ1 gibt Auskunft über die Art des Graphen. Dieser kann ungerichtet, gerichtet oder gemischt (vgl. Kapitel 2.2.1) sein. Mit dem Attribut γ2 erfolgen Angaben über Restriktionen hinsichtlich der Bedienbarkeit. So ist zum Beispiel denkbar, dass nicht jeder Kunde von jedem Fahrzeug bedient werden kann. Weiter gibt das Attribut γ3 an, ob eine oder mehrere Perioden betrachtet werden. (Domschke und Scholl 2010, S. 203)
Zielsetzung
Abschließend wird in dieser Charakteristik δ die Zielsetzung des Problems klassifiziert. Bei allen vier Attributausprägungen handelt es sich um Minimierungsprobleme. Mögliche zu minimierende Größen sind die Summe der zurückzulegenden Entfernungen, die Summe der Fahrzeiten, die Anzahl der benötigten Fahrzeuge bzw. Touren und die Summe der Fahrtkosten. Dabei berechnen sich die Fahrtkosten in Abhängigkeit der übrigen drei Größen. (Domschke und Scholl 2010, S. 203)
Das oben beschriebene Klassifizierungssystem mit den einzelnen Attributen und Attributausprägungen wird in Tabelle 2-1 zusammengefasst. Für die Darstellung wird ein Morphologischer Kasten gewählt. Es handelt sich dabei um eine Technik, bei der ein Problem in seine elementaren Bestandteile zerlegt wird. Die verschiedenen Ausprägungsformen der Problemelemente werden dann in einer Matrix abgebildet und miteinander kombiniert. Der Vorteil eines Morphologischen Kastens besteht in diesem Fall insbesondere darin, dass die Vielzahl von Informationen in verdichteter Form dargestellt wird. (Disselkamp 2012, S. 161 f.)
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 2-1: Morphologischer Kasten zur Klassifikation von Tourenproblemen (eigene Darstellung)
In diesem Abschnitt werden einige Standardprobleme der Tourenplanung anhand des in Kapitel 2.2.2 dargestellten Schemas klassifiziert. Allgemein gilt, wenn beim Attribut α5 keine Zeitrestriktionen hinsichtlich der Bedienung vorliegen, so heißt das zu untersuchende Problem in der englischsprachigen Literatur vehicle routing problem (VRP). Bei der Verwendung von festen Zeitvorgaben wird ein Problem als scheduling problem bezeichnet. Werden Zeitfenster für die Bedienung vorgeschrieben, so handelt es sich um ein vehicle routing and scheduling problem. (Domschke und Scholl 2010, S. 201)
Das wohl bekannteste knotenorientierte Tourenproblem ist das travelling salesman problem (TSP). Bei diesem Problem möchte ein Handlungsreisender seine Waren in mehreren Städten seiner Region vertreiben. Er muss jede Stadt genau einmal besuchen und anschließend in seine Heimatstadt zurückkehren. Um möglichst viel Zeit für die Kundenbesuche zur Verfügung zu haben, gilt das Ziel, die Summe der gefahrenen Strecken zu minimieren. (Eiselt und Sandblom 2010, S. 201) In Tupelschreibweise lässt sich das TSP wie folgt darstellen: [1│1│ │L] für einen ungerichteten Graphen und [1│1│dir│L] für einen gerichteten Graphen. (Domschke und Scholl 2010, S. 203) Diese Attributausprägungen bedeuten anhand des Klassifikationsschemas in Worten: ein Depot, ein Fahrzeug, ungerichteter oder gerichteter Graph, minimiere die Summe der Entfernungen. Bei allen anderen Attributen ist jeweils die mit ○ gekennzeichnete Standardausprägung zu wählen.
Beim bekanntesten kantenorientierten Tourenproblem handelt es sich um das Chinese postman problem oder Briefträgerproblem. Es geht zurück auf einen chinesischen Mathematiker, der im Zuge der Kulturrevolution als Postangestellter eingesetzt wurde. In dem Zusammenhang beschäftigte er sich mit den Aufgaben eines Briefträgers. Dieser holt die Post an einer bestimmten Stelle ab und verteilt sie auf die einzelnen Haushalte. Dabei muss er jede Straße mindestens einmal durchlaufen. Ziel ist es, die Summe der zurückzulegenden Entfernungen zu minimieren. (Eiselt und Sandblom 2010, S. 201) Das Briefträgerproblem in Tupelschreibweise lautet je nach Art des Graphen [1, edge│1│ │L], [1, edge│1│dir│L] bzw. [1, edge│1│mix│L]. (Domschke und Scholl 2010, S. 203) Es zeichnet sich folglich aus durch ein Depot, kantenorientierten Bedarf, ein Fahrzeug und einen ungerichteten, gerichteten bzw. gemischten Graphen. Dabei gilt jeweils das Ziel die Summe der Entfernungen zu minimieren.
Sowohl beim Briefträgerproblem als auch beim TSP handelt es sich um Tourenprobleme der speziellen Art. Es werden folgend fünf Standardprobleme im engeren Sinne betrachtet. Dabei wird auf die Angabe der Art des Graphen (γ1) verzichtet, da jeweils alle drei Ausprägungsformen denkbar sind. (Domschke und Scholl 2010, S. 203 f.)
[...]
