Vergleich unterschiedlicher heuristischer Verfahren für das "Vehicle routing problem with time windows"

Inhaltsverzeichnis

1 Einleitung
1.1 Zielsetzungen der Arbeit
1.2 Vorgehensweise und Aufbau der Arbeit

2 Grundlagen und Abgrenzungen
2.1 Das allgemeine Tourenplanungsproblem
2.2 Tourenplanung unter Berücksichtigung zeitkritischer Restriktionen
2.3 Komplexitätsanalyse

3 Metaheuristiken für Optimierungsprobleme
3.1 Tabu-Search Verfahren
3.2 Simulated Annealing Verfahren
3.3 Evolutionsstrategien
3.4 Parallele Lösungsansätze

4 Vergleich unterschiedlicher Verfahren für die Lösung von großen Tourenplanungsproblemen mit Zeitrestriktionen
4.1 Probleminstanzen in der Literatur
4.2 Vergleichskriterien für die Verfahrensevaluation
4.3 Verfahren zur Lösung großer Tourenplanungsprobleme
4.3.1 Die kooperativ-parallele Metaheuristik von Le Bouthillier und Crainic
4.3.2 Die adaptiven Suchheuristiken von Pisinger und Ropke
4.3.3 Aktive gesteuerte Evolutionsstrategien von Mester und Bräysy
4.3.4 Die Multi-Start lokale Suche (MSLS) Heuristik von Bräysy et al
4.3.5 Ebenen-Schnittverfahren von Kallehauge et al. sowie Cook und Rich
4.4 Gegenüberstellung der unterschiedlichen Verfahren

5 Zusammenfassung

Literaturverzeichnis

Danksagung

Abbildungsverzeichnis

Abb. 4.1: Kollaborationsdiagramm der Metaheuristiken

Abb. 4.2: Vergleich der Nachbarschaftsstrukturen von VNS und ALNS

Abb. 4.3: Kosten der Lösung als Funktion der Anzahl von Iterationen

Abb. 4.4: Streckenersparnis (Saving) durch Verschmelzen von mehreren Touren

Abb. 4.5: Lösung für ein 1000-Kunden Problem (C110_1)

Tabellenverzeichnis

Tab. 3.1: Taxonomie von Flynn (1966)

Tab. 4.1: Resultate für Homberger Probleme mit 200 Kunden

Tab. 4.2: Resultate für Homberger Probleme mit 400 Kunden

Tab. 4.3: Resultate für Homberger Probleme mit 1000 Kunden

Tab. 4.4: Vergleich der verschiedenen Verfahren

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 NP-harten (engl.: n on-deterministic p olynomial 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.

Das VRP kann entweder als Auslieferungs- oder als Sammelproblem (oder als eine Mischform) aufgefasst werden, wobei die den jeweiligen Kunden zu liefernde (bzw. abzuholende) Menge vorgegeben ist. Nachfolgend wird ohne Beschränkung der Allgemeinheit von einem Auslieferungsproblem ausgegangen, bei dem n Kunden von einem Depot ausgehend mit Gütern beliefert werden. Zur Belieferung werden ein oder mehrere gleichartige Fahrzeuge mit jeweils gleicher Lade- und Fahrzeugkapazität Q eingesetzt. Weiterhin werden folgende Annahmen unterstellt (vgl. Homberger 2000):

- Es wird eine einperiodige Planung angenommen.
- Jeder Kunde muss auf genau einer Tour beliefert werden (Unteilbarkeitskriterium).
- Es steht eine beliebig große Menge an gleichartigen Fahrzeugen zur Verfügung.
- Ein Mehrfacheinsatz der Fahrzeuge wird ausgeschlossen.
- Die Geschwindigkeit der Fahrzeuge ist auf allen Strecken gleich.
- Die Güter können in beliebiger Zusammenstellung transportiert werden.

Um einen höheren Realitätsgrad zu erreichen, werden in einigen Modellen in der Literatur auch zusätzliche Bedingungen eingeführt, die z. B. gesetzliche Bestimmungen zur maximalen Arbeitszeit (vgl. Xu et al. 2003) berücksichtigen.

2.2 Tourenplanung unter Berücksichtigung zeitkritischer Restriktionen

Das VRPTW kann als Erweiterung des allgemeinen Tourenplanungsproblems um zusätzliche zeitliche Restriktionen angesehen werden. Als weitere freie Variablen treten beim VRPTW die Dauer der Bedienung des Kunden (Servicezeit) sk und ein Zeitfenster [ ak, bk ], in dem die Belieferung stattzufinden hat, auf. Dem VRPTW wird meist eine hierarchische Zielsetzung zugrunde gelegt (vgl. Solomon 1987). Dabei wird als primäres Ziel die Minimierung der benötigten Fahrzeugzahl und erst als sekundäres Kriterium die Minimierung der Gesamtentfernung angestrebt. Diese Priorisierung lässt sich auch ökonomisch begründen. So sind die Kosten, die mit einer zusätzlichen Anmietung von LKW Kapazitäten in Verbindung stehen, normalerweise wesentlich höher als Kosten, die durch eine längere zurückgelegte Gesamtdistanz entstehen.

Das Ziel der Tourenplanung besteht darin, einen optimalen Tourenplan zu berechnen, mit dem jeder Kunde beliefert wird und der die Einhaltung der nachfolgenden Restriktionen erfüllt (vgl. Homberger 2000):

- Die Ladekapazität des Fahrzeugs darf nicht überschritten werden.
- Die kundenabhängigen Servicezeiten müssen berücksichtigt werden.
- Die Belieferung der Kunden außerhalb der Zeitfenster ist nicht zulässig.
- Die Depotöffnungszeiten sind zu beachten.

Des Weiteren wird angenommen, dass es für das zu lösende Problem mindestens eine zulässige Lösung gibt.

2.3 Komplexitätsanalyse

Das VRPTW gehört zur Klasse der NP-harten Probleme. NP-hart ist ein Begriff aus der Komplexitätstheorie. Er dient der Klassifizierung von Problemen, die sich nur unter besonderem Aufwand berechnen lassen. Formal lässt sich die Klasse NP wie folgt beschreiben:

Ein Problem L 1 lässt sich auf ein Problem L 2 polynominell reduzieren, genau dann, wenn es einen Weg gibt, L 1 zu lösen mit Hilfe eines deterministischen Algorithmus mit polynomineller Laufzeit, der sich auf einen deterministischen Algorithmus stützt, welcher L 2 löst. Ein Problem L 1 ist NP-hart genau dann, wenn alle Probleme aus Lx aus NP auf L 1 polynominell reduzierbar sind.

Es existiert daher vermutlich kein Verfahren, das das Problem mit polynominellem Rechenaufwand exakt lösen kann. Der Rechenaufwand für die Berechnung einer optimalen Lösung steigt exponentiell mit der Kundenanzahl. Aufgrund der Zeitfensterrestriktionen stellt die Berechnung einer beliebigen zulässigen Lösung für eine vorgegebene Fahrzeuganzahl bereits ein NP-vollständiges Problem dar (vgl. Savelsbergh 1985). Deshalb erweist sich das Standardtourenplanungsproblem mit Zeitfensterrestriktionen als fundamental schwieriger, als dasjenige ohne Zeitfensterrestriktionen.

Da heuristische Methoden häufig nahezu optimale Lösungen in einer vergleichsweise geringen Rechenzeit liefern, wurde die Entwicklung von Heuristiken und Metaheuristiken zur Lösung des VRPTW in der letzten Zeit am weitesten vorangetrieben (vgl. Mester und Bräysy 2005). Im folgenden Kapitel werden einige grundlegende und in vielen Verfahren angewandte Metaheuristiken vorgestellt.

3 Metaheuristiken für Optimierungsprobleme

Nach Schütz (1997) stellen Metaheuristiken allgemeine Verfahrensbeschreibungen dar, die durch den Einbau von problemspezifischem Wissen für ein konkretes Problem angepasst werden. In diesem Kontext besteht somit ein problemunabhängiges Rahmenverfahren, in das problemspezifische Heuristiken eingebettet werden. Nach Osman und Kelley (1997) unterscheidet man zwei verschiedene Typen von Metaheuristiken:

- Metaheuristiken zur Steuerung einer Konstruktionsheuristik und
- Metaheuristiken zur Steuerung einer Nachbarschaftssuche.

Dabei wird ersterer Typ hauptsächlich dazu eingesetzt, Anfangslösungen für eine anschließende intelligente Nachbarschaftssuche zu berechnen. Prinzipiell ist es auch denkbar, dass statt der Konstruktion einer Lösung diese auf bereits vorliegende Lösungen zurückgreift.

Metaheuristiken zur Steuerung einer Nachbarschaftssuche ermöglichen es, die Suche aus lokalen Optima herauszuführen und Zyklen zu vermeiden. Häufig wird die Nachbarschaftsstruktur während der Suche gewechselt, um die Suche in neue Gebiete des Lösungsraums zu lenken.

Die eigentliche Steuerung des Suchprozesses erfolgt durch einen Selektions-Mechanismus, mit dem aus den generierten Nachbarlösungen und gegebenenfalls der aktuellen Lösung eine Folgelösung ausgewählt wird (Homberger 2000). Sobald vorgegebene Terminationskriterien erfüllt sind, wird die Suche beendet. Als allgemeine Terminationskriterien können u. a. folgende angeführt werden:

- Eine maximale Anzahl von Iterationen ist ausgeführt worden.
- Eine maximale Anzahl von Iterationen ist ausgeführt worden, ohne eine Verbesserung des bislang besten berechneten Zielfunktionswertes.

Die Generierungs- und Selektions-Mechanismen werden häufig in zwei Klassen eingeteilt. Einerseits soll die Erkundung neuer Gebiete im Lösungsraum gefördert werden („Exploration“), andererseits soll die intensive Erkundung eines Gebiets durch Ausnutzung bereits gewonnener Informationen über das zu lösende Problem ermöglicht werden („Exploitation“).

Als erfolgreiche Vertreter des Metatyps 2 haben sich in jüngster Zeit vor allem das Tabu Search und das Simulated Annealing etabliert, die in den folgenden Absätzen kurz vorgestellt werden sollen. In einem weiteren Abschnitt wird eine Evolutionsstrategie eingeführt, die ebenfalls als Metaheuristik ihren Einsatz bei der Lösung kombinatorischer Optimierungs­probleme findet.

3.1 Tabu-Search Verfahren

Das Tabu-Search (TS) Verfahren wurde von Glover (1986) und von Hansen (1986) unabhängig voneinander entwickelt. Es stellt nach Homberger (2000) eine Strategie zur „aggressiven Exploration“ des Lösungsraums dar. In seiner Grundform untersucht TS bei jeder Iteration die vollständige Nachbarschaft der aktuellen Lösung. Zur Steuerung des Suchprozesses und zur Vermeidung von Zyklen verwendet TS ein Gedächtnis, das als „Tabuliste“ bezeichnet wird. Mit Hilfe dieser Liste wird die Nachbarschaft auf eine Menge („Pool“) eingeschränkt, die eine echte Teilmenge der Nachbarschaftsmenge ist. Die anderen Lösungen der Nachbarschaft werden tabu gesetzt. Hierdurch wird verhindert, dass es zu einem Zyklus kommen kann. In jeder Iteration wird die beste nicht tabuisierte Lösung ausgewählt. Für die Auswahl der besten Lösung stehen verschiedene Verfahren zur Verfügung. Zunächst ist die „Best-Akzeptanz-Strategie“ zu nennen. Hierbei wird die Nachbarlösung ausgewählt, welche die höchste Verbesserung zur aktuellen Lösung darstellt. Falls keine Verbesserung erzielt werden kann, wird im Allgemeinen die Lösung mit der geringsten Verschlechterung ausgewählt. Im Fall von sehr großen Nachbarschaften, die einen sehr großen Rechenaufwand für die Besten-Suche verursachen, werden folgende alternative Vorgehensweisen verwendet:

- Best-Akzeptanz-Strategie mit einer eingeschränkten Nachbarschaft und
- First-Akzeptanz-Strategie.

Im ersten Fall wird die Menge der in einer Iteration durchzuführenden Moves a priori eingeschränkt (Semet und Taillard 1993). Unter einem Move versteht man in diesem Falle einen Zug, der eine Lösung durch Modifikation in eine Nachbarlösung überführt. Aus der Menge der jeweils möglichen Moves werden in einer Iteration lediglich einige ausgewählt und auf die aktuelle Lösung angewendet. Die Auswahl erfolgt hierbei entweder zufällig oder unter Einbeziehung problemspezifischen Wissens. Unter letzterem versteht man Lösungen mit solchen Eigenschaften, die in guten Lösungen (vermutlich) nicht auftreten.

Bei der First-Akzeptanz-Strategie werden solange Nachbarlösungen in einer meist zufälligen Reihenfolge generiert, bis eine nicht tabuisierte Nachbarlösung gefunden ist, die gegenüber der aktuellen Lösung eine Verbesserung darstellt (oder die vollständige Nachbarschaft untersucht worden ist). Im Unterschied zur Best-Akzeptanz-Strategie werden nun nicht mehr intensiv Verbesserungen in der Nachbarschaft gesucht, sondern tendenziell eher neue Gebiete des Lösungsraumes aufgesucht.

In der Tabuliste werden normalerweise Eigenschaften oder Attribute bereits ausgeführter Moves gespeichert. Im Tabulisten-Management wird geregelt, wie lange und wann die Informationen in der Tabuliste vorgehalten werden. Es besteht auch die Möglichkeit, dass vollständige Lösungen in der Tabuliste abgelegt werden. In diesem Fall ist jede Nachbarlösung daraufhin zu prüfen, ob sie bereits in der Tabuliste enthalten ist. Auf diese Weise können zwar Zyklen auf jeden Fall ausgeschlossen werden, allerdings ist der Rechenaufwand auch sehr hoch und nicht praktikabel. Häufig werden in der Tabuliste Eigenschaften des ausgewählten Moves gespeichert, die jeweils in einer Iteration zu der ausgewählten Folgelösung geführt haben (vgl. Glover 1989). Die Vermeidung von Zyklen erfolgt nun dadurch, dass durchgeführte Moves über mehrere Iterationen hinweg nicht rückgängig gemacht werden dürfen. Die Eigenschaften eines Moves werden entweder als „from“-Attribut oder als „to“-Attribut gespeichert. Ein „from“-Attribut beinhaltet eine Ausprägung, die die aktuelle Lösung, nicht aber die Nachbarlösung besitzt. Ein „to“-Attribut dagegen beinhaltet eine Ausprägung, die die Nachbarlösung, nicht aber die aktuelle Lösung aufweist.

Beim Tabulisten Management unterscheidet man statische und dynamische Varianten (Glover 1990). Beim statischen Tabulisten Management wird die Tabuliste als eine first-in first-out (FIFO) Liste mit vorgegebener Listenlänge verwaltet. In ihr werden entweder die Eigenschaften der ausgewählten Folgelösung oder aber die den Move beschreibenden Eigenschaften eingetragen. Zyklen können also nur vermieden werden, solange sie nicht über die Tabulistenlänge hinausgehen.

[...]