Vehicle Routing Problem with Time Windows. Route Construction and Local Search Algorithms

Inhaltsverzeichnis

Symbolverzeichnis

1. Kurzzusammenfassung

2. Einleitung
2.1 Heutige Relevanz der Thematik
2.2 Anwendungsbereiche
2.3 Literaturübersicht
2.4 Aufbau der Seminararbeit

3. Problemformulierung
3.1 Variablen und Strukturierung von Raum und Zeit
3.2 Mathematische Modellierung

4. Methoden zum Lösen des Problems
4.1 Allgemeine Verfahrensweise
4.2 Tourenplanung mit Zeitfenstern
4.2.1 Der Sweep-Algorithmus
4.2.2 Der Savings-Algorithmus
4.3 Optimierung mit lokalen Suchverfahren
4.3.1 Das Suchverfahren 2-opt
4.3.2 Das Suchverfahren 3-opt

5. Schlussfolgerung

Literaturverzeichnis

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1.Kurzzusammenfassung

Diese Seminararbeit beschäftigt sich mit der Fahrzeugroutenplanung mit Zeitfenstern, welche ein kombinatorisches Optimierungsproblem darstellt. Wissenschaftler beschäfti- gen sich bereits seit den 70er Jahren mit dieser Thematik. Die Relevanz war allerdings noch nie zuvor so hoch wie jetzt, denn durch die immer weitere Verbreitung der Nut- zung von E-Commerce sind Logistikunternehmen gefragt wie nie zuvor. Diese Arbeit beschäftigt sich zum einen mit der Definition von Tourenplanungen mit Zeitfenstern und zum anderen mit Lösungsansätzen für diese Problematik.

2. Einleitung

2.1 Heutige Relevanz der Thematik

11.30 Uhr in Berlin. Es schellt an der Tür der jungen Frau Karr. Zu ihrem Glück ist es der zuverlässige Paketzusteller von DHL, der ihr nun das sehnlichst erwartete Paket liefert. Frau Karr wurde zu einer Veranstaltung eingeladen, für die ihr bisher noch das passende Outfit fehlte. Sie entschloss sich gestern zu einer Bestellung im Online-Shop um sich jeglichen Stress zu ersparen. Damit das Paket auch rechtzeitig ankommt, wählte sie die Versandart Morning-Express. Dies garantierte ihre eine Zustellung bis 12 Uhr am Werk- tag nach Versand. So konnte sie sich sicher sein, das Paket auf jeden Fall persönlich ent- gegen nehmen zu können.

In der heutigen Gesellschaft sind solche Situationen, wie die oben geschilderte, keine Seltenheit mehr. Ob es Kleidung, Kosmetika, Arzneimittel oder sogar frische Lebensmit- tel sind - Alles kann über Online-Versandhändler bestellt werden. So verkauft das riesige E-Commerce-Unternehmen Amazon beispielsweise in 60 Sekunden 25.000 verschiedene Artikel (Qmee.com, 2014). Um die Bedürfnisse der Kunden zu befriedigen, bedarf es allerdings mehr als ein breitgefächertes und tiefes Sortiment. Die Kunden wollen mög- lichst schnelle Lieferungen, die pünktlich zu Hause ankommen. Hier werden Logistik- Unternehmen auf die Probe gestellt. Dass auf diese Unternehmen ganz und gar nicht mehr zu verzichten ist, zeigt die positive Umsatzentwicklung der Deutschen Logistikbranche in den letzten Jahren - im Jahr 2000 wurde ein Umsatz von 154 Milliarden € verzeichnet, welcher bis 2010 auf 210 Milliarden € anstieg. Dies ist ein Zuwachs von mehr als einem Drittel in 10 Jahren. Bis zum Jahr 2013 stieg der Jahresumsatz dann rapide um weitere 9,5% auf 230 Milliarden € an (statista.com, 2014). Damit stellt die Logistikbranche den drittgrößten Wirtschaftsbereich Deutschlands dar (tag-der-logistik.de, 2015). Trotz des enormen Wachstums stehen die Unternehmen unter dem Druck, sich den Erwartungen und Zielsetzungen ihrer Umwelt anpassen zu müssen. Kundenunzufriedenheit durch un- pünktliche Lieferungen einzufahren, kann sich heute kein Unternehmen mehr leisten, denn die global vernetzte Welt sowie die freie Marktwirtschaft bieten den Konsumenten eine große Auswahl zum Ausweichen auf andere Dienstleister. Aufgrund dessen sind op- timal geplante Abläufe eine Grundvoraussetzung für das Bestehen in der heutigen Wirt- schaft - wie Logistikunternehmen sich hier durchsetzen, soll diese Arbeit genauer erläu- tern.

2.2 Anwendungsbereiche

Im Folgenden werden die Anwendungsbereiche des Vehicle Routing Problems with Time Windows beispielhaft erklärt. Dies soll zu einem besseren Verständnis der Thematik füh- ren.

Das Vehicle Routing Problem with Time Windows betrifft alle Firmen, die es zur Auf- gabe haben, ihre Kunden mit Waren zu beliefern oder diese beim Kunden abzuholen. Hierbei ist der Fokus darauf gerichtet, die Kunden in Form von Rundreisen vom Depot aus so anzufahren, dass die Gesamtlänge/Gesamtzeit des Tourenplans minimal ist, dass insgesamt eine minimale Anzahl an Touren gefahren wird und dass zudem eine gleich- mäßige Auslastung der Fahrzeuge vorliegt (Vahrenkamp/Mattfeld 2007: 276). Bei dieser Planung müssen oftmals Restriktionen, wie zum Beispiel die der Kapazität beachtet wer- den. Der entscheidende Unterschied der Tourenplanung mit Zeitfenster zum klassischen Routing Problem ist, dass die Belieferung der Kunden in einem bestimmten Zeitintervall stattfinden muss. Für das Vorliegen solcher Kundenzeitfenster kann es sehr verschiedene Gründe geben - Bedingungen, wie die persönliche Entgegennahme der Lieferung sowie zeitlich befristete Halteverbote oder Durchfahrverbote in Einkaufszonen zu bestimmten Uhrzeiten (Gietz 1994: 14). Ein praxisnahes Beispiel ist die Belieferung von Automobilherstellern. Heutzutage wird größtenteils Just-in-time produziert um Kosten für die Lagerung von Bauteilen zu sparen. Um trotzdem nicht in Verzug mit der Fertigstellung eines Fahrzeugs zu geraten, müssen Einzelteile in einem vorgesehenen Zeitfenster am Montageort eintreffen, umso eine reibungslose Produktion gewährleisten zu können. Hier wird der Stellenwert der logistischen Planung sehr deutlich.

2.3 Literaturübersicht

Lösungen für Tourenplanungsprobleme mit Zeitfenstern können auf zwei verschiedene Wege gefunden werden. Zum einen gibt es heuristische Verfahren, die gern in der Praxis angewendet werden, da sie laut Gietz (1994) gute bis befriedigende Lösungen erzeugen, einfach zu programmieren sind, wenig Speicherplatz erfordern, geringe Rechenzeiten be- nötigen und ein hohes Maß an Flexibilität aufweisen. Dem stehen die exakten Optimie- rungsalgorithmen gegenüber, die zwar bis zu einer gewissen Anzahl an Kunden eine op- timale Lösung produzieren können, aber dafür sehr lange Rechenzeiten aufweisen. Die unten aufgeführte Tabelle gibt einen Überblick über Veröffentlichungen zu Tourenpla- nungsproblemen mit Zeitfenstern.

Abbildung in dieser Leseprobe nicht enthalten

(Tabelle 1, vgl. Vahrenkamp/Mattfeld, 2007)

2.4 Aufbau der Seminararbeit

Die vorliegende Arbeit ist folgendermaßen gegliedert:

In Kapitel 3 wird zunächst eine detaillierte Formulierung sowie Modellierung des vorlie- genden Problems vorgenommen. Hierbei werden Variablen definiert sowie eine zeitliche und räumliche Struktur geschaffen. Diese wird anschließend mathematisch dargestellt. Das Kapitel 4 beschäftigt sich im ersten Teil ganz allgemein mit verschiedenen Methoden zum Auffinden von Lösungen des Tourenproblems. Im Anschluss daran werden zwei gängige Eröffnungsheuristiken vorgestellt, die mithilfe vereinfachter Beispiele verständ- licher gemacht werden sollen. Daran knüpft die Präsentation zweier Verbesserungsver- fahren, die hier stellvertretend für die Gruppe der lokalen Such-Algorithmen vorgestellt werden. Zum Schluss erfolgt eine persönliche Bewertung über das Tourenplanungsprob- lem mit Zeitfenstern als Forschungsgebiet.

3. Problemformulierung

3.1 Variablen und Strukturierung von Raum und Zeit

In diesem Abschnitt soll klar definiert werden unter welchen Bedingungen die Prob- lemlösung der Tourenplanung mit Zeitfenstern vorgenommen wird. Außerdem werden im weiteren Verlauf der Seminararbeit Definitionen vom Leser vorausgesetzt, die hier erklärt werden.

Wie Gietz (1994) in seinem Buch erwähnt, basiert jede Tourenplanung auf einem Graph V = (V,E), der die räumliche Struktur präsentiert. Dabei stellt V die Knotenmenge dar, welche die Kunden und das Depot repräsentieren. Die zu versorgenden Kundenorte werden mit 1, … ,n nummeriert und das Depot erhält die Nummer 0. E definiert die Kan- tenmenge, welche die zulässigen Verbindungen von Kunde i zu Kunde j oder zum De- pot 0 anzeigt. Die Bewertung d ij einer Kante (i,j) bildet die Entfernung von Kunde i zu Kunde j ab. Um den Blick auf die wesentliche Problematik zu lenken, werden in dieser Arbeit größten Teils die Bedingungen des Standartproblems der Tourenplanung ange- wendet. Es wird also fortan davon ausgegangen, dass Start- sowie Endpunkt einer Tour identisch sind - man spricht von einer geschlossenen Tour. Im Gegensatz dazu stehen offene Touren. Hier kehren die Fahrzeuge nicht zum selben Depot zurück. Neben den bereits oben definierten knotenorientierten Tourenproblemen, gibt es ebenfalls kanten- orientierte Probleme, bei denen das Fahrzeug zur Ausführung des Auftrags entlang einer Kante fahren muss (z.B. bei der Müllabfuhr) (Vahrenkamp/Mattfeld 2007:275). Des Weiteren werden die Entfernungen zwischen den einzelnen Kunden und zwischen dem Depot als bekannt und symmetrisch (richtungsunabhängig) angenommen. Einbahnstra- ßen oder notwendige Umwege durch Straßensperrungen machen die Anwendung von diesem Fall in der Realität unmöglich. Des Weiteren erfolgt in dieser Arbeit die Angabe der Distanzen nur in Form von euklidischen¹ Daten. Es wird außerdem die Annahme getroffen, dass alle Auslieferungsfahrzeuge, dessen Anzahl mit m angegeben wird, gleichartig sind und eine einheitliche Ladekapazität Q aufweisen. Auch die Nachfrage- menge q aller Kunden wird als identisch festgesetzt. Wie Vahrenkamp und Mattfeld (2007) anführen, muss zusätzlich zur räumlichen Struktur und den Variablen des Stan- dardproblems eine zeitliche Struktur modelliert werden, die die Fahrt- und Ankunftszei- ten eines LKWs in einer Tour abbildet. Diese Struktur besteht aus der Abfahrtszeit t 0 des Lieferfahrzeugs am Depot, der Fahrzeit t ij auf den Kanten (i,j), einem Zeitfenster [ a i ,b i ] bei einem Kunden i, der Ankunftszeit t i des Fahrzeugs beim Kunden i und der Service- zeit z i beim Kunden i. Man differenziert weiche von harten Zeitfenstern. Wenn ein har- tes Zeitfenster vorliegt, muss der Service innerhalb des vorgegebenen Zeitintervalls [ a i ,b i ] stattfinden. Es ist natürlich möglich, dass das Fahrzeug vor Servicebeginn a i des Zeitfensters beim Knoten i eintrifft, allerdings entsteht dann eine Wartezeit w i, die sich durch die Subtraktion a i - t i berechnet. Das Komplement dazu sind weiche Zeitfenster. Hier ist ein Service im Zeitfenster des Kunden i wünschenswert, aber nicht unbedingt notwendig. Wenn der Service außerhalb des Zeitfensters stattfindet, fallen zusätzliche Strafkosten an, die mit zunehmenden Abstand zum Zeitfenster ansteigen können.

[...]

¹ Dies trägt die Bedeutung, dass sich die Punkte eines Knotens in einer 2-dimensionalen Ebene befinden, wie in einem (X,Y)-Koordinatensystem. Die Berechnung der Distanz zweier Knoten erfolgt durch