FernUniversität in Hagen
Fachbereich Wirtschaftswissenschaft

Diplomarbeit
zur Erlangung des Grades
eines Diplom-Wirtschaftsingenieurs

Vergleich unterschiedlicher heuristischer Verfahren für das
Vehicle Routing Problem with Time Windows

Stephan Pachnicke

Inhaltsverzeichnis

1 Einleitung 1

1.1 Zielsetzungen der Arbeit 2
1.2 Vorgehensweise und Aufbau der Arbeit 2

2 Grundlagen und Abgrenzungen 3

2.1 Das allgemeine Tourenplanungsproblem 3
2.2 Tourenplanung unter Berücksichtigung zeitkritischer Restriktionen 4
2.3 Komplexitätsanalyse 5

3 Metaheuristiken für Optimierungsprobleme 6

3.1 Tabu-Search Verfahren 7
3.2 Simulated Annealing Verfahren 9
3.3 Evolutionsstrategien 11
3.4 Parallele Lösungsansätze 12

4 Vergleich unterschiedlicher Verfahren für die Lösung von großen Tourenplanungsproblemen mit Zeitrestriktionen 16

4.1 Probleminstanzen in der Literatur 16
4.2 Vergleichskriterien für die Verfahrensevaluation 17
4.3 Verfahren zur Lösung großer Tourenplanungsprobleme 18
4.3.1 Die kooperativ-parallele Metaheuristik von LE BOUTHILLIER und CRAINIC 18
4.3.2 Die adaptiven Suchheuristiken von PISINGER und ROPKE 21
4.3.3 Aktive gesteuerte Evolutionsstrategien von MESTER und BRÄYSY 26
4.3.4 Die Multi-Start lokale Suche (MSLS) Heuristik von BRÄYSY et al. 29
4.3.5 Ebenen-Schnittverfahren von KALLEHAUGE et al. sowie COOK und RICH 31
4.4 Gegenüberstellung der unterschiedlichen Verfahren 35

5 Zusammenfassung 41

Literaturverzeichnis 43
Danksagung 48

1 Einleitung

Das Transportwesen und die damit verbundene logistische Planung des Warenflusses sowie die Tourenplanung spielen eine wichtige Rolle im betriebswirtschaftlichen Umfeld. Unter Tourenplanung versteht man allgemein eine Klasse von Planungsproblemen, die verschiedene Ausprägungen bezüglich der Zielfunktion und den Nebenbedingungen aufweisen. Eine konkrete Problemstellung der Tourenplanung sieht etwa folgendermaßen aus: Von einem oder mehreren Lagern ausgehend, sind mit einem vorhandenen Fuhrpark, ein oder mehrere Kunden entsprechend den vorhandenen Aufträgen zu beliefern. Hierbei ist die Kapazität der Fahrzeuge beschränkt. Eine in der betrieblichen Praxis häufig auftretende weitere Restriktion ist die Vorgabe von Zeitfenstern. Unter Zeitfenstern versteht man Intervalle, die den frühesten und spätesten Beginn einer Auftragsdurchführung begrenzen. Ein typisches Beispiel für ein Tourenplanungsproblem mit Zeitfenstern ist die „just-in-time“ Belieferung durch Paketdienste. Im angelsächsischen Sprachbereich wird das Problem auch als „vehicle routing problem with time windows“ (VRPTW) bezeichnet. In der Regel liegt dem VRPTW eine hierarchische Zielsetzung zugrunde, die die benötigte Fahrzeugzahl in einem ersten Schritt und die Minimierung der Gesamtdistanz in einem zweiten Schritt berücksichtigt.

Das VRPTW ist ein kombinatorisches Optimierungsproblem, welches zur Klasse der NPharten (engl.: non-deterministic polynomial time) Probleme gezählt wird. Dies bedeutet, dass bislang kein Algorithmus bekannt ist, mit dem eine optimale Lösung in polynomialer Zeit gefunden werden kann. Stattdessen wächst der Lösungsaufwand mit der Problemgröße exponentiell. Deshalb bietet sich der Einsatz von heuristischen Verfahren an.

Hierzu zählen insbesondere Metaheuristiken, wie das Tabu Search Verfahren, Simulated Annealing oder Evolutionäre Algorithmen (z.B. genetische Algorithmen). Die ersten Metaheuristiken haben ihren Ursprung in den 70er Jahren. In letzter Zeit wurden besonders hybride und verteilt-parallele Ansätze untersucht. Unter hybriden Ansätzen versteht man eine Kombination von verschiedenen Metaheuristiken. Verteilt-parallele Ansätze versuchen das Problem nicht mehr sequentiell, sondern durch mehrere parallele Prozesse zu lösen.

In dieser Arbeit sollen speziell große Probleminstanzen mit mehreren hundert Kunden untersucht werden. Hierfür werden verschiedene Verfahren, die in der jüngsten Literatur veröffentlicht wurden, miteinander verglichen.

1.1 Zielsetzungen der Arbeit

Die erste Zielsetzung der Arbeit besteht darin, die verschiedenen Metaheuristiken für die Lösung eines Tourenplanungsproblems mit Zeitfenstern zu beschreiben. Insbesondere werden das Tabu Search- und das Simulated Annealing Verfahren erläutert. Außerdem wird eine Evolutionsstrategie aufgezeigt und eine mögliche Parallelisierung angesprochen.

In einem weiteren Teil der Arbeit wird das Ergebnis einer umfassenden Literaturrecherche zu Lösungsansätzen für das VRPTW mit großen Probleminstanzen präsentiert. Hierfür werden unterschiedliche Herangehensweisen erläutert, die in der jüngsten Literatur vorgestellt worden sind. Die verschiedenen Verfahren werden anhand von einschlägigen Benchmarkproblemen bewertet.

Abschließend werden die vorgestellten Verfahren miteinander verglichen und bewertet.

1.2 Vorgehensweise und Aufbau der Arbeit

Nach einer Einleitung im ersten Kapitel werden im zweiten Kapitel die Grundlagen des Tourenplanungsproblems mit Zeitfenstern erläutert. Im dritten Kapitel werden dann verschiedene Metaheuristiken für Optimierungsprobleme vorgestellt. Besonders werden die Verfahren Tabu-Search und Simulated Annealing sowie Evolutionsstrategien präsentiert. Außerdem werden die Unterschiede zwischen sequentiellen und verteilt-parallelen Verfahren diskutiert.

Im vierten Kapitel werden die Ergebnisse der Literaturrecherche zu Lösungsverfahren für das VRPTW bei großen Probleminstanzen gezeigt. Die unterschiedlichen Verfahren werden anhand der angeführten Benchmarkprobleme mit einander verglichen.

Im fünften Kapitel folgen eine Zusammenfassung der vorliegenden Arbeit und ihrer wesentlichen Ergebnisse sowie ein Ausblick auf weiterführende Forschungsarbeiten.

2 Grundlagen und Abgrenzungen

Gegenstand dieses Kapitels ist zunächst die Beschreibung des allgemeinen Tourenplanungsproblems. Im zweiten Abschnitt wird dieses um Zeitfensterrestriktionen (VRPTW, engl.: vehicle routing problem with time windows) erweitert. Es werden sowohl die hierarchische Zielsetzung als auch die Zeitfensterrestriktionen erläutert. Im letzten Abschnitt wird auf die mathematische Komplexität des VRPTW und die Konsequenzen für algorithmische Lösungsverfahren eingegangen.

2.1 Das allgemeine Tourenplanungsproblem

Die Tourenplanung beschäftigt sich mit der Ermittlung optimaler Fahrzeugtouren für das Ausliefern oder Einsammeln von Gütern an bestimmten Orten (vgl. HOMBERGER 2000). Der Ort, an dem die Auslieferungsfahrten beginnen, wird hierbei als „Depot“ bezeichnet. Unter einer „Tour“ wird die geordnete Menge von Orten verstanden, die auf einer gemeinsamen an einem Depot beginnenden und endenden Fahrt beliefert werden. Die Menge aller Touren wird
als Tourenplan bezeichnet und stellt das Ergebnis der Tourenplanung (engl.: vehicle routing problem, VRP) dar.

[...]