Bestellmengenplanung basierend auf Wagner/Whitin und Spieltheorie

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

1 Motivation, Problemstellung und Gang der Untersuchung

3 Das Wagner-Whitin-Problem im Bestellmengenspiel
3.1 Das Konzept des Kerns
3.2 Annahmen an die Modellierung
3.3 Algorithmische Spieltheorie
3.3.1 Die Row-Generation-Procedure
3.3.2 Anwedung auf das Wagner-Whitin-Problem
3.4 Ökonomische Interpretation

4 Zusammenfassung, Fazit und Ausblick

A Anhang
A.1 Algorithmen und Probleme
A.1.1 HP′′(S)
A.1.2 SP ′(π).
A.1.3 SP ′′(π) .
A.1.4 Core′(HP, SP′)
A.1.5 Core′′(HP, SP′′)
A.1.6 Core′(HP,SP ′)
A.1.7 Core′′(HP, SP′′)
A.1.8 Core(HP,SˆP)
A.1.9 Core′(HP′,SˆP)
A.1.10 Core′′(HP′′,SˆP)
A.2 Zahlenbeispiel
A.2.1 Graphische Interpretation

Literaturverzeichnis

Abbildungsverzeichnis

A.1 Kern{n₁}, {n₂}, {n₃} mit HP(S)

A.2 Kern{n₁}, {n₂}, {n₃} mit HP′(S)

A.3 Kern{n₁}, {n₂}, {n₃} mit HP′′(S)

Tabellenverzeichnis

A.1 Werte der Variablen

A.2 Werte des kooperativen Spiels

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Motivation, Problemstellung und Gang der Untersuchung

Im Unternehmensalltag gewinnen neben vertikalen Kooperationen auch hori- zontale Beschaffungskooperationen zunehmend an Bedeutung. Durch das Auf- treten von Unternehmen als Kooperation, können Kosten eingespart werden. Gleiches gilt in zunehmendem Maße auch für öffentliche Einrichtungen (vgl. Drechsel und Kimms 2010, S. 313). Hieraus erwächst die Frage, wie die hieraus entstehenden Koalitionsgewinne so auf die Beteiligten verteilt werden können, dass die Koalition stabil bleibt und darüber hinaus der Gewinnanteil als fair empfunden wird (vgl. Sackmann und Rittmann 2012, S. 240-241). In der Litera- tur finden sich Verfahren, die unter einfachen Annahmen eine solche Allokation direkt berechnen können. Für komplexe Problemstellungen der Bestellmengen- planung ist bekannt, dass stabile Allokationen exitieren. Jedoch fehlt ein effizien- tes Verfahren zur Ermittlung dieser Allokationen.

Die vorliegende Arbeit soll ein algorithmisches Verfahren zur Lösung von ko- operativen Bestellmengenproblemen, auf Basis des Wagner-Whitin-Verfahrens vorstellen, dass sowohl stabile, als auch faire Allokationen von Koalitionsge- winnen bzw. Einsparungen gewährleisten kann. Im folgenden Kapite 2 erfolgt die Einordnung der Thematik in die bestehende Literatur. Hierbei werden verschiedene Ansätze zur kooperativen Bestellmen- genplanung vorgestellt. Kapitel 3 beginnt mir einer kurzen formalen Beschrei- bung des Kerns und setzt mit einer Darstellung des Wagner-Whitin-Problems und einer Anpassung für den N-Spieler-Fall fort. Anschließend erfolgt die Darstellung eines Algorithmus zur Berechnung von Kernelementen und die Anwendung auf das Wagner-Whitin-Problem. Abschließend wird eine Betrach- tung der ökonomischen Bedeutung vorgenommen und ein Ausblick auf mögli- che Erweiterungen gegeben.

2 Einordnung der Thematik in die bestehende Literatur

In diesem Kapitel werden verschiedene, in der Literatur beschriebene, analyti- sche und nicht analytische Verfahren zur kooperativen Bestellmengenplanung vorgestellt.

Die Kernfrage bei der Betrachtung kooperativer Spiele ist, ob ein oder mehrere Mitglieder der Koalition einen Anreiz haben diese zu verlassen. Ein Konzept das diese Frage beantworten kann, ist das des Kerns. Ist der Kern eines kooperativen Spieles nicht leer, existiert mindestens eine stabile Allokation die zur Stabilität der Koalition führt. Bei einem nicht leeren Kern hat also kein an der Koalition Beteiligter einen Anreiz diese zu verlassen oder eine andere als die große Koalition zu bilden. Ist der Kern eines kooperativen Spieles hingegen leer, kann keine stabile große Koaltion bestehen (vgl. Owen 2013, S. 213-215). Eine formale Betrachtung des Kerns erfolgt in Kapitel 3.1 .

Der erste vorgestellte Ansatz zur kooperativen Bestellmengenplanung stammt von Meca et al. (2004). Es wird der Frage nachgegangen, wie Einsparungen bezüglich der Lagerkosten aufgrund von kooperativer Bestellmengenplanung fair zwischen den Kooperationspartnern verteilt werden können. Untersucht wird diese Fragestellung anhand eines bewusst einfach modellierten Bestell- mengenspiels. Zugrunde gelegt wird eine Gruppe von N = {1, 2, . . . , n} Firmen mit jeweils individueller konstanter Nachfrage di ≥ 0, Lagerkosten hi ≥ 0, Be- stellmenge Qi ≥ 0, sowie identischen bestellfixen Kosten a > 0. Gegenstand der Betrachtung ist der Ein-Güterfall mit einem Lieferanten für alle N Firmen. Alle Firmen haben ein Interesse daran, als große Koalition zu agieren. Hierbei stellen alle Parameter, abgesehen von den bestellfixen Kosten, private Informationen der jeweiligen Kooperationspartner dar (vgl. Meca et al. 2004, S. 130). Zur Lö- sung des Problems wird auf die Andlersche Loßgrößenformel zurückgegriffen. Es wird bewiesen, dass sich ein optimales gemeinsames Bestellverhalten mit ei- ner Kernallokation C(c0) für die Verteilung der Bestellkosten, durch Offenlegen

der optimalen persönlichen Bestellhäufigkeit im Falle der nicht kooperativen Bestellmengenplanung [Abbildung in dieser Leseprobe nicht enthalten]angeben lässt.

Die Bestellkosten der Koalition ergeben sich zu[Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

Um eine stabile Kernallokation zu erzielen, erfolgt die Verteilung der Gesamtkosten über eine proportionale Verteilungsregeln_i(c0) auf die koalierenden Firmen (vgl. Meca et al. 2004, S. 132-133).

Abbildung in dieser Leseprobe nicht enthalten

In späteren Veröffentlichungen wird diese Regel als SOC-rule (Share the orde- ring cost) bezeichnet (vgl. Meca 2007 S. 500). Die durch Preisgabe der indivi- duellen Bestellhäufigkeit ermittelten quadrierten individuellen Bestellkosten, werden also mittels (2.2), jeweils ins Verhältnis zu den Gesamtkosten der Koaliti- on gesetzt. Für alle Bestellmengenspiele (N, c0) gilt, dass π (c0) ein Element des Kerns C(c0) ist (vgl. Meca et al. 2004, S. 132-133). Es konnte weiterhin gezeigt werden, dass durch Preisgabe weiterer Informationen neben mi, keine Verbesse- rung der Lösung erzielt werden kann (vgl. Meca et al. 2004, S. 135). Somit ist eine gemeinsame Bestellpolitik konkurrierender Firmen möglich, da keine Infor- mationen preisgegeben werden müssen, die im Konkurrenzkampf gegen das je- weilige Unternehmen eingesetzt werden könnten.

Neben der vorgestellten Allokationsregel für Bestellmengenspiele, zeigen Meca et al. (2004) auch eine Regel für die Verteilung von Einsparungen bei Lager- kostenspielen auf, die immer Kernallokationen erzeugt. Das zugrundeliegende Modell wird hierbei dahingehend erweitert, dass im Falle der Kooperation mehrerer Firmen, die Lagerung der Güter zentral im günstigsten Lagerhaus der Koalition erfolgt (vgl. Meca et al. 2004, S. 135-137). Das Konzept der Lager- kostenspiele wurde in der Folge durch Meca (2007) weiter vertieft. Es werden generalisierte Lagerkostenspiele diskutiert, wobei das Modell aus Meca et al. (2004) um Fehlmengen und eine graduelle Lieferung des Gutes erweitert wird (vgl Meca et al. 2007, S. 504). Es wird gezeigt, dass diese Spiele ausgewogen sind. Ferner wird eine Familie von Kernallokationen angegeben und eine propor- tionale Kostenverteilungsregel für die vorgenannte Familie von Allokationen diskutiert (vgl. Meca 2007, S. 515-516).

Ein gemischter Ansatz wird von Meca et al. (2007) vorgestellt. Neben der ge- meinsamen Nutzung des günstigsten Lagerhauses der Koalition, werden den einzelnen Firmen Rabatte für ihre Bestellungen angeboten. Es wird gezeigt, dass auch diese Form von Spiel vollständig ausgewogen ist. Ferner wird eine mo- difizierte SOC-rule angegeben, welche in dieser Umgebung Kernallokationen liefert (vgl. Meca et al. 2007).

Ein komplexeres Problem auf Basis der Andlerschen Loßgrößenformel bearbei- ten Fiestras-Janeiro et al. . Sie beschreiben eine Situation in der sich mehrere Firmen N = {1,2,..., n} einem Bestellmengenproblem gegenüber sehen, ihre bestellfixen Kosten aber aus zwei Komponenten bestehen. Die erste Kompo- nente sind die für alle Firmen gleichen Kosten für das Auslösen der Bestellung a > 0. Die zweite Komponente sind die individuellen Transportkosten ai > 0, welche sich proportional zur Entfernung zum Lieferanten angeben lassen. Wei- tere Größen sind die deterministische Nachfragemenge di > 0, die Lagerkosten hi > 0 und die Bestellmenge Qi > 0. Eine Koalition S ⊂ N kann Bestellungen gemeinsam aufgeben. Die gemeinsamen Transportkosten als zweite Kompo- nente der Gesamtfixkosten, ergibt sich, unter der Annahme, dass alle Firmen auf einer Route liegen, zu as = max{ai|i ∈ S}. Der Lieferant akzeptiert und wünscht die gemeinsame Bestellung als Koalition unter der Bedingung, dass in der jeweiligen Periode die Bestellkosten bei a + as fixiert bleiben. Das bedeutet, auch wenn eine Firma der Koalition nicht bestellen sollte und sich dadurch as verringern würde, bleibt es bei dem zuvor vereinbarten höheren Transportkos- ten (vgl. Fiestras-Janeiro et al. 2012, S. 398-400). Es wird gezeigt, dass im Falle der Kooperation, Kernallokationen erzielt werden können. Die Autoren stellen zwei Allokationsregeln vor, die für Koalitionen S ⊂ N stabile Kernallokationen liefern. Eine praktische Anwendbarkeit ihrer Erkenntnisse sehen sie im Bereich des Franchisings (vgl. Fiestras-Janeiro et al. 2012, S. 406 und Fiestras-Janeiro et al. 2013, S. 452).

Einen nicht deterministischen Ansatz stellt das Newsvendor-Problem von Hart- man et al. (2000) dar. Es wird angenommen, dass eine Anzahl von Zeitungsver- käufern existiert, die sich jeweils einer periodischen stochastischen Nachfrage nach Zeitungen gegenüber sieht. Die Betreiber bestellen je Periode eine bestimm- te Anzahl Exemplare der Zeitung. Da die Nachfrage nicht deterministisch ist, können in der Folge zwei Fälle auftreten. Im ersten Fall wurden für die Periode nicht ausreichend viele Zeitungen bestellt und der Inhaber macht weniger Um- satz als möglich. Im zweiten Fall übersteigt die Zahl der bestellten Zeitungen die Nachfrage und der Betreiber muss die überzähligen Exemplare abschreiben. Die Kioskbesitzer haben die Möglichkeit ihre Bestellungen gemeinsam aufzuge- ben und die Zeitungen zentral zu lagern (vgl. Hartman et al. 2000, S. 26-27). Es wird gezeigt, dass hierauf basierende Spiele einen nicht leeren Kern haben, so- fern die Nachfrage symmetrisch bzw. gemeinsam multivariat normalverteilt ist (vgl. Hartman et al. 2000, S. 47-48). Müller et al. (2002) konnten zeigen, dass der Kern von Newsvendor Spielen unabhängig von der Nachfrageverteilung nicht leer ist. Es kann also eine stabile Koalition aufgrund von fairer Kostenallokation gebildet werden.

Einen Ansatz mit dynamischen Loßgrößenspielen wählen van den Heuvel et al. (2007). Er basiert auf dem Wagner-Whitin-Loßgrößenproblem, welches auch in Kapitel 3 dieser Arbeit Gegenstand der Betrachtung ist. Zugrundegelegt wird ei- ne Gruppe von Firmen welche über einen beschränkten Zeitraum eine bekannte Nachfrage nach dem gleichen Gut haben. Werden die Bestellungen gebündelt aufgegeben, können die Firmen Kosten sparen. Ein grundsätzlicher Unter- schied zum Ansatz von Meca et al. (2007) über die Andlersche-Losgrößenformel ist, dass für das Wagner-Whitin-Problem keine direkte Berechnung einer Lö- sung möglich ist. Es kann gezeigt werden, dass dynamische Loßgrößenspiele ausgewogen sind und folglich ihr Kern nicht leer ist. Eine Möglichkeit zur Berechnung von Kernelementen wird nicht aufgezeigt (vgl. van den Heuvel et al. 2007). Hwang und van den Heuvel (2012) betrachten ein dynamisches Loßgrößenspiel mit beschränkter Lagerkapazität und Fehlmengen. Es werden Beschaffungskosten, Lagerhaltungskosten und Fehlmengenkosten unterschie- den. Die Betrachtung erfolgt für zwei verschiedene Kostenstrukuren. Im ersten Fall wird eine konkave Kostenstruktur angenommen und im zweiten Fall li- neare Lagerhaltungs- und Fehlmengenkosten und der Ausschluss spekulativer Motive für Lager- und Fehlmengen. Für beide Kostenstrukturen kann ein effizi- enter Lösungsalgorithmus, für die Berechnung von Kernelementen angegeben werden (vgl. Hwang und van den Heuvel 2012). 3 Das Wagner-Whitin-Problem im Bestellmengenspiel In diesem Kapitel wird zunächst das Konzept des Kerns näher erläutert. Nach- folgend wird das Wagner-Whitin-Problem formuliert und auf den N-Spieler Fall erweitert. Schließlich wird ein Algorithmus zur iterativen Berechnung von Kernelementen vorgestellt, auf das Wagner-Whitin-Problem angewendet und diskutiert.

3.1 Das Konzept des Kerns

An dieser Stelle soll das bereits im zweiten Kapitel angesprochene Konzept des Kerns näher definiert werden. Erstmals inhaltlich beschrieben wurde der Kern durch Francis Ysidro Edgeworth. In seinem Essay Mathematical Psychics beschreibt er stabile Allokationen einer Tauschökonomie für zwei und mehr Teilnehmer (vgl. Edgeworth 1881, S. 17 ff.). Eine systematische Beschreibung des Kerns erfolgte später durch Gillies (vgl. Gillies 1959, S. 47 ff.). Sei N die ge- gebene Anzahl Spieler undn_i der Gesamtkostenanteil des Spielers i ∈ N, dann ist π = (n₁,..., π |N|) ein Vektor, der eine stabile Allokation im Kern darstellt. Ferner sei [Abbildung in dieser Leseprobe nicht enthalten]die charakteristische Funktion oder Koalitionsfunktion eines Spiels, die die Kosten jeder Koalition S ⊆ N bestimmt. Für eine stabile Allokation können zwei Bedingungen angeführt werden. Damit Effizienz vor- liegt, muss [Abbildung in dieser Leseprobe nicht enthalten] gelten. Die Alloaktionn_ist eine Imputation, wenn n_i [Abbildung in dieser Leseprobe nicht enthalten] für alle i gilt. Hierdurch wird verhindert, dass ein Spieler allein geringere Kosten als in der Koalition haben kann. Gleiches gilt für eine Koaltion S ⊂ N ,[Abbildung in dieser Leseprobe nicht enthalten], hier muss gelten das ∑i∈Sn_i ≤ c(S) ist, sodass für S ein Anreiz besteht, eine große Koaltion einzugehen. Eine Imputation die diesen Bedingun- gen genügt, wird als Kernelement bezeichnet.

Der Kern ist durch

Abbildung in dieser Leseprobe nicht enthalten

definiert (vgl. Drechsel und Kimms 2010, S. 310). Es sei an dieser Stelle noch- mals angemerkt, dass der Kern auch mehrere stabile Allokationen umfassen kann. Die Formulierung des Kerns umfasst kein Kriterium für Fairness. So kann es sein, dass eine formal stabile Allokation für ein Problem gefunden wird, diese aber in der Realität von einzelnen Akteuren abgelehnt wird, ob- wohl sie trotz der Unfairness formal besser gestellt sind (vgl. Zelewski 2009, S. 62). Ferner muss nicht unbedingt eine Kernallokation existieren, man spricht hier dann vom leeren Kern (vgl. Owen 2013, S. 214). Im weiteren Verlauf der Arbeit wird in Kapitel 3.3 ein effizienter Alogrithmus zur Ermittlung von Kernallokationen vorgestellt, der auch das Kriterium der Fairness ins Kalkül zieht.

3.2 Annahmen an die Modellierung

In diesem Abschnitt wird die Erweiterung des Wagner-Whitin-Problems auf den N-Spieler-Fall dargelegt, sowie die Eigenschaften des entstehenden koope- rativen Spieles beschrieben, um die Basis für die Ermittlung von Kernelementen zu schaffen.

Ausgangspunkt ist das Wagner-Whitin-Problem, welches bereits in Kapitel 2 im Zusammenhang mit dynamischen Loßgrößenspielen angesprochen worden ist. Ein Unternehmen sieht sich über T Perioden mit einer je Periode bekannten Nachfrage dt mit t = 1, 2, ..., T nach einem einzelnen Gut konfrontiert. Zur De- ckung der Nachfrage in der Periode t, kann eine Bestellung in der gleichen oder einer vorhergehenden Periode ausgelöst werden. Eine Nachfrage dt muss peri- odengleich befriedigt werden. Ferner sind Fehlmengen nicht zulässig. Wird die Lagerung eines Gutes nötig, fallen am Ende der Periode pro Stück Lagerkosten in Höhe von ht an. Es fallen pro ausgelöstem Bestellvorgang bestellfixe Kosten at > 0 und Stückbestellkosten pt an. Gesucht werden die optimalen Bestell- mengen Qt in den jeweiligen Perioden. Das Unternehmen sieht sich also dem klassischen Problem der Loßgrößenplanung in Ansehung von Bestellkosten vs. Lagerhaltungskosten gegenüber. In Abhängigkeit von den Bestellmengen Qt be- finden sich am Ende einer Periode It ≥ 0 Einheiten des Gutes auf Lager, wobei der Lagerbestand zu Beginn der Periode Null o.B.d.A. I0 = 0 ist (vgl. Wagner und Whitin 1958, S. 1770). Das Problem lässt sich als gemischt ganzzahliges Optimierungsproblem darstellen.

Abbildung in dieser Leseprobe nicht enthalten

Die Entscheidungsvariablen dieses Problems sind also die Bestellmenge Qt, die binäre Variable xt (die für xt = 1 anzeigt, dass eine Bestellung in Periode t ausgelöst wird) und die Lagermenge It. Die Variable M ist eine hinreichend große Zahl, z.B. die Summe der Nachfrage dt über alle Perioden. Die Funk- tion (3.2) minimiert die bestellfixen Kosten a, die Stückbestellkosten pt und die Lagerhaltungskosten ht. Die Nebenbedingung (3.3) stellt sicher, dass der Lagerbestand It für jede Periode den Bestand der Vorperiode, plus der Bestell- menge der aktuellen Periode, abzüglich der Periodennachfrage umfasst. Die Nebenbedingung (3.4) sorgt dafür, dass sobald die Bestellmenge in einer Peri- ode positiv ist, die Entscheidungsvariable xt auf xt = 1 steht. Die Forderung in (3.5) verhindert das Auftreten von Fehlmengen und stellt sicher, dass Bedarfe periodengleich gedeckt werden. In (3.6) wird xt als binäre Entscheidungsvaria- ble definiert (vgl. Drechsel 2010, S. 63-64). Für das klassische Wagner-Whitin Problem, bestehen effiziente Lösungsalgorithmen (vgl. z.B. Aggarwal und Park 1993).

Um das vorliegende Problem im Rahmen der kooperativen Spieltheorie zum Einsatz zu bringen, bedarf es einiger Anpassungen. Wie in Kapitel 2 bereits angesprochen, haben van den Heuvel et al. (2007) bewiesen, dass der Kern von Spielen unter den Bedingungen des Wagner-Whitin-Problems nicht leer ist.

Im Bestellmengenspiel wird eine Gruppe von N ≥ 2 mit N = 2, ..., n Firmen be- trachtet. Jede Firma i ∈ N sieht sich einer periodischen individuellen Nachfrage

[...]