In den letzten Jahrzehnten rückte ein Bereich der kombinatorischen Optimierungsprobleme immer mehr in den Brennpunkt der Forschung:
die Klasse der Tourenplanungsprobleme. Immer mehr Güter müssen in immer kürzerer Zeit von einem Ort zum anderen transportiert werden. Bei der Tourenplanung werden daher Fragestellungen diskutiert, wie eine Zusammenstellung von Auslieferungs- und Sammelaufträgen aussehen muss, um einen möglichst effizienten Ablauf zu gewährleisten. Die Schwierigkeit dieser Organisation liegt darin, die dem Problem zu Grunde liegenden Restriktionen einzuhalten. In der Praxis treten häufig Einschränkungen in Form einer begrenzten Ladekapazität der zur Verfügung stehenden Fahrzeuge oder zeitlicher Vorgaben der Kunden auf. Diese zeitlichen Vorgaben beinhalten den frühest beziehungsweise den spätest möglichen Belieferungszeitpunkt des Kunden. Beispielsweise kann ein Kunde aus der Just-in-Time Fertigung keine Lieferung vor diesem Zeitfenster annehmen, da ihm dafür schlicht Lagerkapazitäten fehlen. Eine Belieferung nach Ende des Zeitfensters ist ebenfalls nicht erlaubt, da es in diesem Szenario unter Umständen zu einem Stillstand der Produktion in Folge fehlender Ressourcen kommen kann.
In der Literatur wird dem Tourenplanungsproblem mit Zeitfensterrestriktionen meist eine hierarchische Zielstellung zu Grunde gelegt, einem primären sowie einem sekundären Ziel. Vorrangig ist hierbei die Minimierung der benötigten Fahrzeuge, nachrangig die Minimierung der zurückgelegten Gesamtfahrstrecke. Seit Mitte der Siebziger Jahre werden zur Lösung des VRPTW die dafür entwickelten Metaheuristiken eingesetzt. Sie basieren auf der Grundidee, physikalische oder biologische Prozesse nachzuahmen. Typische Vertreter solcher Verfahren sind Genetische und Evolutionäre Algorithmen, Simulated Annealing und Tabu-Search.
Eine Zielsetzung dieser Arbeit ist es, einen geeigneten Algorithmus zur Lösung des Tourenplanungsproblems mit Zeitfensterrestriktionen vorzustellen und diesen zu evaluieren. Ein zweites Ziel wird sein, ein weiteres, von der Literatur bisher unbeachtetes Kriterium zur Bewertung einer gefundenen Lösung umzusetzen: eine möglichst gleichmäßige Verteilung der Kunden auf die jeweiligen Touren. Damit soll erreicht werden, dass jeder Fahrer einer Tour zeitlich annähernd gleich lange unterwegs ist wie seine Kollegen auf den anderen Touren. Dabei wird dieses Kriterium nicht als Ziel sondern als Wunsch formuliert.
Inhaltsverzeichnis
- 1 Einleitung
- 1.1 Problemstellung
- 1.2 Zielstellung der Arbeit
- 1.3 Aufbau und Gliederung der Arbeit
- 2 Grundlagen und Abgrenzung
- 2.1 Tourenplanung im Allgemeinen
- 2.2 Tourenplanung mit zeitlicher Restriktion
- 2.2.1 Voraussetzungen und Realitätsbeschränkung
- 2.2.2 Mathematische Modellbildung
- 2.2.3 Komplexitätsuntersuchung des VRPTW
- 2.2.4 Typologie der Zeitfensterrestriktionen
- 2.3 Ansätze zur Lösung kombinatorischer Optimierungsprobleme
- 2.3.1 Problemspezifische Heuristiken
- 2.3.2 Metaheuristiken
- 3 Verfahren zur Lösung des VRPTW
- 3.1 Konstruktionsverfahren
- 3.2 Definition der Nachbarschaftsstrukturen
- 3.3 Bewertungsfunktion eines Tourenplans
- 3.4 Aufbau des Gesamtverfahrens
- 3.4.1 Minimierung der Fahrzeuganzahl
- 3.4.2 Minimierung der Gesamtfahrstrecke
- 4 Algorithmische Beschreibung des Verfahrens
- 4.1 Repräsentation elementarer Komponenten
- 4.1.1 Repräsentation der Kunden
- 4.1.2 Repräsentation der Tourenpläne
- 4.2 Elementare Zugriffe
- 4.3 Elementare Berechnungen
- 4.4 Elementare Zulässigkeitsbedingungen
- 4.5 Elementare Operationen
- 4.6 Konstruktion der Ausgangslösung
- 4.7 Algorithmische Umsetzung der Nachbarschaftsstrukturen
- 4.7.1 Operator Or-Opt
- 4.7.2 Operator 2-Opt*
- 4.7.3 Operator Single-Interchange
- 4.7.4 Operator Single-Insertion
- 4.7.5 Auswahl des Operators
- 4.8 Bewertung von Tourenplänen
- 4.9 Verbesserungsverfahren
- 4.9.1 Ejection-Chain Heuristik
- 4.9.2 Rekursion der Ejection-Chain
- 4.9.3 Lokale Suche zur Minimierung der Tourenanzahl
- 4.9.4 Lexikographischer Vergleichsoperator
- 4.9.5 Akzeptanz einer verschlechterten Lösung
- 4.9.6 Metaheuristik: Threshold Accepting
- 4.9.7 Verfahren zur Minimierung der Gesamtfahrstrecke
- 4.1 Repräsentation elementarer Komponenten
- 5 Evaluation des Gesamtverfahrens
- 5.1 Probleminstanzen von Solomon und Homberger
- 5.2 Parametrisierung des Gesamtverfahrens
- 5.3 Darstellung der berechneten Lösungen
- 5.4 Auswertung der berechneten Lösungen
Zielsetzung und Themenschwerpunkte
Diese Diplomarbeit befasst sich mit der Entwicklung und Evaluation einer zweistufigen Metaheuristik zur Lösung des Vehicle Routing Problem with Time Windows (VRPTW). Ziel ist die effiziente Bestimmung von Tourenplänen, die sowohl die Anzahl der benötigten Fahrzeuge als auch die Gesamtfahrstrecke minimieren. Die Arbeit untersucht verschiedene Algorithmen und bewertet deren Performance anhand von bekannten Benchmark-Instanzen.
- Entwicklung einer zweistufigen Metaheuristik für das VRPTW
- Implementierung und Test verschiedener lokaler Suchverfahren
- Bewertung der Algorithmeneffizienz anhand von Benchmark-Instanzen
- Analyse der Einflussfaktoren auf die Lösungsqualität
- Vergleich mit bestehenden Lösungsansätzen
Zusammenfassung der Kapitel
1 Einleitung: Dieses Kapitel führt in die Thematik der Tourenplanung mit Zeitfensterrestriktionen ein, beschreibt die Problemstellung des VRPTW und definiert die Zielsetzung der Arbeit. Es skizziert den Aufbau und die Gliederung der gesamten Arbeit, um dem Leser einen strukturierten Überblick zu bieten und die einzelnen Kapitel in ihren Zusammenhang zu stellen.
2 Grundlagen und Abgrenzung: Hier werden die theoretischen Grundlagen der Tourenplanung im Allgemeinen und speziell des VRPTW erläutert. Es erfolgt eine Abgrenzung zu verwandten Problemen und eine detaillierte Beschreibung des mathematischen Modells. Die Komplexität des Problems wird analysiert und verschiedene Ansätze zur Lösung kombinatorischer Optimierungsprobleme, insbesondere Heuristiken und Metaheuristiken, werden vorgestellt und in Bezug auf das VRPTW diskutiert. Die verschiedenen Typologien der Zeitfensterrestriktionen werden ebenso behandelt.
3 Verfahren zur Lösung des VRPTW: Dieses Kapitel beschreibt die im Rahmen der Arbeit entwickelten Verfahren zur Lösung des VRPTW. Es werden Konstruktionsverfahren für die Erstellung von Ausgangslösungen, die Definition von Nachbarschaftsstrukturen für lokale Suchverfahren und die Bewertungsfunktion zur Beurteilung der Güte von Lösungen detailliert dargestellt. Der Aufbau des Gesamtverfahrens, welches aus der Minimierung der Fahrzeuganzahl und der Gesamtfahrstrecke besteht, wird systematisch erläutert.
4 Algorithmische Beschreibung des Verfahrens: Dieses Kapitel bietet eine detaillierte algorithmische Beschreibung des in Kapitel 3 vorgestellten Verfahrens. Es beschreibt die Repräsentation der Datenstrukturen, elementare Zugriffe und Berechnungen, Zulässigkeitsbedingungen, Operationen und die Konstruktion der Ausgangslösung. Die algorithmische Umsetzung der verschiedenen Nachbarschaftsstrukturen (Or-Opt, 2-Opt*, Single-Interchange, Single-Insertion) wird ausführlich erklärt, ebenso das Bewertungsverfahren und das Verbesserungsverfahren, welches unter anderem die Ejection-Chain Heuristik und Threshold Accepting beinhaltet.
Schlüsselwörter
Tourenplanung, Vehicle Routing Problem with Time Windows (VRPTW), Metaheuristik, Lokale Suche, Nachbarschaftsstrukturen, Algorithmus, Optimierung, Zeitfensterrestriktionen, Komplexität, Heuristik, Benchmark-Instanzen, Solomon-Instanzen, Homberger-Instanzen.
Häufig gestellte Fragen (FAQ) zur Diplomarbeit: Zweistufige Metaheuristik für das Vehicle Routing Problem with Time Windows (VRPTW)
Was ist der Gegenstand dieser Diplomarbeit?
Die Diplomarbeit befasst sich mit der Entwicklung und Evaluation einer zweistufigen Metaheuristik zur Lösung des Vehicle Routing Problem with Time Windows (VRPTW). Ziel ist die effiziente Bestimmung von Tourenplänen, die sowohl die Anzahl der benötigten Fahrzeuge als auch die Gesamtfahrstrecke minimieren.
Welche Ziele werden in der Arbeit verfolgt?
Die Arbeit zielt darauf ab, eine effiziente zweistufige Metaheuristik für das VRPTW zu entwickeln, verschiedene lokale Suchverfahren zu implementieren und zu testen, die Algorithmeneffizienz anhand von Benchmark-Instanzen zu bewerten, die Einflussfaktoren auf die Lösungsqualität zu analysieren und die Ergebnisse mit bestehenden Lösungsansätzen zu vergleichen.
Wie ist die Arbeit aufgebaut?
Die Arbeit gliedert sich in fünf Kapitel: Einleitung (Problemstellung, Zielstellung, Aufbau), Grundlagen und Abgrenzung (Tourenplanung allgemein, VRPTW, mathematisches Modell, Komplexität, Lösungsansätze), Verfahren zur Lösung des VRPTW (Konstruktionsverfahren, Nachbarschaftsstrukturen, Bewertungsfunktion, Gesamtverfahren), Algorithmische Beschreibung des Verfahrens (Datenstrukturen, Operationen, Ausgangslösung, Nachbarschaftsstrukturen, Bewertungsverfahren, Verbesserungsverfahren) und Evaluation des Gesamtverfahrens (Probleminstanzen, Parametrisierung, Darstellung und Auswertung der Lösungen).
Welche Methoden werden eingesetzt?
Die Arbeit verwendet eine zweistufige Metaheuristik, die verschiedene lokale Suchverfahren wie Or-Opt, 2-Opt*, Single-Interchange und Single-Insertion beinhaltet. Weiterhin werden die Ejection-Chain Heuristik und Threshold Accepting eingesetzt. Die Evaluation erfolgt anhand von Benchmark-Instanzen von Solomon und Homberger.
Welche konkreten Algorithmen werden beschrieben?
Die algorithmische Beschreibung umfasst die Repräsentation der Datenstrukturen, elementare Zugriffe und Berechnungen, Zulässigkeitsbedingungen und Operationen. Ausführlich werden die algorithmischen Umsetzungen der verschiedenen Nachbarschaftsstrukturen und das Bewertungsverfahren beschrieben. Das Verbesserungsverfahren beinhaltet die Ejection-Chain Heuristik und Threshold Accepting.
Welche Ergebnisse werden präsentiert?
Die Ergebnisse der Evaluation werden anhand der berechneten Lösungen auf Basis der Probleminstanzen von Solomon und Homberger dargestellt und ausgewertet. Die Arbeit analysiert die Performance der entwickelten Metaheuristik und vergleicht sie implizit oder explizit mit bestehenden Lösungsansätzen.
Welche Schlüsselwörter beschreiben den Inhalt der Arbeit?
Tourenplanung, Vehicle Routing Problem with Time Windows (VRPTW), Metaheuristik, Lokale Suche, Nachbarschaftsstrukturen, Algorithmus, Optimierung, Zeitfensterrestriktionen, Komplexität, Heuristik, Benchmark-Instanzen, Solomon-Instanzen, Homberger-Instanzen.
Für welche Zielgruppe ist diese Arbeit gedacht?
Diese Arbeit richtet sich an Wissenschaftler und Studierende im Bereich der Operations Research, Logistik und Informatik, die sich mit Tourenplanung und Optimierungsproblemen befassen. Der Fokus liegt auf dem akademischen Nutzen, der Analyse von Themen und der strukturierten Darstellung.
- Quote paper
- Armin Bayer (Author), 2008, Zweistufen-Metaheuristik zur Lösung des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen unter Verwendung Lokaler Suche in zufallsgesteuerten Nachbarschaften, Munich, GRIN Verlag, https://www.grin.com/document/123841
