Robust inventory routing under demand uncertainty


Seminararbeit, 2017
32 Seiten, Note: 1,0
Moe Schmidt (Autor)

Leseprobe

Inhaltsverzeichnis

Abkürzungsverzeichnis

Abbildungssverzeichnis

Formel- und Symbolverzeichnis

1 Einleitung
1.1 Problemstellung
1.2 Zielsetzung
1.3 Vorgehensweise

2 Inventory Routing Problem
2.1 Literarische Einführung des Inventory Routing Problem
2.2 Grundlagen

3 Zwei Seiten des Inventory Routing Problem
3.1 Vehicle Routing Problem
3.2 Bestandsmanagement

4 Robustheit als Lösung für den Umgang mit Unsicherheiten
4.1 Robuste Optimierung
4.2 Modelle des robusten Inventory Routing Problem
4.2.1 Nominale Formulierung
4.2.2 Lineare robuste Formulierung
4.3 Lösungsansatz Branch-and-Cut Algorithmus
4.4 Beispielrechnung der linearen robusten Formulierung

5 Fazit

Anhang

Literaturverzeichnis

Abkürzungsverzeichnis>

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

Abbildung 1: Das Vehicle Routing Problem

Abbildung 2: Zusammenhang der verschiedenen Modelle

Abbildung 3: Veränderung der Kosten im Zusammenhang mit Gamma [t]

Formel- und Symbolverzeichnis

Mengen:

Abbildung in dieser Leseprobe nicht enthalten

Parameter:

Abbildung in dieser Leseprobe nicht enthalten

Entscheidungsvariablen:

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

1.1 Problemstellung

Gemessen an den Kosten des Umsatzes in Prozent sind die wesentlichen Komponenten der Logistikkosten die Transport- und Lagerbestandskosten. Während die Komponente Transport bei 48,4 % liegt, befindet sich die Komponente Lagerbestand bei 22,9 % aller Logistikkosten.1 Im Bereich dieser beiden Komponenten wird eine Kostenreduktion angestrebt, bei der die unterschiedlichen Kosten bisher getrennt voneinander betrachtet wurden.2 Mit Hilfe einer integrierten Betrachtungsweise der unterschiedlichen Kosten- arten, können oftmals relevante Einsparungen erzielt werden. Deshalb werden Modelle gesucht, die sowohl die Transport- als auch die Lagerkosten minimieren.3 Die Einspa- rungen können infolge von Synergieeffekten der beiden Kostenarten generiert werden. Die Höhe der Transportkosten muss bekannt sein, um zu bestimmen, wann ein Kunde beliefert und wie viel Ware ausgeliefert wird. Auf diese Weise können die Kosten pro Kunde ermittelt werden. Andererseits stehen die Transportkosten in Abhängigkeit zu den tatsächlich durchgeführten Routen. Diese basieren wiederum auf den Informationen über die Kundenauswahl und den Lagerbestand des jeweiligen Kunden.4 In der Praxis ist es immer häufiger der Fall, dass der Logistikdienstleister neben dem Transport auch für den Lagerbestand des Kunden verantwortlich ist.5 Außer der Routenplanung müssen ebenfalls die Liefermengen und die Liefertermine bzw. Lieferzeiten definiert werden. Diese Problemstellung wird als „Inventory Routing Problem“ (IRP) bezeichnet. Das IRP ist oft mit Unsicherheiten in den Daten, die zwischen Logistikdienstleister und Kunden übermittelt werden, verbunden. Dabei ist häufig der Bedarf der Kunden von der Unsicherheit der Daten betroffen und der Kunde erhält somit nicht zufriedenstellende Liefermengen. Deshalb müssen Lösungsansätze gefunden werden, die die Unsicherheit der Daten bzw. fehlende Daten berücksichtigen, um Liefermengen optimal planen und die Kunden zufriedenstellen zu können.6

1.2 Zielsetzung

Die Zielsetzung dieser Arbeit besteht darin, die Herleitung eines Modells zur Darstel- lung des linearen robusten IRP aufzuzeigen. Des Weiteren werden vor allem die robuste Optimierung und die Modelle des Inventory Routing Problems im Mittelpunkt der Un- tersuchung stehen. Abschließend wird ein Lösungsansatz und ein Rechenbeispiel, dass mit Hilfe von AMPL modelliert und mit CPLEX gelöst wird, vorgestellt sowie die Er- gebnisse des Rechenbeispiels interpretiert.

1.3 Vorgehensweise

In dieser Arbeit wird im zweiten Kapitel ein Überblick über das IRP gegeben. Hierbei wird auf die existierende Literatur, die Grundlagen und die Merkmale des Iventory Rou- ting Problems näher eingegangen. Im dritten Kapitel werden die zwei Seiten des Inventory Routing Problems, das Vehicle Routing Problem (VRP) und das Bestands- management, dargestellt. Anschließend wird im vierten Kapitel die Robustheit als Lö- sung für den Umgang mit Unsicherheiten vorgestellt und erläutert. Diesbezüglich wird näher auf die robuste Optimierung und auf die Modelle des Inventory Routing Problems eingegangen. Darüber hinaus folgt in diesem Kapitel die Vorstellung des Lösungsansatz Branch-and-Cut Algorithmus sowie ein Rechenbeispiel der linearen robusten Formulie- rung. Ein abschließendes Fazit fasst die Ausführungen zusammen.

2 Das Inventory Routing Problem

2.1 Literarische Einführung des Inventory Routing Problem

Das IRP ist eine Betrachtungsweise, die seit den 80er Jahren stets weiterentwickelt wurde. Vorreiter des IRP sind Bell et al., die 1983 mit ihrer Arbeit den Grundstein die- ser kontinuierlichen Weiterentwicklung gelegt haben. Ziel dieser Arbeit ist die Erstel- lung eines Plans mit kurzen Laufzeiten, der die zu beliefernden Kunden und die Liefermengen von industriellen Gasen festzulegen.7 In den darauf folgenden Jahren hat sich eine Vielzahl von Autoren mit diesem Problem kritisch auseinandergesetzt.8 Geprägt wurde der Begriff des Inventory Routing von Federgruen und Zipkin im Jahr 1984, die sich mit einperiodigen IRP´s und stochastischen Nachfragen beschäftigt haben.9 Dror und Ball haben sich 1987 dem mehrperiodigen IRP´s gewidmet, allerdings mit begrenz- tem Horizont und konstanten Nachfragen.10 Nach der Jahrtausendwende hat sich Adelman mit der preisgerichteten Annäherung an das IRP mit stochastischer Nachfrage und unbegrenztem Horizont befasst.11 Moin und Salhi haben 2007 den aktuellsten Stand der Technik unter Betrachtung der Nützlichkeit und Begrenzung der Modelle vorge- stellt. Hierbei wurden die Modelle nach ihrem Planungshorizont gegliedert.12 Darüber hinaus wurde das IRP im Zusammenhang mit dem Transport über Seeweg und Straße im Jahre 2010 von Andersson et al. in einem weiteren Artikel dargestellt.13

Das erste exakte Verfahren wurde 2007 von Archetti et al. vorgestellt. In ihrem Artikel stellten sie einen Branch-and-Cut Algorithmus14 vor, mit dem Instanzen mit bis zu 50 Kunden und einem Zeithorizont von drei Einheiten optimal gelöst werden konnten. Wird der Horizont allerdings auf sechs Einheiten erweitert, sinkt die Größe der optimal zu lösenden Instanz auf 30 Kunden.15

Neben der grundlegenden sowie der stochastischen Betrachtungsweise des IRP lassen sich vermehrt robuste Ansätze des IRP finden. Einer der ersten robusten Ansätze wurde 1973 von Soyster veröffentlicht.16 Dieser erste Ansatz befasst sich innerhalb der linea- ren Programmierung mit unsicheren Parametern. Hierbei bedient sich Soyster allerdings ausschließlich der Worst-Case Annahme.17 In einer neueren Veröffentlichung aus dem Jahr 2008 setzt Aghezzaf einen robusten Plan zur Belieferung, für den Fall von unsiche- ren Kundennachfragen und Fahrzeiten, auf.18 Auch Solyali et al. beschäftigen sich in ihrem 2012 veröffentlichen Artikel mit der Formulierung eines robusten, linearen Mo- dells und stellen einen Branch-and-Cut Algorithmus für diesen Fall vor. Auf diese Wei- se können sie Instanzen mit bis zu 30 Kunden und sieben Perioden in annehmbarer Zeit lösen.19

Die in diesem Teil ausgewählten Autoren und ihre Veröffentlichungen stellen nur eine Auswahl an vorhandener Literatur dar.

2.2 Grundlagen

Um die Thematik des IRP eindeutiger zu beleuchten, ist das Vendor-Managed- Inventory (VMI) von besonderer Bedeutung.20 Bei dieser Art des Bestandsmanage- ments ist der Anbieter für das Inventar seines Kunden zuständig. Der Anbieter ist folg- lich verantwortlich für die Verfügbarkeit der Produkte und bestimmt die Menge und den Zeitpunkt der Lieferungen. Mit Hilfe des Sicherheitsbestands wird zudem gewährleistet, dass eine vom Anbieter und Kunden zusammen definierte Menge der Produkte immer im Bestand des Kunden ist. Somit können bei gleichzeitgier Bestandsminderung Wiederbeschaffungszeiten gesenkt, Kosten reduziert und der Servicegrad erhöht wer- den.21 Durch das VMI ergeben sich für den Kunden die Vorteile, dass dieser weniger Aufwand im Rahmen der Bestellungen hat und der Anbieter ist verpflichtet, den Kun- den bedarfsgerecht zu beliefern und Out-of-Stock Situationen zu vermeiden.22 Die Nut- zung des VMI geht mit bestimmten Voraussetzungen einher. Der Kunde muss dem An- bieter alle relevanten Informationen rechtzeitig zur Verfügung stellen und der Anbieter muss diese Informationen mit Hilfe bestimmter Software verarbeiten und zur Planung der Liefermengen weiterverarbeiten. An dieser Stelle entsteht der Konflikt zwischen Transport- und Bestandsplanung, der das IRP charakterisiert.23 Neben den technologi- schen Voraussetzungen spielt die Kooperation zwischen Anbietern und Kunden eine entscheidende Rolle. Es muss ein stetiger Austausch zwischen beiden Parteien stattfin- den und der Kunde muss die Bereitschaft zeigen, die relevanten Informationen bereitzu- stellen und somit Einblick in seine Absätze zuzulassen.24

Das IRP weist keine Grundform auf, kann aber in ihrer Betrachtungsweise unterschie- den werden. Die Nachfrage wird einerseits als deterministisch oder stochastisch be- trachtet und andererseits kann der Planungshorizont als begrenzt oder unbegrenzt be- trachtet werden.25 Zusätzlich kann auch die Lieferfrequenz bewertet werden. Hierzu gehört neben dem Liefertermin auch die Liefermenge. Es besteht die Möglichkeit, dass die Lieferung erst ausgelöst wird, wenn der Bestand vollständig verbraucht ist oder der Sicherheitsbestand unterschritten ist.26 Im Rahmen der Lieferfrequenz müssen Fragen nach Zeit, Menge und Raum beantwortet werden. Wann wird der Kunde beliefert? Wel- che Menge wird geliefert? Welche Route wird gewählt?27 Des Weiteren ist die Anzahl der beteiligten Akteure ein wichtiger Bestandteil der IRP. Je mehr Akteure involviert sind, desto komplexer wird die Situation.28 Es wird zwischen Akteuren mehreren diffe- renziert. Diese können dem Unternehmen angehören und somit findet eine interne Be- lieferung statt oder es kann sich um externe Akteure handeln, die den Grad der Kom- plexität wiederum steigern.29

Das IRP unterliegt einer Vielzahl von Nebenbedingungen. Restriktionen sind elementa- rer Bestandteil dieser Nebenbedingungen. Beispiele für Restriktionen sind Kapazitäts- beschränkungen oder unsicherer Fahrzeitbestimmungen. Der Bestand des Kunden darf auch nicht negativ sein und der Anbieter muss ausreichend Ware zur Verfügung stellen, um die Lieferung zu garantieren. Zudem müssen Restriktionen vorhanden sein, die eine zulässige und vor allem durchführbare Route sicherstellen.30

Das IRP weist auch Beziehungen zu anderen Problemstellungen der Logistik auf. Da- durch ist diese Problemstellung NP-schwer.31 Diese Bezeichnung lässt sich auf die Komplexitätsklassen zurückführen und besagt, dass dieses Problem nicht in determinis- tischer polynomialer Zeit zu lösen ist. Für dieses Problem gibt es noch keine effizienten Algorithmen.32

3 Zwei Seiten des Inventory Routing Problem

3.1 Vehicle Routing Problem

Das IRP beinhaltet in seiner räumlichen Komponente das sogenannte Vehicle Routing Problem (VRP).33 Das Vehicle Routing stellt eine Problemstellung dar, die in der Praxis in der Güterlogistik und auch in der Tourenplanung eine wichtige Rolle spielt. Innerhalb des VRP geht es darum, Kunden mit Hilfe von Lieferfahrzeugen möglichst effizient von einem oder mehreren Depots aus zu beliefern. Gleichzeitig darf dabei keine Nebenbe- dingung verletzt werden. Im einfachsten Fall liegt eine Menge von Fahrzeugen vor, mit denen Kunden in einem bestimmten Gebiet beliefert werden müssen. Dabei muss die Anzahl der Kunden so aufgeteilt werden, dass jedes Fahrzeug eine bestimmte Anzahl von Kunden beliefert. Diese Aufteilung bedarf der Bestimmung möglichst guter Routen der Fahrzeuge.34

In Abbildung 1 wird das VRP grafisch dargestellt und veranschaulicht die Problemstel- lung. Innerhalb dieser Grafik werden die Kunden als Knoten bzw. Knotenpunkte und die fettgedruckten Linien als Route der einzelnen Fahrzeuge gekennzeichnet. Die Linien zwischen den einzelnen Kunden werden als Kanten bezeichnet.

Abb. 1: Das Vehicle Routing Problem

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Chimani, M.; Klein, K.; Mutzel, P., Vehicle, 2009, S. 2.

Die jeweiligen Kanten zwischen den Knoten oder zwischen dem Depot und einem Kno- ten gehen mit bestimmten Kosten und Lieferzeiten einher. In jedem Depot steht nur eine bestimmte Anzahl an Lieferfahrzeugen, mit einer bestimmten Kapazität, zur Verfü- gung.35 Unter Berücksichtigung dieser Anforderungen wird eine entsprechende Route gesucht, die als Start- und Zielpunkt das Depot aufweist und alle Kunden genau einmal angefahren werden sollen. Darüber hinaus müssen bestimmte Restriktionen eingehalten werden. Hierzu zählen z.B. Kapazitäts-, Zeit-, oder Anlieferfensterrestriktionen. Die Kapazitätsrestriktionen werden sowohl mit nicht negativen Nachfragemengen assoziiert als auch mit der Einhaltung der Fahrzeugkapazitäten. Restriktionen der Komponente Zeit sind mit der Kante zwischen den Kunden oder dem Depot und den Kunden ver- bunden. Auf dieser Kante und der gesamten Route müssen die Zeitvorgaben eingehalten werden. Anlieferrestriktionen beziehen sich direkt auf die Kunden. Bestimmte Kunden können nur in definierten Zeitfenstern beliefert werden, z.B. aufgrund von Öffnungszei- ten.36 Dabei ist das übergeordnete Ziel die Minimierung der Transportkosten.37

Das VRP lässt jedoch nicht vollständig in das IRP integrieren. Es bestehen zwar Ge- meinsamkeiten, die die Problemstellung des IRP verständlicher machen, jedoch beste- hen auch Unterschiede zwischen diesen beiden Problemstellungen. Innerhalb des VRP platziert der Kunde seine Bestellung und der Lieferant plant anhand dieser Daten seine Routen. Auch im Hinblick auf den Planungshorizont differenzieren sich die Problem- stellungen. Das VRP bezieht sich in seiner Grundform meist auf die Betrachtung ein- zelner Tage und auf die Erfüllung der einzelnen Kundennachfragen. Das IRP hingegen ist weitsichtiger ausgelegt. Es werden zwar Entscheidungen über Mengen, Routen und Zeiten an einzelnen Tagen einbezogen, allerdings unter Berücksichtigung der Auswir- kungen auf zukünftige Planungen. Durch diese Flexibilität wird jedoch die Entscheidungsfindung komplexer.38

3.2 Bestandsmanagement

Die zweite Seite des IRP stellt das Bestandsmanagement dar. Hierbei steht die zeitliche Komponente im Mittelpunkt und bezieht sich auf den optimalen Liefertermin der Kun- den.39 Das Bestandsmanagement ist ein grundsätzlicher Bestandteil für Unternehmen, die Transporte, Auslieferungen oder Lagerung von physischen Gütern in ihrer Kernauf- gabe sehen, wie z.B. Hersteller und Groß- und Einzelhändler. Dabei kann die Kosten- struktur sehr komplex sein40, aufgrund der Tatsache, dass die Bestände eines deutschen Großhandelsunternehmens durchschnittlich 34% des Umlaufvermögens darstellen.41 Frühzeitige Anlieferungen, die dem geplanten Bedarf bzw. Prognosen nicht entspre- chen, können zu erhöhten Beständen führen.42 Ein hoher Bestand bedeutet nicht, dass Schwankungen in der Nachfrage und der Produktion besser aufgefangen werden kön- nen. Die Lagerbestände müssen dabei immer mit den entstehenden Lagerhaltungskosten ins Verhältnis gesetzt werden, da steigende Lagerkosten den Gewinn eines Unterneh- mens mindern. Um einen effizienten Einsatz des Bestandsmanagements zu gewährleisten, müssen die Ursache für Bestandsaufbau und Bestandsabbau genau betrachtet und analysiert werden, um hieraus gewonnen Potentiale zur Kostenoptimierung zu nutzen.43

[...]


1 Vgl. The Establish Davis Database, Logistics Cost, 2016, S. 7.

2 Vgl. Abdelmaguid, T. et al., Inventory Routing Problem, 2009, S. 1519.

3 Vgl. Chan, L., et al., Inventory-Routing Models, 1998, S. 96.

4 Vgl. Moin, N.H.; Salhi, S., Logistical Overview, 2007, S. 1185 f.

5 Vgl. Andersson, H. et al., Inventory Management, 2010, S. 1516.

6 Vgl. Solyali, O. et al., Demand Uncertainty, 2012, S. 327 f.

7 Vgl. Bell, W. et al., Industrial Gases, 1983, S. 4 ff.

8 Vgl. Hemmelmayr, V. et al., VMI, 2010, S. 686.

9 Vgl. Federgruen, A.; Zipkin, P., Allocation Problem, 1984, S. 1019 ff.

10 Vgl. Dror, M.; Ball, M., Short-Period problem, 1987, S. 819 ff.

11 Vgl. Adelman, D., Stochastic Routing, 2004, S. 499 ff.

12 Vgl. Moin, N.H.; Salhi, S., Logistical Overview, 2007, S. 1185.

13 Vgl. Andersson, H. et al., Inventory Management, 2010, S. 1515.

14 Branch-and-Cut Alorithmen sind Branch-and-Bound Algorithmen, bei denen, entlang des Entschei- dungsbaums, in jedem Knoten das Schnittebenenverfahren angewendet wird. Vgl. Grünert, T.; Irnich, S., Optimierung, 2005, S. 139.

15 Vgl. Archetti, C. et al., Branch-and-Cut, 2007, S. 382 ff.

16 Vgl. Soyster, A., Linear Programming, 1973, S. 1154 ff.

17 Vgl. Soyster, A., Linear Programming, 1973, S. 1156; Solyali, O. et al., Demand Uncertainty, 2012, S. 328.

18 Vgl. Aghezzaf, E-H., Robust Distribution Planning, 2008, S. 1055 ff.

19 Vgl. Solyali, O. et al., Demand Uncertainty, 2012, S. 327 ff.

20 Vgl. Abdelmaguid, T. et al., Inventory Routing Problem, 2009, S. 1519.

21 Vgl. Piontek, J., Logistikmanagement, 2009, S. 98.

22 Vgl. Archetti, C. et al., Branch-and-Cut, 2007, S. 382 f.

23 Vgl. Kleywegt, A. et al., Stochastic Inventory, 2004, S. 42.

24 Vgl. Piontek, J., Logistikmanagement, 2009, S. 98 f.

25 Vgl. Solyali, O. et al., Demand Uncertainty, 2012, S. 327.

26 Vgl. Bertazzi, L.; Speranza, G., IRP, 2012, S. 311 f.

27 Vgl. Song, J-H.; Savelsbergh, M., Measurement, 2007, S. 44; Moin, N.H.; Salhi, S., Logistical Over- view, 2007, S. 1186.

28 Vgl. Andersson, H. et al., Inventory Management, 2010, S. 1517 f.

29 Vgl. Chan, L. et al., Inventory-Routing Models, 1998, S. 96.

30 Vgl. Archetti, C. et al., Branch-and-Cut, 2007, S. 383.

31 Vgl. Archetti, C. et al., Branch-and-Cut, 2007, S. 383.

32 Vgl. Nickel, S. et al., Operations Research, 2011, S. 201 f.

33 Vgl. Andersson, H. et al., Inventory Management, 2010, S. 1518.

34 Vgl. Toth, P.; Vigo, D., VRP, 2002, S. 2 f.

35 Vgl. Toth, P.; Vigo, D., VRP, 2002, S. 2 f.

36 Vgl. Laporte, G.; Osman, I., Routing, 1995, S. 230 f; Lau, H-C. et al., Time Windows, 2003, S. 559 ff.

37 Vgl. Toth, P.; Vigo, D., VRP, 2002, S. 2 f.

38 Vgl. Toth, P.; Vigo, D., VRP, 2002, S. 309 f.

39 Vgl. Lau, H-C. et al., Time Windows, 2003, S. 662; Trudeau, P.; Dror, M., Stockouts, 1992, S. 172.

40 Vgl. Andersson, H. et al., Inventory Management, 2010, S. 1518.

41 Vgl. Piontek, J., Logistikmanagement, 2009, S. 17.

42 Vgl. Günther H-O.; Tempelmeier, H., Produktion, 2012, S. 269.

43 Vgl. Piontek, J., Logistikmanagement, 2009, S. 17.

Ende der Leseprobe aus 32 Seiten

Details

Titel
Robust inventory routing under demand uncertainty
Hochschule
FOM Hochschule für Oekonomie & Management Essen, Standort Duisburg
Note
1,0
Autor
Jahr
2017
Seiten
32
Katalognummer
V459996
ISBN (eBook)
9783668908260
ISBN (Buch)
9783668908277
Sprache
Deutsch
Schlagworte
Inventory Routing, IRP, Inventory Routing Problem
Arbeit zitieren
Moe Schmidt (Autor), 2017, Robust inventory routing under demand uncertainty, München, GRIN Verlag, https://www.grin.com/document/459996

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Robust inventory routing under demand uncertainty


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden