Universität Hohenheim, Institut für Betriebswirtschaftslehre
Fakultät V – Wirtschafts- und Sozialwissenschaften
Seminar zur Produktionsplanung und -steuerung
Wintersemester 2006/ 2007, 25.11.2006

Besonderheiten stochastischer Tourenplanungsprobleme

von: Patrick Schellhorn

Inhaltsverzeichnis

1 Einleitung  1

1.1 Gegenstand und Aufbau dieser Arbeit  1

2 Überblick über deterministische Tourenplanungsprobleme 2

2.1 Ein bestimmtes Standardproblem der Tourenplanung  2
2.2 Exakte Verfahren und Heuristiken  3

3 Stochastische Tourenplanungsprobleme und ihre  6

3.1 Besonderheiten  6
3.2 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage 7

3.2.1 Besonderheiten von Tourenplanungsproblemen mit stochastischer Nachfrage am Beispiel des Savingsverfahrens 10
3.2.2 Das Savingsverfahren von Clark und Wright 10
3.2.3 Der stochastische Clark und Wright Algorithmus 11

4 Fazit  14

Literaturverzeichnis 15

Anhang  16

 

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 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 Zuordnungsproblemen (Clustering) und Reihenfolgeproblemen (Routing Problem).² 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 Tourenplanungsproblem.

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.³

[...]

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

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

3 Vgl. Domschke, W. (1982), S. 132