Besonderheiten stochastischer Tourenplanungsprobleme

Inhaltsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

1 Einleitung
1.1 Gegenstand und Aufbau dieser Arbeit

2 Überblick über deterministische Tourenplanungsprobleme
2.1 Ein bestimmtes Standardproblem der Tourenplanung
2.2 Exakte Verfahren und Heuristiken

3 Stochastische Tourenplanungsprobleme und ihre
3.1 Besonderheiten
3.1 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage
3.1.1 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage am Beispiel des Savingsverfahrens
3.1.2 Das Savingsverfahren von Clark und Wright
3.1.3 Der stochastische Clark und Wright Algorithmus

4 Fazit

Literaturverzeichnis

Anhang

Tabellenverzeichnis

Tab. 1: 75 Kunden Tourenplanungsproblem mit stochastischer Nachfrage

Tab.2: Ergebnis des 75 Kunden Tourenplanungsproblems mit dem SC - W

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Bereits das Standardproblem der Tourenplanung mit deterministischen Daten ist mit mathematischen Modellen in einer für die Praxis relevanten Größenordnung nicht vollständig beherrschbar. Können zusätzlich nur stochastische Daten verwendet werden, was in der Praxis eine realistische Annahme ist, wird das Tourenplanungsproblem noch wesentlich komplexer.

Aus diesem Grund wurden stochastische Tourenplanungsprobleme (im Folgenden mit SVRP abgekürzt) in der Literatur bisher kaum behandelt, obwohl die stochastische Tourenplanung, für die Praxis eine größere Bedeutung als die deterministische Tourenplanung haben dürfte.^[1]

1.1 Gegenstand und Aufbau dieser Arbeit

Im Kern dieser Arbeit geht es darum, darzustellen, durch welche Eigenschaften sich SVRPs von deterministischen Tourenplanungsproblemen unterscheiden. Zu diesem Zweck wird in Kapitel 3 ein Überblick über die verschiedenen SVRPs gegeben. Um die Besonderheiten der SVRPs herausarbeiten zu können, muss aber zunächst das Grundproblem, das allen Tourenplanungsproblemen gemeinsam ist, erklärt werden. Dieses Grundproblem wird in Kapitel 2 erläutert. Anschließend wird ebenfalls in Kapitel 2 ein Überblick über deterministische Tourenplanungsprobleme gegeben. Ferner wird eine Klassifizierung der verschiedenen Lösungsansätze für Tourenplanungsprobleme in diesem Kapitel vorgestellt. Zum Schluss wird in Kapitel 4 auf ein Verfahren exemplarisch etwas detaillierter eingegangen. Aufgrund der erwähnten Komplexität des Themas kann in dieser Arbeit kein allumfassender Überblick über sämtliche Besonderheiten der SVRPs gegeben werden. Hingegen geht es darum, bestimmte Ausschnitte des Themas auf exemplarischer Ebene genauer zu analysieren.

2 Überblick über deterministische Tourenplanungsprobleme

Unter einem Tourenplanungsproblem (im Folgenden als VRP bezeichnet) versteht man ganz allgemein das Problem, dass in einem Fuhrpark verschiedenen Fahrzeugen Aufträge zuzuordnen sind, wobei für jedes Fahrzeug zugleich die Reihenfolge festgelegt werden muss, in der die Aufträge auszuführen sind.

In der angloamerikanischen Literatur sind diese Probleme unter dem Begriff „Vehicle Routing Problems“ bekannt. VRPs bestehen aus einer Kombination von Zuordnungs­problemen (Clustering) und Reihenfolgeproblemen (Routing Problem).^[2] Das Reihenfolgeproblem ist im Prinzip ein Rundreiseproblem. Dabei muss entweder die kürzeste Rundreise, die jeden Knoten genau einmal enthält (Traveling Salesman Problem), oder die kürzeste Rundreise, welche jede Kante genau einmal enthält (Briefträgerproblem), gefunden werden.

Das in Kapitel 2.1. erläuterte Standardproblem ist ein knotenorientiertes Tourenplanungs­problem.

2.1 Ein bestimmtes Standardproblem der Tourenplanung

Da es eine Vielzahl von verschiedenen Tourenplanungsproblemen gibt, wird an dieser Stelle ein konkretes Tourenplanungsproblem herausgegriffen und exemplarisch für alle anderen Fälle näher erläutert. Von diesem Standardproblem wird im weiteren Verlauf dieser Arbeit stets ausgegangen.

Dazu muss zunächst der Begriff der „Tour“ und der Begriff der „Route“ definiert werden. Unter einer Tour versteht man die Menge aller Kunden, die von einem Fahrzeug auf einer Fahrt, die im Depot beginnt und dort auch wieder endet, beliefert werden. Unter einer Route versteht man die Reihenfolge, in der die Kunden einer Tour angefahren werden.^[3]

Für das Standardproblem wird angenommen, dass es nur ein Depot aber n Kunden gibt. Die Standorte der Kunden, wie auch der Standort des Depots, sind bekannt.

Die kürzesten Wege zwischen den Kunden untereinander und zwischen dem Depot und den Kunden sind ebenfalls bekannt und symmetrisch. Nun sollen innerhalb von einer Periode n Kunden mit beliebig vielen Fahrzeugen beliefert werden. Dabei muss beachtet werden, dass ein Fahrzeug nur eine Tour übernehmen kann. Der Fuhrpark besteht in diesem VRP aus einer homogenen Fahrzeugflotte. Jede Tour beginnt und endet am Depot. Teillieferungen sind nicht möglich und die Kundenbedarfe sind deterministisch.^[4] Die Zielsetzung des Planers ist es typischerweise, die Touren und Routen so zu planen, dass die gesamten Fahrtkosten, die gesamte Fahrzeit oder die insgesamt zurückgelegte Entfernung minimiert werden.^[5] In dieser Arbeit werden die Fahrtkosten mit der zurückgelegten Entfernung gleichgesetzt, d.h. es wird stets angenommen, dass die Fahrtkosten linear von der zurückgelegten Entfernung abhängen.

Weitere Varianten von VRPs, welche in dieser Arbeit nicht weiter vertieft werden, wären zum Beispiel Mehrperiodensysteme, Mehrdepotprobleme oder Sammelprobleme.^[6]

Außerdem ist es denkbar, dass zusätzlich zur Kapazitätsrestriktion eine Zeit-Fenster-Restriktion vorliegt. Dabei muss jeder Kunde innerhalb eines bestimmten Zeitintervalles

[ai, bi] besucht werden. Denkbar ist auch eine Entfernungsrestriktion. In diesem Fall darf die gesamte Länge einer Route, eine bestimmte vorgegebene Konstante nicht überschreiten.^[7]

2.2 Exakte Verfahren und Heuristiken

Generell können Verfahren zur Lösung von Tourenplanungsproblemen in exakte und heuristische Verfahren unterteilt werden.^[8]

Exakte Verfahren haben in der Praxis bei der Lösung von Tourenplanungsproblemen bisher keine große Bedeutung erlangt.^[9] Dies liegt v.a. daran, dass exakte Verfahren so komplex sind, dass sie nur mit exponentiellem Rechenaufwand gelöst werden können. So können exakte Verfahren, die zum Beispiel zur Lösung des Traveling Salesman Problems verwendet werden, aufgrund sehr langer Rechenzeiten nur für kleine n verwendet werden.^[10] Weil das Traveling Salesman Problem als Reihefolgenproblem nur ein Teilproblem der VRPs ist, kann ein VRP nicht einfacher lösbar sein als ein Traveling Salesman Problem. Daraus folgt, dass auch ein VRP nicht sinnvoll für große n mit exakten Verfahren gelöst werden kann. Exakte Verfahren sind aber dennoch nützlich, um an kleineren Kundenzahlen die Lösungsqualität von Heuristiken überprüfen zu können.^[11]

[...]

^[1] Vgl. Vaterrodt, H.J. (1975), S. 15

^[2] Vgl. Matthäus, F. (1978), S. 11 ff

^[3] Vgl. Domschke, W. (1982), S. 132

^[4] Beim Tourenplanungsproblem mit stochastischer Nachfrage (siehe Kapitel 3.1.) , sind Teillieferungen möglich und die Nachfrage ist stochastisch

^[5] Vgl. Domschke, W. (1982), S. 132

^[6] Vgl. Domschke, W. (1982), S. 131

^[7] Vgl.. Gendreau et. al. (1996), S. 3

^[8] Vgl. Scheubrein, R., Geiger, M. (2000), S. 6

^[9] Vgl. Domschke, W. (1982), S. 136

^[10] Vgl. Fleischmann, B. (1998), S. 293

^[11] Vgl. Fleischmann, B. (1998), S. 293