Dynamische Tourenplanung

Aufderheide, Björn

Dynamische Tourenplanung

Eine Literaturübersicht

von Björn Aufderheide (Autor:in)

BWL - Beschaffung, Produktion, Logistik

Zusammenfassung

Inhaltsangabe:Einleitung:
Tourenplanungsprobleme gehören zu den am häufigsten untersuchten Problemstellungen des Operations Research. Dennoch beschäftigt sich der weitaus größere Anteil der Arbeiten mit statischen Tourenplanungsproblemen. Sie unterliegen der stark vereinfachenden Annahme der Planungssicherheit durch unveränderliche Informationen im Zeitablauf. In Problemstellungen der realen Welt sind allerdings fast alle Parameter mit Unsicherheit behaftet und ändern sich im Zeitablauf. Die Berücksichtigung dieses Aspektes für eine möglichst realitätsnahe Planung findet in der dynamischen Tourenplanung statt.
Gerade in der heutigen Zeit, in der die wirtschaftliche, ökologische Nachhaltigkeit und die Just in Time Produktion im Rahmen der Öffnung der Märkte und der Globalisierung immer mehr in den Blickpunkt geraten, ist es wesentlich die notwendigen logistischen Dienstleistungen so effizient wie möglich zu gestalten. Die gestiegenen Rechnerleistungen und die Entwicklung im Bereich der Kommunikations- und Informationstechnologie bietet immer neuere Möglichkeiten große Mengen an Echtzeitdaten effektiv zu verarbeiten und solche Systeme kostengünstig für Unternehmen, die logistische Aufgaben im Bereich der Tourenplanung zu bewältigen haben, bereitzustellen. Des Weiteren zeigen die praktischen Anwendungsgebiete durch ihre Vielfalt und Breite, dass ein großer Bedarf an intelligenten Lösungen durch eine dynamische Tourenplanung besteht.
Was in dem wachsenden Gebiet der dynamischen Tourenplanung Diskussionsgegenstand in der Literatur ist, wird in dieser Arbeit durch einen Überblick im Rahmen der Grundlagen der dynamischen Tourenplanung und der grundlegenden Unterscheidungsmöglichkeiten gegenüber einer statischen Tourenplanung aufgezeigt. Bevor der Aufbau und Gang dieser Arbeit im Folgenden detaillierter behandelt wird, sollen zunächst der Gegenstand und die Zielstellung dieser Arbeit mit den dahinter stehenden Fragestellungen erfolgen.
Problemstellung:
Die dynamischen Tourenplanungsprobleme wurden gerade in den letzten Jahren stärker erforscht. Diese Arbeit soll einen Literaturüberblick über diesen Themenbereich der Logistik geben. Dabei wird zunächst auf den Gegenstand dieser Arbeit eingegangen, um anschließend anhand der einzelnen Fragestellungen die Zielstellung dieser Arbeit aufzuzeigen.
Im Rahmen eines Literaturüberblickes sollen in dieser Arbeit die wesentlichen Bereiche der dynamischen Tourenplanung beleuchtet werden. Daher kann und soll eine […]

Leseprobe

Inhaltsverzeichnis

Björn Aufderheide

Dynamische Tourenplanung

Eine Literaturübersicht

ISBN: 978-3-8366-4128-9

Herstellung: Diplomica® Verlag GmbH, Hamburg, 2010

Zugl. Universität Bremen, Bremen, Deutschland, Diplomarbeit, 2009

Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,

insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von

Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der

Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,

bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung

dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen

der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik

Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich

vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des

Urheberrechtes.

Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in

diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,

dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei

zu betrachten wären und daher von jedermann benutzt werden dürften.

Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können

Fehler nicht vollständig ausgeschlossen werden und der Verlag, die Autoren oder

Übersetzer übernehmen keine juristische Verantwortung oder irgendeine Haftung für evtl.

verbliebene fehlerhafte Angaben und deren Folgen.

http://www.diplomica.de, Hamburg 2010

Inhaltsverzeichnis

Inhaltsverzeichnis ... I

Abbildungsverzeichnis ... III

Tabellenverzeichnis ... IV

Abkürzungsverzeichnis... V

Symbolverzeichnis ...VII

Einleitung ...1

1.1

Gegenstand und Ziel der Arbeit...1

1.2

Aufbau der Arbeit...2

Grundlagen der dynamischen Tourenplanung...4

2.1

Einordnung in die Logistik...4

2.2 Begriffsbildung...5

2.3 Das

Problemfeld ...8

2.4 Anwendungsbereich ...14

Dynamik in Tourenplanungsproblemen ...17

3.1

Herkunft der Dynamik...17

3.2

Komplexität von Tourenplanungsproblemen ...18

3.3

Grad der Dynamik (DOD)...20

3.4

Umgang mit der Dynamik ...24

Wesentliche Unterschiede zur statischen Tourenplanung...29

4.1 Zeitliche

Aspekte...29

4.1.1

Der Faktor Zeit...29

4.1.2

Offener Planungshorizont ...30

4.1.3

Modifizierte Zeitfensterrestriktionen ...31

4.2 Informationen ...31

4.2.1

Unsicherheit zukünftiger Informationen...31

4.2.2

Wichtigkeit unmittelbarer Informationen ...33

4.2.3

Aktualisierung der Informationsgrundlage ...34

4.3 Entscheidungsrelevante

Aspekte ...34

4.3.1

Revision bereits getroffener Entscheidungen ...35

4.3.2

Zurückstellen von Aufträgen...38

4.3.3

Integration der Warteschlangentheorie ...39

4.3.4

Zielsetzungen ...41

4.4 Sonstige

Aspekte ...43

4.4.1

Flexibilität der Flottengröße ...43

4.4.2

Rechenzeiten ...44

4.4.3

Weitere Unterschiede ...45

Voraussetzungen einer dynamischen Tourenplanung ...47

5.1 Technische

Komponenten ...47

5.2

Notwendigkeit der dynamischen Tourenplanung...49

Zusammenfassung und Ausblick ...51

6.1

,,State of the Art" ...51

6.2 Herausforderungen ...53

Literaturverzeichnis ...56

III

Abbildungsverzeichnis

Abbildung 1: Supply-Chain-Planning-Matrix (Ohrt, 2008:6)...5

Abbildung 2: Vergleich verschiedener Definitionsansätze (Richter, 2005:68)...7

Abbildung 3: Dynamisches Tourenplanungsszenario (eigene Darstellung) ...21

Abbildung 4: Unterschiedliche Verteilung dynamischer Kunden (Richter, 2005:113) ...21

Abbildung 5: Reaktionszeiten (Richter, 2005:113)...22

Abbildung 6: Klassifizierung nach DOD und Zielkriterium (Larsen, 2000:63) ...23

Abbildung 7: Literaturüberblick (Larsen, Madsen und Solomon 2008:208) ...28

Abbildung 8: Resequencing-Entscheidungen (Psaraftis, 1988:227f.)...36

Abbildung 9: Reassignment-Entscheidungen (Psaraftis, 1988:228) ...37

Abbildung 10: Zurückstellung eines Kundenauftrages (Psaraftis, 1988:230)...39

Abbildung 11: Datenfluss im GPS-System (Larsen, Solomon und Madsen, 2008:202) ...48

Tabellenverzeichnis

Tabelle 1: Merkmale von Tourenplanungsproblemen (Lackner, 2003:16ff.) ...14

Tabelle 2: Rechenzeiten (Richter, 2005:30)...20

Abkürzungsverzeichnis

Collegial Communication

CDVRP:

Capacitated Dynamic Vehicle Routing Problem

DARP:

Dial-A-Ride Problem

DDARP:

Dynamic Dial-A-Ride Problem

DDARPTW: Dynamic Dial-A-Ride Problem with Time Windows

DMDVRP: Dynamic Multi Depot Vehicle Routing Problem

DMPRP:

Dynamic Multi Period Routing Problem

DOD:

Degree of Dynamic

DPDP:

Dynamic Pickup & Delivery Problem

DSDVRP:

Dynamic Split Delivery Vehicle Routing Problem

DTDVRP:

Dynamic Time-Dependent Vehicle Routing Problem

DTRP:

Dynamic Traveling Repairman Problem

DTSP:

Dynamic Traveling Salesman Problem

DTSPTW:

Dynamic Traveling Salesman Problem with Time Windows

DVRP:

Dynamic Vehicle Routing Problem

DVRPHE:

Dynamic Vehicle Routing Problem with heterogeneous Vehicles

DVRPTW: Dynamic Vehicle Routing Problem with Time Windows

EDOD:

Effective Degree of Dynamism

ERP:

Enterprise Resource Planning

FCFS:

First Come First Serve Strategie

GEN:

Generation Strategie

GIS:

Geographical Information Systems

GLONASS: Global Navigation System

GPRS:

General Packet Radio Service

GPS:

Global Positioning System

GSM:

Global System for Mobile Communications

JIT:

Just in Time

KC:

Knowledge-based Collegial Communication

KS:

Knowledge-based Synchronization

mod TSP:

modifizierte TSP Strategie

MPGA :

Modified Probabilistic Gradual Add

MPMS:

Initial Points Multiple Strategien

MPSS:

Multiple Initial Points Single Strategie

MTF:

Many-to-few

MTM:

Many-to-many

MTO:

Many-to-one

NN:

Nearest Neighbour Strategie

PART:

Partitioning Strategie

PDP:

Pickup & Delivery Problem

PGA:

Probabilistic Gradual Add

PNN:

Probabilistic Nearest Neighbour

PTSP:

Probabilistic Traveling Salesman Problem

PVRP:

Probabilistic Vehicle Routing Problem

RS:

Rigid Synchronization

SEO:

Single Event Optimization

SFC:

Space Filling Curve Strategie

SMS:

Short Message System

SPMS:

Single Initial Point Multiple Strategien

SPSS:

Single Initial Point Single Strategie

SQM:

Stochastic Queue Median Strategie

SVRP:

Stochastic Vehicle Routing Problem

TSP:

Traveling Salesman Problem

TSP:

Traveling Salesman Problem Strategie

VRP:

Vehicle Routing Problem

VII

Symbolverzeichnis

Ende der Reaktionszeit

Ankunftsrate von Kunden (Poisson-Verteilung)

: Dynamische

Kunden

: Statische

Kunden

: Gesamtkundenanzahl

PH: Planungshorizont

Reaktionszeit des Kunden i

: Zeitpunkt

Kapitel 1

Einleitung

Tourenplanungsprobleme gehören zu den am häufigsten untersuchten Problemstellungen des Operati-

ons Research. Dennoch beschäftigt sich der weitaus größere Anteil der Arbeiten mit statischen Tou-

renplanungsproblemen. Sie unterliegen der stark vereinfachenden Annahme der Planungssicherheit

durch unveränderliche Informationen im Zeitablauf. In Problemstellungen der realen Welt sind aller-

dings fast alle Parameter mit Unsicherheit behaftet und ändern sich im Zeitablauf. Die Berücksichti-

gung dieses Aspektes für eine möglichst realitätsnahe Planung findet in der dynamischen Tourenpla-

nung statt.

Gerade in der heutigen Zeit, in der die wirtschaftliche, ökologische Nachhaltigkeit und die ,,Just in

Time" Produktion im Rahmen der Öffnung der Märkte und der Globalisierung immer mehr in den

Blickpunkt geraten, ist es wesentlich die notwendigen logistischen Dienstleistungen so effizient wie

möglich zu gestalten. Die gestiegenen Rechnerleistungen und die Entwicklung im Bereich der Kom-

munikations- und Informationstechnologie bietet immer neuere Möglichkeiten große Mengen an Echt-

zeitdaten effektiv zu verarbeiten und solche Systeme kostengünstig für Unternehmen, die logistische

Aufgaben im Bereich der Tourenplanung zu bewältigen haben, bereitzustellen. Des Weiteren zeigen

die praktischen Anwendungsgebiete durch ihre Vielfalt und Breite, dass ein großer Bedarf an intelli-

genten Lösungen durch eine dynamische Tourenplanung besteht.

Was in dem wachsenden Gebiet der dynamischen Tourenplanung Diskussionsgegenstand in der Li-

teratur ist, wird in dieser Arbeit durch einen Überblick im Rahmen der Grundlagen der dynamischen

Tourenplanung und der grundlegenden Unterscheidungsmöglichkeiten gegenüber einer statischen

Tourenplanung aufgezeigt. Bevor der Aufbau und Gang dieser Arbeit im Folgenden detaillierter be-

handelt wird, sollen zunächst der Gegenstand und die Zielstellung dieser Arbeit mit den dahinter ste-

henden Fragestellungen erfolgen.

1.1

Gegenstand und Ziel der Arbeit

Die dynamischen Tourenplanungsprobleme wurden gerade in den letzten Jahren stärker erforscht.

Diese Arbeit soll einen Literaturüberblick über diesen Themenbereich der Logistik geben. Dabei wird

zunächst auf den Gegenstand dieser Arbeit eingegangen, um anschließend anhand der einzelnen Fra-

gestellungen die Zielstellung dieser Arbeit aufzuzeigen.

Im Rahmen eines Literaturüberblickes sollen in dieser Arbeit die wesentlichen Bereiche der dyna-

mischen Tourenplanung beleuchtet werden. Daher kann und soll eine sehr tiefe Durchdringung gewis-

ser Sachverhalte nicht erfolgen. Die Literaturübersicht findet sukzessive über die Auseinandersetzung

mit den wesentlichen unten erläuterten Fragestellungen in dem Themenbereich der dynamischen Tou-

renplanung statt. Dabei ermöglicht es der behandelte Themenbereich, die grundlegende Literatur die-

ses Bereiches anhand eines möglichst umfassenden Überblicks wiederzuspiegeln. Für eine detaillierte

mathematische Modellbeschreibung dynamischer Planungsprobleme wird hier auf die einzelnen Lite-

raturquellen verwiesen, da hier eine verbale Beschreibung der verschiedenen Problemstellungen näher

liegt. Im Folgenden sollen nun die grundlegenden Fragestellungen dieser Arbeit genannt werden.

Im zweiten Kapitel steht daher die Frage nach der Einordnung in den Themenbereich und der

Abgrenzug zu anderen Problemstellungen im Vordergrund. Deshalb wird in einem ersten Schritt ge-

schaut, wo die dynamische Tourenplanung im Kontext der betriebswirtschaftlichen Logistik angesie-

delt ist. Dann ist die Frage, wie die dynamische Tourenplanung aufgrund der grundlegenden Begriff-

lichkeiten und Definitionen von anderen Problemklassen der Tourenplanung genauer abgegrenzt wer-

den kann. Danach ist es interessant, wie die einzelnen Problemstellungen innerhalb des Bereiches der

dynamischen Tourenplanung aussehen, um das Problemfeld weiter abzugrenzen. Anschließend ist die

Frage, wo die dynamische Tourenplanung in der Praxis angewendet wird.

Im dritten Kapitel steht die Dynamik in Tourenplanungsproblemen im Mittelpunkt. Die dabei ge-

stellten Fragen sind, welche Eingangsinformationen sind in dynamische Planungssituationen mit Un-

sicherheit behaftet, also wo kommt die Dynamik her? Was hat die Dynamik für Auswirkungen auf die

Komplexität von Tourenplanungsproblemen? Wie kann die Dynamik abgebildet oder gemessen wer-

den? Abschließend ist die Frage wie der Dynamik dann entgegnet wird und welche gängigen Ansätze

zur Lösung von dynamischen Tourenplanungsproblemen es gibt.

Im vierten Kapitel wird der Frage nachgegangen, was weitere grundlegende Unterscheidungs-

merkmale nach Psaraftis zwischen statischen und dynamischen Tourenplanungsproblemen bezüglich

der zeitlichen Dimension, der Informationen, entscheidungsrelevanter und weiterer in der Literatur

gefundener Aspekte sind. Außerdem ist die Frage, wie bis jetzt in der Literatur darauf eingegangen

wurde.

Abschließend wird im fünften Kapitel die Frage gestellt, was einerseits die technischen Vorrausset-

zungen einer dynamischen Tourenplanung sind und was eine dynamische Tourenplanung notwendig

erscheinen lässt. In Bezug auf die gestellten Fragestellungen ergibt sich daher der folgende Aufbau

und Gang dieser Arbeit.

1.2

Aufbau der Arbeit

In Kapitel 2 sollen die wesentlichen Grundlagen der dynamischen Tourenplanung für eine weitere

Vertiefung und eine erste Einordnung in den Themenbereich geschaffen werden. Deshalb bietet sich in

Kapitel 2.1 eine kurze Einordnung der Tourenplanung in das Aufgabengebiet der betriebswirtschaftli-

chen Logistik an, um anschließend in Kapitel 2.2 die grundlegenden Begriffe und Definitionen für

eine bessere Abgrenzung der dynamischen Tourenplanung von anderen Problemklassen aufzuzeigen.

Im darauf folgenden Kapitel 2.3 werden dann einzelne Problemstellungen der dynamischen Touren-

planung näher betrachtet, um das Problemfeld aufzuzeigen. Abschließend wird in Kapitel 2.4 der gro-

ße Anwendungsbereich der dynamischen Tourenplanung dargestellt, um einen Überblick über den

Einsatzbereich in der Praxis zu geben.

In Kapitel 3 wird die Dynamik in Tourenplanungsproblemen näher betrachtet. Dabei beschäftigt

sich Kapitel 3.1 näher mit Eingangsinformationen, die in Anlehnung an die reale Welt mit Unsicher-

heit behaftet sind und daher in einer dynamischen Tourenplanung berücksichtigt werden sollten. Zwar

ist die Berücksichtigung dynamischer Aspekte eine wichtige Erweiterung des klassischen Tourenpla-

nungsproblems, aber die Auswirkungen auf die Komplexität der dynamischen Problemstellungen

werden in Kapitel 3.2 behandelt. Anschließend wird in Kapitel 3.3 anhand einer bedeutenden Kenn-

zahl zur Charakterisierung dynamischer Tourenplanungsprobleme der Grad der Dynamik (DOD) the-

matisiert. Abschließend werden in Kapitel 3.4 die besonderen Herausforderungen im Umgang mit der

Dynamik erörtert und die gängigsten Ansätze zur Lösung von dynamischen Tourenplanungsproble-

men angeführt.

In Kapitel 4 werden die

grundlegenden Unterscheidungsmerkmale zwischen statischen und dyna-

mischen Tourenplanungsproblemen im Einzelnen diskutiert. Einerseits nehmen die zeitlichen Aspekte

gerade in der dynamischen Tourenplanung einen bedeutenden Stellenwert ein. In Kapitel 4.1 wird

daher die zeitliche Dimension als ersten wesentlichen Unterschied zwischen statischen und dynami-

schen Tourenplanungsproblemen behandelt, während daneben auch der Planungshorizont unterschie-

den wird. Dazu zählen des Weiteren modifizierte Zeitfensterrestriktionen, soweit diese berücksichtigt

werden. In Kapitel 4.2 werden die Eingangsinformationen näher beleuchtet. Das betrifft insbesondere

die Unsicherheit von weiter in der Zukunft liegenden Informationen, und daraus resultierend eine grö-

ßere Wichtigkeit von unmittelbaren Informationen. Auch die fortlaufende Aktualisierung der Informa-

tionsgrundlage in dynamischen Tourenplanungsproblemen fällt in dieses Kapitel. Anschließend wer-

den in Kapitel 4.3 entscheidungsrelevante Aspekte in dynamischen Problemstellungen vertieft. Das

umfasst die Revision bereits getroffener Entscheidungen oder das vorläufige Zurückstellen und Auf-

schieben von ungünstigen Kundenaufträgen, sowie die Integration der Warteschlangentheorie, falls

ungünstige Kundenaufträge nicht außer Acht gelassen werden sollen. Und auch die Zielsetzungen in

dynamischen Tourenplanungsproblemen werden hier betrachtet. Schließlich werden in Kapitel 4.4

unter sonstigen Aspekten dann die Flexibilität der Flottengröße und die Rechenzeiten vor weiteren in

der Literatur gefundenen Anregungen für Unterschiede behandelt. Darunter fallen die Unterscheidung

anhand von verwendeten Lösungsverfahren, die Unterschiede in der Art der Aufgabenstellung und die

Einbeziehung von Kursänderungen.

In Kapitel 5 werden dann die Vorraussetzungen thematisiert, die eine dynamische Tourenplanung

ermöglichen und eine effektiveren Gestaltung hilfreich sind.

Um in einer globalisierten Welt, in der

der Wettbewerbsdruck zunimmt, die effiziente Verteilung der produzierten Güter zu gewährleisten,

muss gerade die Tourenplanung den dynamischen Problemstellungen entsprechen können. Welche

technologischen Rahmenbedingungen durch Entwicklungen dafür geschaffen wurden, wird in Kapitel

5.1 dargestellt. Anschließend wird in Kapitel 5.2 noch einmal betont werden, wie notwendig eine dy-

namische Tourenplanung ist und was für ein Nutzen aus ihr entspringt.

Zum Ende der Arbeit werden in Kapitel 6 die Ergebnisse noch einmal in Bezug auf die im vorheri-

gen Kapitel gestellten Fragen zusammengefasst. Das geschieht in Kapitel 6.1 durch ein ,,State of the

Art", während im Anschluss dann weitere Herausforderungen im Bereich der dynamischen Touren-

planung abschließend in Kapitel 6.2 genannt werden.

Kapitel 2

Grundlagen der dynamischen Tourenplanung

Nachdem im einleitenden ersten Kapitel zunächst der Gegenstand und die Zielstellung, sowie der

Aufbau und der Gang dieser Arbeit vorgestellt wurden, sollen nun im Folgenden wesentliche Grund-

lagen der dynamischen Tourenplanung für eine weitere Vertiefung geschaffen werden. Deshalb bietet

sich in Kapitel 2.1 eine kurze Einordnung der Tourenplanung in das Aufgabengebiet der betriebswirt-

schaftlichen Logistik an, um anschließend in Kapitel 2.2 die grundlegenden Begriffe und Definitionen

für eine bessere Abgrenzung der dynamischen Tourenplanung von anderen Problemklassen aufzuzei-

gen. Im darauf folgenden Kapitel 2.3 werden dann einzelne Problemstellungen der dynamischen Tou-

renplanung näher betrachtet, um das Problemfeld aufzuzeigen. Abschließend wird in Kapitel 2.4 der

große Anwendungsbereich der dynamischen Tourenplanung dargestellt, um einen Überblick über den

Einsatzbereich in der Praxis zu geben.

2.1

Einordnung in die Logistik

Die betriebswirtschaftliche Logistik beschäftigt sich mit Güter- und Informationsflüssen vom Liefe-

ranten in das Unternehmen, innerhalb des Unternehmens und vom Unternehmen zum Kunden. Aufga-

ben, die übernommen werden müssen sind dabei die Planung, Steuerung und Kontrolle von Transport-

und Lagerhaltungssystemen. Dabei stellt die effiziente Versorgung des Kunden mit dem richtigen

Produkt oder der richtigen Dienstleistung zum richtigen Zeitpunkt, im richtigen Zustand und am rich-

tigen Ort zu minimalen Kosten die Hauptaufgabe dar, siehe dazu Pfohl (2000:11f.).

In Abbildung 1 sind die verschiedenen Phasen des Güter- und Informationsflusses in verbundenen

logistischen Funktionsbereichen, sowie eine gängige Strukturierung der logistischen Aufgaben zu

sehen. Dort findet des Weiteren eine idealtypische Einteilung in die Phasen der Beschaffung, Produk-

tion, Distribution und Absatz statt, wobei die Entsorgung hier nicht weiter betrachtet werden soll.

Die Distributionslogistik stellt dabei einen Teilbereich dar, der sich hauptsächlich auf den Güter-

und Informationsfluss vom Absatzlager hin zum Absatzmarkt bezieht. Die Planung erfolgt in diesem

Teilbereich getrennt. Aufgrund der Länge des Planungszeitraumes wird die Distributionslogistik in

strategische, taktische und operative Aufgabenfelder unterteilt. Die strategische Planung hat lang-

fristigen Charakter mit komplexen Planungsstrukturen. Im Gegensatz dazu, weist die operative Pla-

nung einen kurzfristigen Zeithorizont mit einem hohen Grad detaillierter Problemstellungen auf. Die

strategische Distributionslogistik beinhaltet z.B. die Festlegung der Standortwahl, der Distributions-

struktur, der Lager, der Vertriebsstrukturen und der Transportwege. Daneben fallen beispielsweise die

Festlegung des Lieferbereiches und der Fuhrparkgröße unter die mittelfristigen taktischen Aufgaben-

stellungen, wie es Fleischmann, Meyr und Wagner (2005:89) zuordnen. Während die operative Distri-

butionslogistik sich auf die Auftragsabwicklung, die Lagerhaltung, die Verpackung und den Waren-

transport einschließlich der konkreten Planung der Touren konzentriert. Die Tourenplanung lässt sich

deshalb als Teilaufgabe der operativen Distributionslogistik zuordnen (siehe Lackner (2004:7f.). Auch

die dynamische Tourenplanung wird den operativen Aufgaben der Distributionslogistik zugeschrie-

ben. Durch die dynamischen Eingangsinformationen muss mehrmals täglich ein neuer Tourenplan

aufgestellt werden, was sogar einen noch kurzfristigeren Charakter als die klassische Tourenplanung

bedeutet. Zwar gibt es auch mittelfristige oder langfristige Planung von Touren wie bei der Fahrpla-

nerstellung von Bussen und Zügen, allerdings zählen diese zu den Ausnahmen.

Abbildung 1: Supply-Chain-Planning-Matrix (Ohrt, 2008:6)

Auch wenn die verschiedenen Planungsbereiche getrennt voneinander betrachtet werden, bestehen

zwischen den einzelnen Aufgabenbereichen wechselseitige Interdependenzen. Die Planung einer dy-

namischen Tourenplanung sollte daher über alle Aufgabenbereiche integriert sein. Beispielsweise be-

einflusst die Anzahl der Auslieferungslager, die Festlegung eines Liefergebietes oder die Größe des

Fuhrparks die Länge oder Anzahl der Touren. Und umgekehrt können diese Touren bei zu hohen Kos-

ten Auswirkung auf die strategischen Entscheidungen im Hinblick auf die Standortwahl haben. Nähe-

res hierzu findet sich bei Lackner (2003:7ff.), Richter (2005:14ff.) und Ohrt (2008:6).

Nachdem nun eine erste Einordnung in die betriebswirtschaftliche Logistik erfolgte und die dyna-

mische Tourenplanung als Teilaufgabe der operativen Distributionslogistik zu verstehen ist, soll eine

weitere Abgrenzung und Definition der wesentlichen Begrifflichkeiten erfolgen.

2.2

Begriffsbildung

Nach der allgemeinen Einordnung in die Logistik führt dieses Kapitel grundlegende Begriffe und De-

finitionen ein. In der Literatur, die überwiegend englischsprachig ist, existieren neben dem Begriff

,,dynamic" auch Bezeichnungen wie ,,real-time" oder ,,on-line". Gemeint ist damit der dynamische

Aspekt. Um eine klarere Vorstellung über den Begriff der ,,dynamischen" Tourenplanung zu erlangen,

ist es sinnvoll sich die Definitionen von statischen und dynamischen Problemstellungen und weiteren

Begrifflichkeiten anzuschauen.

Einer der ersten, der sich mit dem dynamischen Tourenplanungsproblem als Erweiterung des tradi-

tionellen statischen Problemfeldes auseinander gesetzt hat, ist Psaraftis (1988:224). Nach seiner Defi-

nition ist ein Tourenplanungsproblem statisch:

[...] if the assumed inputs to this problem do not change, either during the execution of

the algorithm that solves it, or during the eventual execution of the route.

Demnach ist ein Tourenplanungsproblem statisch, wenn sich die Informationen (wie z. B. Ort der

Lieferung, Fahrzeiten, Kundennachfrage oder Servicezeit beim Kunden) für das Problem nicht ändern,

weder bei Ausführung des Lösungsalgorithmus, noch während der Tour.

Dem Entscheidungsträger

müssen alle Informationen gleichzeitig mit der Bestimmung der Menge von Touren für das Problem

vor dem Planungsprozess bekannt sein. Es bedarf daher keine mehrmalige Aktualisierung der Pla-

nungsergebnisse vorangehender Planungsschritte, wie Psaraftis (1995:150) es in einer späteren Arbeit

noch einmal fest hält. Madsen, Larsen und Solomon (2007:21) betonen auch die zeitliche Dimension,

der eine wichtige Rolle zukommt. Denn, wie aus dieser Definition zu erkennen ist, sind alle planungs-

relevanten Informationen vor dem Planungsprozess und der Optimierung der Touren bekannt. Außer-

dem ändern diese sich nicht nachdem die Touren geplant wurden.

Auf der anderen Seite definiert Psaraftis (1988:224f.) das dynamische Tourenplanungsproblem im

Folgenden:

[...] inputs may (and, generally, will) change (or be updated) during the execution of

the algorithm and the eventual execution of the route.

Darunter ist zu verstehen, dass im Gegensatz zur statischen Tourenplanung sich die Informationen

in einem dynamischen Tourenplanungsproblem während der Durchführung der Tour oder des Lö-

sungsalgorithmus ändern können oder aktualisiert werden. Wesentlich ist, dass nicht alle Informatio-

nen vor dem Planungsprozess bekannt sind. Informationen können sich parallel zur Ausführung der

Touren ändern. Das geschieht Beispielsweise, wenn neue Kunden hinzukommen, nachdem die Touren

geplant wurden.

Deshalb müssen die Planungsergebnisse vorheriger Planungsschritte mehrmals aktua-

lisiert werden, und der Lösungsalgorithmusprozess gleichzeitig oder parallel stattfinden. Wie aus der

Definition von Psaraftis zu erkennen ist, spielt die zeitliche Dimension auch hier eine wichtige Rolle.

Denn nicht alle planungsrelevanten Informationen sind vor dem Planungsprozess und der Optimierung

der Touren bekannt. Außerdem können sich diese, nachdem die Touren geplant wurden, ändern. Das

heißt auch, dass das Problem dynamisch ist, wenn einige Informationen im Voraus bekannt sind, aber

der Rest erst im Zeitablauf generiert wird.

In der Literatur ist eine grundsätzliche Abgrenzung von statischen und dynamischen Tourenpla-

nungsproblemen vorzufinden. Allerdings finden noch weitere Abgrenzungen zwischen stochastischen

oder deterministischen Problemstellungen statt. Gietz (1994:12) und Vogt (1998:45) benutzen auch

den Begriff der stochastischen Tourenplanung. Eine Problemstellung ist dann stochastisch, wenn die

Eingangsinformationen stochastisch sind. Das sind beispielsweise die Fälle, wenn die tatsächliche

Nachfragemenge erst beim Kunden erfahren wird oder Fahrzeiten zu bestimmten Tageszeiten mit

Wahrscheinlichkeiten bewertet sind. Genaue Daten liegen in solchen Fällen erst während der Durch-

führung einer Tour oder kurz vor dem Beginn der Tour vor. Durch die Bewertung mit Wahrschein-

lichkeiten wird erreicht, dass der dynamische Charakter der Eingangsinformationen mit einbezogen

werden kann. Da alle Eingangsdaten bekannt sind, bevor die Touren geplant sind, wird die stochasti-

sche Tourenplanung unter der statischen Tourenplanung eingeordnet.

Zur dynamischen Tourenplanung wird sie hingegen eingeordnet, wenn eine Tour sich während der

Durchführung ändert. Eine weitere Abgrenzung ist die deterministische Tourenplanung. Ein Touren-

planungsproblem ist deterministisch, wenn alle Eingangsdaten mit Sicherheit zum Planungszeitpunkt

bekannt sind. Das heißt, dass im Vorfeld z. B. auch die tatsächliche Nachfragemenge des Kunden be-

kannt sein muss. Die Gemeinsamkeit der Definitionen für statische und dynamische Tourenplanungs-

probleme ist, dass sie auf Planungszeitpunkten beruhen. Im statischen Fall wird die Planung einmal

vor der Durchführung der Tour gemacht, während sie im dynamischen Fall mehrmals parallel zur

Tourendurchführung gemacht werden muss (siehe Richter (2005:65)).

Im Gegensatz dazu beziehen Ghiani et al. (2003:3) ihre Definitionen eher auf die Eingangsinforma-

tionen. Sie gehen sogar noch weiter und bilden Kombinationen aus den vier zuvor dargestellten Defi-

nitionen. Somit kann ein dynamisches Problem auch deterministisch oder stochastisch sein. Im deter-

ministischen Fall liegen alle Informationen mit Sicherheit vor Planungsbeginn vor. Im stochastischen

Fall treten die Informationen zufällig auf und sind mit Unsicherheit belastet, wie es zum Beispiel Po-

well, Jaillet und Odoni (1995) in ihrer Arbeit beschreiben.

Richter (2005:68) fasst die unterschiedlichen Definitionsansätze in Abbildung 2 zusammen. Die

drei Kombinationsmöglichkeiten deterministisch statisch, stochastisch statisch und deterministisch

dynamisch sind hier unter der statischen Tourenplanung zusammengefasst. Nur unter die Kombinati-

onsmöglichkeit stochastisch dynamisch ist die dynamische Tourenplanung eingeordnet. In dieser Ar-

beit wird weitestgehend dieser Bereich thematisiert.

Abbildung 2: Vergleich verschiedener Definitionsansätze (Richter, 2005:68)

Der Begriff ,,Dynamik" kann auch auf verschiedene Ebenen bezogen werden. So unterscheiden

Powell, Jaillet und Odoni (1995:142f.)

zwischen Dynamik des Problems, Dynamik des angewendeten

Modells oder Dynamik bezüglich der praktischen Anwendung.

Ein Problem ist dynamisch, wenn ein oder mehrere seiner Parameter eine Zeitfunktion darstellen.

Das heißt, dass die relevanten Informationen sich im Zeitablauf ändern. Das schließt Probleme mit

sich ständig ändernden dynamischen Informationen, sowie im Voraus bekannte mit ein.

Ein Modell ist dynamisch, wenn es die Wechselwirkungen der Handlungen im Zeitablauf mit ein-

bezieht. Also Faktoren ändern sich im Zeitablauf und die Auswirkungen werden mit berücksichtigt.

Zwischen dynamisch deterministischen und stochastischen Modellen soll unterschieden werden. Hier

kann ein dynamisches Problem in einem Modell mathematisch beschrieben werden.

Während eine Anwendung dynamisch ist, wenn das zugrunde liegende Modell bei neu generierten

Informationen, die das Problem ändern, wiederholt neu gelöst werden muss. Deshalb werden hohe

Rechnerleistungen benötigt.

Wenn hier Informationen gemeint sind, weisen sie in der dynamischen Tourenplanung gewisse Att-

ribute auf, denen Psaraftis (1995:153ff.) eine entscheidende Rolle zuspricht. Er nimmt eine Klassifika-

tion in die Bereiche der Entwicklung, der Qualität, der Verfügbarkeit und des Verarbeitungsprozesses

von eingehenden Informationen vor:

Die Entwicklung von Informationen haben einen entscheidenden Einfluss darauf, ob es sich um

ein statisches oder dynamisches Tourenplanungsproblem handelt. Wie oben bereits bei der Definition

beschrieben, sind statische Daten vor dem Tourenplanungsprozess vollständig bekannt und weisen

keine Entwicklung auf, weil sie sich während der gesamten Tourausführung nicht ändern. Im Gegen-

satz dazu weisen dynamische Daten die Eigenschaft auf, dass eine Entwicklung statt findet, denn es

kommen neue Informationen hinzu und sie ändern sich im Zeitablauf.

Die Qualität von Informationen kann auch differenziert werden. So können einige oder alle In-

formationen über den gesamten Tourenplanungsprozess mit Sicherheit zur Verfügung stehen, während

andere Informationen nur mit Unsicherheit prognostiziert oder anhand von Wahrscheinlichkeiten be-

schrieben werden können. Beispiele für sichere Informationen sind die Anzahl der Fahrzeuge, die

Entfernung zwischen den Kunden oder die zur Verfügung stehenden Fahrzeugkapazitäten. Informati-

onen wie Kundenaufträge oder Fahrzeiten unter Unsicherheit werden in Kapitel 3.1 näher betrachtet.

Die Qualität der Informationen gestaltet sich in dynamischen Tourenplanungsproblemen umso besser,

Details

Seiten
Erscheinungsform: Originalausgabe
Erscheinungsjahr: 2009
ISBN (eBook): 9783836641289
DOI: 10.3239/9783836641289
Dateigröße: 1 MB
Sprache: Deutsch
Institution / Hochschule: Universität Bremen – Wirtschaftswissenschaften
Erscheinungsdatum: 2010 (Januar)
Note: 2,1
Schlagworte: dvrp real-time warteschlangentheorie dynamik zeit
Produktsicherheit: Diplom.de

Autor

Björn Aufderheide (Autor:in)