3 Quantitative Modellierung der Auslieferungsplanung auf der Letzten Meile       

Wie die im vorherigen Kapitel aufgeführten Untersuchungen zeigen, bietet die Verwendung von Schließfachsystemen zur Gestaltung der Letzten Meile ein großes Potential zur Kostenreduktion. Um die beiden Auslieferungsformen Hauszustellung und Schließfachsysteme quantitativ zu vergleichen, wird in diesem Kapitel zunächst ein bestehendes Tourenplanungsmodell für Hauszustellung untersucht. Unter dem Ausdruck Hauszustellung wird, wie in Kapitel 2.1.4 festgelegt, Hauszustellung mit persönlicher Anwesenheit des Empfängers verstanden. Anschließend wird das Modell in einigen Aspekten modifiziert. Motivation hierfür ist zum einen, dass das Modell auf diese Weise überhaupt lauffähig gemacht wird. Zum anderen vereinfacht die Anpassung den Vergleich mit dem anschließend in Kapitel 3.3 analysierten Modell für die Verwendung von Schließfachsystemen. Dabei handelt es sich um eine im Rahmen der vorliegenden Arbeit durchgeführte Modifikation des Modells für Hauszustellung.

3.1 Tourenplanung mit Hauszustellung (Grundmodell)

Für die Modellierung der Tourenplanung mit Hauszustellung wird ein bestehendes Modell als Grundlage gewählt. Es handelt sich dabei um ein VRPTW von Schmid et al. (2013). Die Entscheidung fällt auf dieses Modell, da es alle gewünschten Ausprägungen abbildet und anschaulich präsentiert wird. Die Autoren nehmen in ihrer Ausarbeitung bereits selbst einige Variationen des Modells vor und empfehlen in ihrem Ausblick weitere Varianten abzubilden. Es ist daher gut als Grundlage für Modifikationen geeignet.

Es werden zunächst die Rahmenbedingungen des Modells erläutert. Anschließend wird das Modell anhand des in Kapitel 2.2.2 vorgestellten Schemas klassifiziert. Schließlich erfolgt die Vorstellung und Analyse des mathematischen Modells.

3.1.1 Rahmenbedingungen und Klassifikation

Bei dem vorliegenden Modell von Schmid et al. (2013) handelt es sich um ein VRPTW. Es gilt für den zusammenhängenden Graphen G = (V, A), wobei die Knotenmenge V = {0, n+1} ∪ {1,..., n} neben der Menge der Kunden C = {1,..., n} auch zwei Kopien des Depots 0 und n+1 abbildet. Faktisch liegt nur ein Depot vor, systemisch wird dieses in Start- und Enddepot unterteilt. A ist die Menge der Kanten, auf denen die Fahrtkosten cij sowie die Fahrzeiten tij anfallen. (Schmid et al. 2013, S. 436) Die Menge der Kanten wird zur Modellierung nicht benötigt, da jede Kante durch das Knotenpaar (i,j), i, j ∈ V dargestellt werden kann. Daher wird die Menge A im Folgenden nicht weiter betrachtet.

Die Matrizen zur Darstellung der Variablen cij und tij erfüllen die Dreiecksungleichung. (Schmid et al. 2013, S. 436) Bei der Dreiecksungleichung handelt es sich um Formel (3‑1), welche aussagt, dass die Entfernung zwischen zwei Knoten i und k nicht kürzer werden kann, wenn ein Umweg über den Knoten j gefahren wird. Einfacher ausgedrückt, bedeutet dies: Der direkte Weg ist immer der kürzeste. (Vahrenkamp und Mattfeld 2007, S. 24)

Jeder Knoten i ∈ V weist eine Nachfrage qip von Produkt p ∈ P auf. Diese ist von genau einem Fahrzeug zu erfüllen. Für die Bedienung fällt eine Bediendauer si an. Es wird angenommen, dass am Depot keine Nachfrage und keine Bediendauer auftreten (q0p = qn+1,p = s0 = sn+1 = 0). Für jeden Knoten gilt ein Zeitfenster [ai, bi] innerhalb dessen die Bedienung beginnen muss. Eine Bedienung vor ai ist nicht gestattet. Für den Fall, dass ein Knoten nach bi bedient wird, fallen Strafkosten  je Zeiteinheit an. Das Zeitfenster am Depot mit a0 = an+1 sowie b0 = bn+1 repräsentiert die frühestmögliche Abfahrtszeit sowie die spätestmögliche Rückkehr der Fahrzeuge. (Schmid et al. 2013, S. 436)

K = {1,..., m} ist die Menge der m homogenen Fahrzeuge, welche am Depot stationiert sind. Die Fahrzeuge verfügen über eine Kapazität Q, welche bei der Auslieferung nicht überschritten werden darf. Jedes Fahrzeug darf nicht mehr als eine Tour fahren. Teillieferungen sind nicht erlaubt. (Schmid et al. 2013, S. 436)

Es werden die folgenden Variablen definiert: Die Binärvariable xijk ist gleich eins, wenn Fahrzeug k auf Kante (i, j) fährt. Ebenso ist yik gleich eins, wenn Fahrzeug k Knoten i bedient. Die Variable wik bestimmt den Beginn der Bedienung an Knoten i durch Fahrzeug k. Mit ui wird die Verspätung der Bedienung an Knoten i ausgedrückt. (Schmid et al. 2013, S. 436)

Hinsichtlich des Klassifikationsschemas aus Kapitel 2.2.2 lässt sich das vorliegende Modell als [1, stw│m, cap│ │FK] einordnen. Die Unterschiede zum in Kapitel 2.2.4 vorgestellten Standard-VRPTW [1, tw│m, cap, dur│ │L] liegen folglich darin, dass bei den Zeitrestriktionen α5 weiche Zeitfenster vorliegen. Genaugenommen handelt es sich um halbweiche Zeitfenster, denn es ist lediglich eine Verletzung des Zeitfensters nach hinten möglich. Weiter unterscheidet sich das Modell von Schmid et al. (2013) gegenüber dem Standard-VRPTW dadurch, dass bei dem Attribut β4 keine maximale Tourendauer je Fahrzeug festgelegt ist. Daher entfällt der Parameter für die maximale Tourendauer. Diese Einschränkung ergibt sich nur indirekt über das für das Depot definierte Zeitfenster. Schließlich liegt der dritte Unterschied bezüglich der Klassifikation in der Zielsetzung δ. Während im Standard-VRPTW die zurückzulegenden Entfernungen minimiert werden, sind es bei Schmid et al. (2013) die Fahrtkosten. Es werden daher nicht die Entfernungen zwischen zwei Knoten, sondern die Fahrtkosten und Fahrzeiten angegeben.

Weitere Unterschiede der beiden Modelle lassen sich an den Mengen, Parametern und Variablen ablesen. Dabei handelt es sich um die Zerlegung des Depots in Start- und Enddepot bei Schmid et al. (2013). Diese systemische Unterteilung hat den Vorteil, dass sowohl die Abfahrtszeit am Startdepot als auch der Zeitpunkt der Rückkehr zum Enddepot im Ergebnis abgelesen werden kann. Darüber hinaus unterscheidet sich das Modell von Schmid et al. (2013) vom Standard-VRPTW dadurch, dass bei den Bedarfen verschiedene Produkttypen differenziert werden. Bei der Entscheidungsvariable für die Bestimmung der Ankunftszeit wik wird bei Schmid et al. (2013) mit einem zusätzlichen Index die Auswahl des Fahrzeugs berücksichtigt. Schließlich ergeben sich je ein weiterer Parameter und eine weitere Variable, Verspätungen bei der Bedienung und daraus resultierende Strafkosten abzubilden.

Zur übersichtlicheren Darstellung erfolgt an dieser Stelle eine Auflistung der oben beschriebenen Mengen, Parameter und Variablen in alphabetischer Reihenfolge. Darauf folgt im nächsten Abschnitt die Analyse des Modells.

Mengen

Parameter

Variablen

3.1.2 Modellanalyse

Nach der Vorstellung des Modells für Hauszustellung werden die Formeln einzeln analysiert und dem Standard-VRPTW aus Kapitel 2.2.4 gegenübergestellt. Das Modell lautet wie folgt (Schmid et al. 2013, S. 436 f.):

unter den Nebenbedingungen:

Zunächst ist anzumerken, dass es sich beim dritten Summenzeichen in Formel (3‑2) höchstwahrscheinlich um einen Tippfehler seitens der Autoren Schmid et al. (2013) handelt. Es wird dort die Summe über alle k Fahrzeuge genommen. Die Menge der Fahrzeuge ist jedoch K und nicht V. Daher läuft die Summe an dieser Stelle richtigerweise über k ∈ K und nicht über k ∈ V.

Die Zielfunktion in Formel (3‑2) sorgt dafür, dass die Summe der Gesamtkosten minimiert wird. Diese setzen sich zusammen aus der Summe der Fahrtkosten sowie der Summe der anfallenden Verspätungskosten. Der Unterschied zur Zielfunktion des Standard-VRPTW in Formel (2‑1) besteht in der Verwendung der Fahrtkosten anstelle der Distanzen sowie in der Berücksichtigung der Verspätungskosten. Die Restriktionen (3‑3) sorgen dafür, dass die Fahrzeugkapazität Q nicht überschritten wird. Dies entspricht den Restriktionen (2‑2) aus dem Standard-VRPTW mit dem Unterschied, dass bei Schmid et al. (2013) zusätzlich verschiedene Produkttypen berücksichtigt werden. Durch die Restriktionen (3‑4) wird sichergestellt, dass jeder Kunde genau einmal bedient wird und (3‑5) gewährleisten, dass jedes Fahrzeug das Depot besucht. Die Formel (2‑3) im Standard-VRPTW stellt eine Kombination aus den beiden Formeln (3‑4) und (3‑5) dar.

Die Flussbedingungen (3‑6) und (3‑7) sorgen dafür, dass jeder von einem Fahrzeug k besuchte Knoten von diesem Fahrzeug genau einmal angefahren und wieder verlassen wird. Im Standard-VRPTW wird dies durch die...