Design von Anreizsystemen im Attended Home Delivery: Vorstellung mathematischer Modellformulierungen und anschließende Implementierung des Systems mit IBM ILOG und MS EXCEL

2 Literaturüberblick

Nach Agatz et al. (2013) lässt sich der Forschungsbereich des ATD, angelehnt an die Bereiche des Revenue Managements (RM), in vier unterschiedliche Ansätze unterteilen. Als Unterscheidungskriterien werden zum einen die Modellarten mit den Ausprägungen dynamisch und statisch herangezogen, zum anderen wird eine Unterscheidung zwischen Pricing und Slotting, also der Allokation von Zeitfenstern, vorgenommen.

Statische Modelle im Bereich der Kapazitätssteuerung bezeichnet man als Differentiated Time Slotting. Ziel dieses Forschungsbereiches ist es, durch die spezielle Anpassung von Zeitfenstern an die Bedürfnisse unterschiedlicher Kundengruppen eine effizientere Routenplanung zu ermöglichen. Eine für diese Anwendung sinnvolle Segmentierung der Kundengruppen kann dabei nach geographischen Kriterien wie beispielsweise des PLZ-Gebiets erfolgen. Agatz et al. (2008a) teilen die Gestaltung von Lieferzeitfenstern in zwei Schritte auf. Im ersten Schritt geht es darum, die Serviceanforderungen und Lieferkosten eines Gebiets zu bestimmen. Im zweiten Schritt werden den Gebieten spezifisch gestaltete Zeitfenster zugewiesen, die möglichst alle Serviceanforderungen erfüllen. Bei diesem Vorgang spielen Überlegungen der Routenplanung eine große Rolle, da diese Zuweisung für den Grad der Effizienz der Routenbildung entscheidend ist. In der wissenschaftlichen Literatur werden in diesem Forschungsbereich häufig Untersuchungen zum Einfluss der Länge der Zeitfenster angestellt (vgl. Agatz et al., 2008a, S. 7). So vergleichen bspw. Punakivi und Saranen (2001) die Struktur der Lieferkosten mehrerer Händler und kommen zum Ergebnis, dass sich die Kosten des UATD Services auf nur ein Drittel der Kosten des ATD Services mit zweistündigen Lieferzeitfenstern belaufen. Dies zeigt den Effizienzgewinn der Routenplanung durch die Relaxierung von Beschränkungen auf Grund zugesicherter Zeitfenster (vgl. Agatz et al., 2008a, S. 7). Agatz et al. (2008b) thematisieren darüber hinaus das Problem der Zuweisung von Zeitfenstern zu Liefergebieten. Sie beschreiben, inwiefern Zeitfenster spezifisch gestaltet werden können, um die Serviceanforderungen eines Gebiets zu erfüllen.

Eine gewinnmaximierende Echtzeitsteuerung des Zeitfensterplans ermöglichen dynamische Modelle im Bereich der Kapazitätssteuerung. Diese werden allgemein als Dynamic Time Slotting bezeichnet. Der wichtigste Erfolgsfaktor ist hierbei eine realitätsnahe Abbildung des Kundenverhaltens. Die grundlegende Idee besteht darin, dem Kunden nur eine reduzierte, gewinnmaximierende Menge an Lieferzeitslots zur Auswahl anzubieten. Dabei ist die erfolgsentscheidende Frage, wie ein Kunde auf angebotene Alternativen reagiert, sofern dessen präferiertes Lieferzeitfenster nicht in dieser Menge enthalten ist (vgl. Agatz et al., 2008a, S. 9). In der wissenschaftlichen Literatur lässt sich als grundlegende Thematik in diesem Bereich vor allem die Entscheidung über die Annahme bzw. Ablehnung einer Lieferung in einem spezifischen Lieferzeitfenster feststellen. So entwickeln bspw. Bent und Hentenryck (2004) ein Modell, welches auf Basis von stochastischen Informationen über zukünftige Bestellungen eine Entscheidung über die Angebotsmenge an Zeitslots für eine betrachtete Bestellung treffen kann. Als Maximierungskriterium wird hierbei die Anzahl der angenommenen Bestellungen festgelegt. Campbell und Savelsbergh (2005) nehmen darüber hinaus die Möglichkeit auf, dass zur Gewinnmaximierung teure Lieferungen abgelehnt werden können, um Kapazitäten für günstigere Lieferungen freizuhalten, die in der Zukunft eintreffen könnten.

Differentiated Pricing Modelle verfolgen zur Gewinnmaximierung einen anderen Ansatz. So soll die Nachfrage durch spezifische Lieferpreise unterschiedlicher Zeitfenster geglättet werden. Dadurch werden ebenso kostspielige Überkapazitäten wie auch Nachfrage­verluste durch Unterkapazitäten vermieden (vgl. Agatz et al., 2013, S. 134). Da die Einführung eines solchen Systems wenig komplex ist und die Preise ausschließlich nach statistischen Beobachtungen des Marktes fix festgelegt werden, wird in diesem Bereich im Zusammenhang mit ATD kaum Forschung betrieben.

Deutlich mehr Forschungsbeiträge lassen sich dagegen, wie auch diese Arbeit, dem Bereich des Dynamic Pricing zuordnen. Der Grundgedanke der gewinnmaximierenden Beeinflussung von Kundenentscheidungen durch Preisdifferenzierung wird hierbei um eine dynamische Komponente erweitert, die in Echtzeit über die Höhe des Anreizes entscheiden kann. Dadurch können die Preise bei spontanen Markt- und Nachfrage­veränderungen automatisiert angepasst werden. So wird die Effektivität der Preisdifferen­zierung erhöht und das Verlustrisiko durch unwirksame Anreize verringert. Hierzu sind zwei unterschiedliche Ansätze möglich. Zum einen kann die Nachfrage durch eine kapazitätsabhängige Preissteuerung unter Einbeziehung stochastischer Informationen über zukünftige Bestellungen, ebenso wie auch beim statischen Pricing, geglättet werden. Zum anderen ist auch eine Distanzminimierung der Lieferrouten durch eine geografische Bündelung der Bestellungen denkbar, welche durch gezielte Anreizsetzung auf Zeitfenster mit geringen Lieferkosten erreicht wird (vgl. Agatz et al., 2013, S. 136). Ersteren Ansatz verfolgen Asdemir et al. (2009), indem sie ein Modell vorstellen, welches spezifische Lieferpreise für unterschiedliche Zeitfenster und Kundengruppen dynamisch berechnet. Dieses Modell wird in Abschnitt 3.2 näher erläutert. Campbell und Savelsbergh (2006) verfolgen dagegen den zweitgenannten Ansatz. Die Autoren entwickeln ein Modell, welches für jede neue Bestellung auf Basis bereits angenommener Bestellungen die kostengünstigsten Zeitfenster ermittelt, um gewinnmaximierende Rabatte auf diese zu berechnen. Eine genauere Erläuterung dieses Modells erfolgt in Abschnitt 3.1. Yang et al. (2013) erweitern dieses Modell, indem sie stochastische Informationen über die Lieferkosten zukünftiger Bestellungen mit einbeziehen. Zusätzlich wird ein erweitertes Customer Choice Modell eingesetzt, welches das Kundenverhalten realistischer abbilden kann.

3 Mathematische Modellformulierung

In diesem Abschnitt werden zwei Modelle vorgestellt, die sich dem Forschungsbereich Dynamic Pricing zuordnen lassen. In den Abschnitten 3.1 und 3.2 erfolgt jeweils eine Einführung in die betrachteten Modelle, in Abschnitt 3.3 werden diese dann gegenübergestellt und auf Unterschiede und Gemeinsamkeiten untersucht.

3.1 Modellierung unter Verwendung dynamischer Rabatte

Dieser Abschnitt baut auf einem Modell von Campbell und Savelsbergh (2006) auf. Ziel des Modells ist es, Kunden durch einen finanziellen Anreiz in Form eines Rabatts auf bestimmte Lieferzeitfenster zu lenken. Dadurch sollen die Bestellungen geografisch gebündelt und somit die Lieferkosten gesenkt werden. Die Preise werden hierbei nicht, wie im Dynamic Pricing üblich, vollständig dynamisch bestimmt. Stattdessen bildet ein Fixpreis die Grundlage für den Lieferpreis eines Zeitfensters. Hinzu kommt die Möglichkeit, den Preis in einzelnen Zeitfenstern durch einen Rabatt zu verringern, welcher dynamisch berechnet wird. Dadurch können die Preise einfacher ermittelt werden, als wenn diese vollständig dynamisch bestimmt würden. Zudem stoßen Rabatte in Verbindung mit einem Fixpreis bei Kunden oft auf eine größere Akzeptanz, da die Preisermittlung transparenter dargestellt werden kann. Ein weiterer Vorteil von Rabatten besteht darin, dass die endgültige Preisgestaltung, wie z.B. das Anbieten einer kostenlosen Lieferung, der Marketingstrategie überlassen bleibt, da das Anreizsystem unabhängig davon agieren kann. Der Betrachtungsgegenstand einer Modellinstanz ist eine neu ankommende Bestellung bei beliebig vielen schon angenommenen und geplanten Bestellungen. Da Campbell und Savelsbergh (2006) zuerst ein nichtlineares Modell einführen und dieses in einem zweiten Schritt in die Form eines linearen Programms (LP) bringen, orientiert sich der Aufbau dieses Abschnittes an deren Vorgehen.

3.1.1 Einführung eines nichtlinearen Grundmodells

In Tabelle 1 werden die zur Modellformulierung benötigten Inputparameter, in der Reihenfolge des Auftretens im Formenkonstrukt, eingeführt. Der Index spezifiziert dabei die einzelnen Zeitfenster, bei Zeitfenstern läuft dieser also von bis T.^[1]

Abbildung in dieser Leseprobe nicht enthalten^[2]

Tabelle 1: Bedeutung der Inputparameter

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Bedeutung der Entscheidungsvariablen

Mit den eben eingeführten Variablen und Inputparametern lässt sich folgende Zielfunktion bilden:

(1)

Die Zielfunktion maximiert den erwarteten Gewinn des Lieferplans. Sie setzt sich aus zwei Summanden zusammen. Summand quantifiziert hierbei den Gewinn aus Zeitfenstern mit Rabatten, Summand drückt den Gewinn aus allen Zeitfenstern ohne Rabatte aus. Um den erwarteten Gewinn eines Lieferzeitfensters zu erhalten, werden für alle Zeitfenster die Einfügekosten vom Umsatz der Bestellung abgezogen. Bei Zeitfenstern mit Rabatten wird zusätzlich noch die gewährte Vergünstigung abgezogen und das Ergebnis mit der modifizierten Auswahlwahrscheinlichkeit multipliziert (siehe Summand ). Um die Verschiebung der Wahrscheinlichkeiten auszugleichen, wird bei den Auswahlwahrscheinlichkeiten der Zeitfenster ohne Rabatte die Entscheidungsvariable abgezogen. Damit keine Auswahlwahrscheinlichkeit negativ wird, wird folgende Nebenbedingung festgelegt:

(2)

Somit kann maximal den Wert des geringsten aller Zeitfenster erreichen, bei denen kein Rabatt gewährt wird. Die Größe von ist darüber hinaus davon abhängig, wie stark der Kunde auf Rabatte reagiert, also dem Parameter . Diese Verbindung wird über die zweite Nebenbedingung hergestellt:

(3)

Durch eine kleine Umformung dieser Nebenbedingung erhält man die Gleichung
Daran wird ersichtlich, dass an dieser Stelle sicher gestellt wird, dass im gleichen Maße steigt wie das Summenprodukt aus allen Rabatten und dem Preissensibilitätsfaktor, geteilt durch die Anzahl an Zeitfenstern, welche kein Rabatt erhalten ( ).

Abschließend wird noch eine Nebenbedingung benötigt, die sicherstellt, dass die Rabatte zum einen die gesetzte Grenze nicht überschreiten und zum anderen nicht negativ werden. Mathematisch lässt sich dieser Sachverhalt wie folgt formulieren:

(4)

3.1.2 Linearisierung des Grundmodells

Beim genaueren Betrachten des Summanden der Zielfunktion (1) fällt auf, dass dort die Entscheidungsvariable quadriert wird. Somit handelt es sich hierbei um ein nichtlineares Optimierungsmodell, welches für große Instanzen nur durch erheblichen Rechenaufwand zu lösen ist. Da aber für jede neu ankommende Bestellung eine neue Modellinstanz gelöst werden muss, ist ein nichtlineares Optimierungsmodell für die Anwendung in der Praxis kaum einsetzbar. Daher ist es sinnvoll, ein lineares Modell zu finden, welches bei wesentlich geringerem Rechenaufwand eine möglichst gute Approximation liefert. Die Linearisierung des Grundmodells erfolgt in Anlehnung an Campbell und Savelsbergh (2006). Dazu muss zuerst der nichtlineare Teil der Funktion durch Umformungen isoliert werden:

(1)

(5)

Bei der Funktion (5) handelt es sich um eine ausmultiplizierte Form der Funktion (1). In dieser Form können konstante Summanden (grau hinterlegt) gut identifiziert werden. Diese können zur Vereinfachung vorerst weggelassen werden, da die Berechnung der Entscheidungsvariablen dadurch nicht beeinflusst wird. Somit erhalten wir folgende Funktion (6):

(6)

Damit ist der nichtlineare Term isoliert. Dieser quadratische Term wird nun für jedes durch eine abschnittsweise definierte lineare Funktion (7) ersetzt, welche über Intervalle abgebildet wird^[3]. Die unterste Intervallgrenze liegt bei , die oberste Intervallgrenze beträgt . Die Ermittlung von lässt sich der Gleichung (8) entnehmen.

(7)

(8)

Durch (8) wird sichergestellt, dass die Vergünstigung eines Zeitfensters maximal so groß wird, dass diese B nicht überschreitet und dass kein negativ wird. Durch die - Variablen können, wie in Abbildung 1 durch die roten Linien visualisiert, Linearkombinationen zwischen den Stützpunkten (rote Punkte) hergestellt werden. Grundsätzlich müssen an dieser Stelle zusätzlich für jeden Abschnitt Binärvariablen eingeführt werden, die in einer zusätzlichen Nebenbedingung sicherstellen, dass Linearkombinationen immer nur zwischen zwei benachbarten Stützpunkten hergestellt werden können. Da die zu approximierende Funktion konkav ist und eine Maximierung durchgeführt wird, kann in diesem Fall jedoch darauf verzichtet werden. In Abbildung 1 wird die quadratische Zielfunktion blau dargestellt, die lineare Approximation mit ist rot markiert.

Abbildung 1: Verlauf des Zielfunktionswerts bei einem Zeitfenster mit Rabatt^[4]

Somit erhalten wir folgendes LP:

(9)

(10)

(11)

(12)

(13)

(14)

Um (9) zu erhalten, wurde der nichtlineare Teil der Funktion (6) durch (7) ersetzt, außerdem wurden alle konstanten Terme der Zielfunktion wieder addiert, um die Vergleichbarkeit der Zielfunktionswerte zu gewährleisten. Die neu eingeführten Nebenbedingungen (10) und (11) sind der Linearisierung geschuldet. Die restlichen Nebenbedingungen lassen sich vom nichtlinearen Modell übernehmen.

Da festgelegt werden muss, über wie viele Abschnitte eine Approximation stattfindet, wurden in einem Experiment Approximationen unterschiedlicher Grade mit dem nichtlinearen Grundmodell verglichen. Aus diesem Experiment geht hervor, dass selbst bei einer kleinen Anzahl an Stützstellen verhältnismäßig geringe Abweichungen zustande kommen. Unter gewissen Bedingungen kann es sogar passieren, dass das Maximum der zu approximierenden Funktion ( ) mit einer kleinen Anzahl an eingesetzten linearen Funktionsabschnitten exakt getroffen wird, was dagegen mit einer Vervielfachung der Stützstellen nicht mehr gelingt. Der Grund hierfür liegt in der quadratischen Funktionsstruktur. Generell kann ein exakter Treffer nur mit einer ungeraden Anzahl an Stützstellen gelingen, wobei die genaue benötigte Anzahl von abhängig ist. Abbildung 2 zeigt, dass der ZF- Wert bei stark ansteigt und sich dann in einem periodischen Zyklus fortentwickelt, dessen Amplitude immer geringer wird. Außerdem kann man an dieser Abbildung erkennen, dass der Rechenaufwand, dargestellt durch die Anzahl der Variablen, mit der Steigerung der Stützstellen linear anwächst. Somit stellt die lineare Abbildung durch fünf Stützstellen eine sinnhafte Näherung dar, da bei einer Steigerung der Stützstellen ab diesem Zeitpunkt das Verhältnis nicht mehr rentabel ist.

3.2 Modellierung unter Verwendung dynamischer Preissetzung

Dieser Abschnitt bezieht sich auf das von Asdemir et al. (2009) vorgestellte Modell. Auf Grund der Komplexität des Modells wird an dieser Stelle nur die grundsätzliche Herangehensweise bei der Modellierung thematisiert, auf die komplette mathematische Formulierung wird bewusst verzichtet. Ziel ist es, in das Modell soweit einzuführen, damit ein Modellvergleich zum im vorigen Abschnitt vorgestellten Modell möglich wird.

Abbildung 2: Experiment zur Linearisierung^[5]

Abbildung in dieser Leseprobe nicht enthalten

Die Grundidee des Modells besteht darin, den zeitlichen Verlauf der Nachfrage durch eine dynamische Bestimmung der Lieferkosten zu beeinflussen. So sollen Nachfragespitzen zu Stoßzeiten geglättet werden, um den Ressourcenbedarf, welcher sich am Nachfragemaximum orientiert, zu reduzieren. Somit sinken die Kosten respektive erhöht sich der Gewinn. Asdemir et al. (2009) modellieren diesen Preisfindungsprozess durch ein Markow-Entscheidungsproblem. Hierbei werden alle Perioden des Buchungszeitraums, also von der Öffnung bis zur Schließung der Buchungsmöglichkeit eines Zeitfensters, von einer Modellinstanz betrachtet. Die Preisdifferenzierung wird kundengruppenspezifisch festgelegt, berücksichtigt werden die Auswahlwahrscheinlichkeiten der unterschiedlichen Zeitslots, die Preissensibilität der betrachteten Kundengruppe und die verfügbare Kapazität zum Betrachtungszeitpunkt. Die optimale Preisstruktur der Lieferkosten zur Gewinnmaximierung wird rekursiv über alle Perioden bestimmt. Die Formulierung des Modells baut auf dem stochastischen dynamischen Grundmodell auf, welches vor allem aus dem RM bekannt ist. Für eine ausführliche Erklärung dieses Grundmodells sei auf Klein und Steinhardt (2008) verwiesen.

Um ein realistisches Kundenverhalten abbilden zu können, wird ein Discrete Choice Modell^[6] eingesetzt. Es handelt sich dabei um ein Logit Modell, was die am weitesten verbreitete Ausprägung des Discrete Choice Modells darstellt (vgl. Gönsch et al., 2008, S. 358). Hierzu wird eine Unterteilung der Kunden in unterschiedliche Gruppen vorgenommen, welche jeweils durch spezifische Verhaltensmuster charakterisiert werden. So wird für jede Kundengruppe eine Ankunftswahrscheinlichkeit zu jeder Buchungsperiode festgelegt. Zusätzlich wird vorausgesagt, wie hoch der Nutzen für die betrachtete Kundengruppe bei Lieferung der Ware in einem bestimmten Zeitfenster ist. Um die Beeinflussung der Kundenentscheidung durch die dynamisch gesetzten Lieferpreise abbilden zu können, werden die Nutzenwerte durch eine Funktion modifiziert. Dabei wird der Nutzen durch einen parametrisch festgelegten Anteil des Preises verringert. Steigt also der Lieferpreis eines Zeitfensters, so sinkt die Nachfrage nach demselben respektive steigt die Nachfrage der anderen Zeitfenster zu gleichen Teilen. Basierend auf diesen Nutzenwerten wird durch eine Funktion berechnet, mit welcher Wahrscheinlichkeit die betrachtete Kundengruppe ein bestimmtes Zeitfenster auswählt. Hier spielt neben dem modifizierten Nutzen noch eine stochastische, identisch verteilte Variable eine Rolle. Dadurch bildet das Modell die Gegebenheit aus der Realwelt, dass die Auswahlwahrscheinlichkeit nur zum Teil vorhergesagt werden kann, ab.

Neben den Kundeninformationen werden zur Berechnung der optimalen Preise noch Angaben über die verfügbare Kapazität benötigt. Hierzu wird ein Vektor verwendet, der für jede Periode die verfügbaren Restkapazitäten jedes Zeitfensters aufnimmt. Von diesem Vektor ist es abhängig, ob eine Bestellung angenommen werden kann oder mangels freier Kapazität abgelehnt werden muss.

Mit diesen Inputdaten kann durch Anwendung des ebenfalls aus dem RM bekannten Optimalitätsprinzips von Bellmann ein gewinnmaximierender Preisvektor herbeigeführt werden. Der Preisvektor stellt zugleich die einzige Entscheidungsvariable und somit den alleinigen Hebel dar. Wie im stochastisch dynamischen Grundmodell wird das Optimierungsproblem in Stufen unterteilt, wobei jede Stufe für eine Buchungsperiode steht. Die Annahme, dass pro Stufe höchstens eine Kundengruppe im System ankommt, wird vom Grundmodell übernommen. Das Modell wird nun erweitert, indem für jede Stufe zwei Wertfunktionen und aufgestellt werden. stellt den reduzierten Zustand des Systems dar und beschreibt die maximale mit der verfügbaren Kapazität zum Zeitpunkt zu erreichende Auszahlung. Diese Funktion stellt zudem sicher, dass das System mit gleichbleibender Kapazität in den nächsten Zustand übergeht, falls in keine Kundenankunft zu verzeichnen ist. Der größte Unterschied zum Grundmodell besteht darin, dass in jeder Stufe nicht nur eine binäre Entscheidung zwischen Annahme und Ablehnung der Bestellung ansteht, stattdessen wird bei Kundenankunft im kompletten Systemzustand durch die dynamische Bepreisung der Lieferkosten eine Maximierung des erwarteten Umsatzes durchgeführt. Der Buchungszeitraum wird in Mikroperioden eingeteilt, wobei pro Periode höchstens eine Kundengruppe ankommt. Die rekursive Berechnung erfolgt, wie in Abbildung 3 veranschaulicht, ausgehend von Periode .

[...]

^[1] Campbell und Savelsbergh (2006) führen noch einen zusätzlichen Index ein, welcher den neu ankommenden Kunden bezeichnet. Da für jede neue Bestellung und somit für jeden Kunden aber sowieso eine neue Modellinstanz gebildet werden muss, wird an dieser Stelle zur Vereinfachung darauf verzichtet.

^[2] Die Einfügekosten werden in einem Preprocessing ermittelt, auf welches in Abschnitt 4.2 näher eingegangen wird.

^[3] Für die grundsätzliche Vorgehensweise für eine Approximation einer stetigen Funktion mit einer Variable durch eine abschnittsweise definierte lineare Funktion sei an dieser Stelle auf Nemhauser und Wolsey (1988) verwiesen.

^[4] Inputparameter:

^[5] Inputparameter:

^[6] Für eine Einführung in das Discrete Choice Modelling siehe Gönsch et al. (2008).