Zweistufen-Metaheuristik zur Lösung des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen unter Verwendung Lokaler Suche in zufallsgesteuerten Nachbarschaften


Diplomarbeit, 2008

113 Seiten, Note: 1,0


Leseprobe


Diplomarbeit
Zweistufen-Metaheuristik zur Lösung des Standardproblems
der Tourenplanung mit Zeitfensterrestriktionen unter
Verwendung Lokaler Suche in zufallsgesteuerten
Nachbarschaften
verfasst und vorgelegt von
Armin Bayer
zur Erlangung des akademischen Grades
Diplom-Mathematiker (FH)
Abgabedatum der Arbeit: 17. April 2008
Hochschule für Technik, Wirtschaft und Kultur Leipzig
Fachbereich Informatik, Mathematik und Naturwissenschaften

Inhaltsverzeichnis
Seite I
Inhaltsverzeichnis
1 Einleitung
1
1.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Zielstellung der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3 Aufbau und Gliederung der Arbeit
. . . . . . . . . . . . . . . . . . . . .
2
2 Grundlagen und Abgrenzung
3
2.1 Tourenplanung im Allgemeinen . . . . . . . . . . . . . . . . . . . . . . .
3
2.2 Tourenplanung mit zeitlicher Restriktion . . . . . . . . . . . . . . . . . .
6
2.2.1
Voraussetzungen und Realitätsbeschränkung . . . . . . . . . . . .
6
2.2.2
Mathematische Modellbildung
. . . . . . . . . . . . . . . . . . .
9
2.2.3
Komplexitätsuntersuchung des VRPTW . . . . . . . . . . . . . . .
12
2.2.4
Typologie der Zeitfensterrestriktionen . . . . . . . . . . . . . . .
15
2.3 Ansätze zur Lösung kombinatorischer Optimierungsprobleme . . . . . .
17
2.3.1
Problemspezifische Heuristiken . . . . . . . . . . . . . . . . . . .
17
2.3.2
Metaheuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3 Verfahren zur Lösung des VRPTW
23
3.1 Konstruktionsverfahren
. . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.2 Definition der Nachbarschaftsstrukturen . . . . . . . . . . . . . . . . . .
24
3.3 Bewertungsfunktion eines Tourenplans . . . . . . . . . . . . . . . . . . .
26
3.4 Aufbau des Gesamtverfahrens . . . . . . . . . . . . . . . . . . . . . . . .
28
3.4.1
Minimierung der Fahrzeuganzahl . . . . . . . . . . . . . . . . . .
28
3.4.2
Minimierung der Gesamtfahrstrecke . . . . . . . . . . . . . . . .
30
4 Algorithmische Beschreibung des Verfahrens
32
4.1 Repräsentation elementarer Komponenten . . . . . . . . . . . . . . . . .
32
4.1.1
Repräsentation der Kunden . . . . . . . . . . . . . . . . . . . . .
32
4.1.2
Repräsentation der Tourenpläne . . . . . . . . . . . . . . . . . . .
33
4.2 Elementare Zugriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.3 Elementare Berechnungen . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

Inhaltsverzeichnis
Seite II
4.4 Elementare Zulässigkeitsbedingungen . . . . . . . . . . . . . . . . . . .
39
4.5 Elementare Operationen . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.6 Konstruktion der Ausgangslösung . . . . . . . . . . . . . . . . . . . . . .
53
4.7 Algorithmische Umsetzung der Nachbarschaftsstrukturen . . . . . . . . .
56
4.7.1
Operator Or-Opt . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.7.2
Operator 2-Opt* . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
4.7.3
Operator Single-Interchange . . . . . . . . . . . . . . . . . . . . .
59
4.7.4
Operator Single-Insertion . . . . . . . . . . . . . . . . . . . . . .
60
4.7.5
Auswahl des Operators . . . . . . . . . . . . . . . . . . . . . . . .
61
4.8 Bewertung von Tourenplänen . . . . . . . . . . . . . . . . . . . . . . . .
62
4.9 Verbesserungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
4.9.1
Ejection-Chain Heuristik . . . . . . . . . . . . . . . . . . . . . . .
71
4.9.2
Rekursion der Ejection-Chain . . . . . . . . . . . . . . . . . . . .
72
4.9.3
Lokale Suche zur Minimierung der Tourenanzahl . . . . . . . . .
75
4.9.4
Lexikographischer Vergleichsoperator . . . . . . . . . . . . . . . .
77
4.9.5
Akzeptanz einer verschlechterten Lösung . . . . . . . . . . . . . .
78
4.9.6
Metaheuristik: Threshold Accepting . . . . . . . . . . . . . . . . .
79
4.9.7
Verfahren zur Minimierung der Gesamtfahrstrecke . . . . . . . .
80
5 Evaluation des Gesamtverfahrens
82
5.1 Probleminstanzen von Solomon und Homberger . . . . . . . . . . . . . .
82
5.2 Parametrisierung des Gesamtverfahrens . . . . . . . . . . . . . . . . . .
89
5.3 Darstellung der berechneten Lösungen . . . . . . . . . . . . . . . . . . .
90
5.4 Auswertung der berechneten Lösungen . . . . . . . . . . . . . . . . . . .
97
6 Zusammenfassung
100
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

Abbildungsverzeichnis
Seite III
Abbildungsverzeichnis
2.1 Beziehungen innerhalb der Klasse der Tourenplanungsprobleme . . . . .
5
2.2 VRPTW als Vektoroptimierungsproblem . . . . . . . . . . . . . . . . . .
11
2.3 Komplexität eines exponentiellen Algorithmus im worst case . . . . . . .
14
2.4 Lokale Suche im gesteuerten und ungesteuerten Fall . . . . . . . . . . .
22
3.1 Inter-Move des Or-Opt Operators . . . . . . . . . . . . . . . . . . . . . .
24
3.2 Move des 2-Opt* Operators . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.3 Inter-Move des Single-Interchange Operators . . . . . . . . . . . . . . .
26
3.4 Move des Single-Insertion Operators . . . . . . . . . . . . . . . . . . . .
26
3.5 Hierarchische Vergleichskriterien bezüglich zweier Tourenpläne . . . . .
27
3.6 Aufbau des Gesamtverfahrens . . . . . . . . . . . . . . . . . . . . . . . .
30
4.1 Repräsentation der Kunden . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2 Repräsentation der Tourenpläne . . . . . . . . . . . . . . . . . . . . . . .
34
4.3 Zeitliche Darstellung einer Tour . . . . . . . . . . . . . . . . . . . . . . .
47
4.4 Exemplarischer Schritt des Savingsverfahrens . . . . . . . . . . . . . . .
53
4.5 Topologische Darstellung einer Lösung . . . . . . . . . . . . . . . . . . .
55
4.6 Kennzahlen zur Bewertung von Tourenplänen . . . . . . . . . . . . . . .
63
4.7 Darstellung der zusätzlichen Pufferzeit . . . . . . . . . . . . . . . . . . .
70
4.8 Exemplarischer Rekursionsbaum der Ejection-Chain . . . . . . . . . . . .
75
5.1 Spezifikation der Solomon Probleminstanzen . . . . . . . . . . . . . . .
83
5.2 Spezifikation der Homberger Probleminstanzen mit 200 Kunden . . . . .
84
5.3 Spezifikation der Homberger Probleminstanzen mit 400 Kunden . . . . .
85
5.4 Spezifikation der Homberger Probleminstanzen mit 600 Kunden . . . . .
86
5.5 Spezifikation der Homberger Probleminstanzen mit 800 Kunden . . . . .
87
5.6 Spezifikation der Homberger Probleminstanzen mit 1000 Kunden . . . .
88
5.7 Testumgebung und Parametrisierung wichtiger Verfahrensgrößen . . . .
89
5.8 Berechnete Lösungen der Solomon Probleminstanzen . . . . . . . . . . .
91
5.9 Berechnete Lösungen der Homberger Probleminstanzen mit 200 Kunden
92
5.10 Berechnete Lösungen der Homberger Probleminstanzen mit 400 Kunden
93
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

Abbildungsverzeichnis
Seite IV
5.11 Berechnete Lösungen der Homberger Probleminstanzen mit 600 Kunden
94
5.12 Berechnete Lösungen der Homberger Probleminstanzen mit 800 Kunden
95
5.13 Berechnete Lösungen der Homberger Probleminstanzen mit 1000 Kunden 96
5.14 Darstellung einer berechneten Lösung des Problems RC104 . . . . . . .
98
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

Algorithmenverzeichnis
Seite V
Algorithmenverzeichnis
4.1 Ermittlung des Vorgängers . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2 Ermittlung des Nachfolgers . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.3 Ermittlung einer Tour
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.4 Ermittlung der kleinsten Tour . . . . . . . . . . . . . . . . . . . . . . . .
36
4.5 Berechnung Anzahl Touren . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.6 Kundenanzahl der kleinsten Tour . . . . . . . . . . . . . . . . . . . . . .
37
4.7 Distanz einer ausgezeichneten Tour . . . . . . . . . . . . . . . . . . . . .
38
4.8 Berechnung der Gesamtdistanz . . . . . . . . . . . . . . . . . . . . . . .
38
4.9 Zulässigkeitsprüfung: Einfügen eines Kunden . . . . . . . . . . . . . . .
39
4.10 Zulässigkeitsprüfung: Verdrängen eines Kunden . . . . . . . . . . . . . .
41
4.11 Zulässigkeitsprüfung: Einfügen einer Kundenkette . . . . . . . . . . . . .
42
4.12 Zulässigkeitsprüfung: Einfügen einer Kante . . . . . . . . . . . . . . . .
43
4.13 Zulässigkeitsprüfung: Kreuzen zweier Kanten . . . . . . . . . . . . . . .
44
4.14 Operation: Einfügen eines Kunden . . . . . . . . . . . . . . . . . . . . .
45
4.15 Operation: Aktualisierung der frühesten Abfahrtszeit . . . . . . . . . . .
46
4.16 Operation: Aktualisierung der spätest zulässigen Ankunftszeit . . . . . .
48
4.17 Operation: Aktualisierung der Tour . . . . . . . . . . . . . . . . . . . . .
48
4.18 Operation: Löschen eines Kunden . . . . . . . . . . . . . . . . . . . . . .
49
4.19 Operation: Verdrängen eines Kunden . . . . . . . . . . . . . . . . . . . .
50
4.20 Operation: Zerschneiden einer Tour . . . . . . . . . . . . . . . . . . . . .
51
4.21 Operation: Einfügen einer Kante . . . . . . . . . . . . . . . . . . . . . .
51
4.22 Operation: Kreuzen zweier Kanten . . . . . . . . . . . . . . . . . . . . .
52
4.23 Pseudo-Code: Savingsverfahren . . . . . . . . . . . . . . . . . . . . . . .
54
4.24 Pseudo-Code: Operator Or-Opt . . . . . . . . . . . . . . . . . . . . . . .
57
4.25 Pseudo-Code: Operator 2-Opt* . . . . . . . . . . . . . . . . . . . . . . .
58
4.26 Pseudo-Code: Operator Single-Interchange . . . . . . . . . . . . . . . . .
59
4.27 Pseudo-Code: Operator Single-Insertion . . . . . . . . . . . . . . . . . .
61
4.28 Zufällige Auswahl des Operators . . . . . . . . . . . . . . . . . . . . . .
62
4.29 Ermittlung der Verspätung . . . . . . . . . . . . . . . . . . . . . . . . . .
65
4.30 Bewertungsfunktion: Ermittlung der erforderlichen Gesamtverspätung .
66
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

Algorithmenverzeichnis
Seite VI
4.31 Bewertungsfunktion: Ermittlung der erforderlichen Überladung . . . . .
67
4.32 Berechnung der Verschiebezeit . . . . . . . . . . . . . . . . . . . . . . .
68
4.33 Berechnung der zusätzlichen Pufferzeit . . . . . . . . . . . . . . . . . . .
69
4.34 Hauptfunktion der Ejection-Chain . . . . . . . . . . . . . . . . . . . . . .
71
4.35 Rekursion der Ejection-Chain . . . . . . . . . . . . . . . . . . . . . . . .
72
4.36 Erste Verfahrensstufe: Lokale Suche . . . . . . . . . . . . . . . . . . . . .
76
4.37 Lexikographischer Vergleich zweier Tourenpläne
. . . . . . . . . . . . .
77
4.38 Akzeptanzfunktion für verschlechternde Lösungen
. . . . . . . . . . . .
78
4.39 Zweite Verfahrensstufe: Threshold Accepting Metaheuristik
. . . . . . .
79
4.40 Verfahren zur Minimierung der Gesamtfahrstrecke . . . . . . . . . . . .
81
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

1. Einleitung
Seite 1
1 Einleitung
1.1
Problemstellung
In den letzten Jahrzehnten rückte ein Bereich der kombinatorischen Optimierungspro-
bleme immer mehr in den Brennpunkt der Forschung: die Klasse der Tourenplanungs-
probleme. Immer mehr Güter müssen in immer kürzerer Zeit von einem Ort zum ande-
ren transportiert werden. Bei der Tourenplanung werden daher Fragestellungen disku-
tiert, 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 einzuhal-
ten. In der Praxis treten häufig Einschränkungen in Form einer begrenzten Ladekapa-
zitä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ögli-
chen 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.
Wie Lenstra u. Kan (1981) zeigten, gehört das Tourenplanungsproblem mit Zeitfenster-
restriktionen, das in der angelsächsischen Literatur unter dem Namen ,,Vehicle Routing
Problem with Time Windows" (VRPTW) zu finden ist, zu den N P-harten Optimierungs-
problemen. In der Klasse der N P-harten Probleme fasst man all diejenigen Optimie-
rungsprobleme zusammen, deren optimale Lösung nach gegenwärtigem Wissen prak-
tisch nicht in polynomialem Zeitaufwand gefunden werden kann. Charakteristisch für
solche Probleme ist vielmehr, dass die Zeitkomplexität für das Finden der optimalen
Lösung exponentiell mit der Problemgröße wächst. Auf Grund dessen werden solche
Probleme meist mit heuristischen Verfahren untersucht. Sie zeichnen sich dadurch aus,
in akzeptablem Zeitaufwand gute Lösungen zu erzielen. Im Unterschied zu exakten
Lösungsmethoden, wie beispielsweise dem Branch and Bound Algorithmus oder den
Dekompositionsverfahren ist das Finden der optimalen Lösung jedoch nicht garantiert.
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

1. Einleitung
Seite 2
In der Literatur wird dem Tourenplanungsproblem mit Zeitfensterrestriktionen meist
eine hierarchische Zielstellung zu Grunde gelegt, einem primären sowie einem sekun-
dären Ziel. Vorrangig ist hierbei die Minimierung der benötigten Fahrzeuge, nachrangig
die Minimierung der zurückgelegten Gesamtfahrstrecke. Seit Mitte der Siebziger Jah-
re 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, Si-
mulated Annealing und Tabu-Search.
1.2
Zielstellung der Arbeit
Eine Zielsetzung dieser Arbeit ist es, einen geeigneten Algorithmus zur Lösung des Tou-
renplanungsproblems mit Zeitfensterrestriktionen vorzustellen und diesen zu evaluie-
ren. Um die Güte der Lösung abschätzen zu können, werden die Benchmark Probleme
von Solomon (1987) bzw. Homberger (2000) herangezogen und mit den bisher besten
in der Literatur veröffentlichten Lösungen verglichen. Ein zweites Ziel wird sein, ein
weiteres, von der Literatur bisher unbeachtetes Kriterium zur Bewertung einer gefun-
denen 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 an-
nähernd gleich lange unterwegs ist wie seine Kollegen auf den anderen Touren. Dabei
wird dieses Kriterium nicht als Ziel sondern als Wunsch formuliert.
1.3
Aufbau und Gliederung der Arbeit
Nach der Einleitung wird im zweiten Kapitel das Standardproblem der Tourenplanung
mit Zeitfensterrestriktionen vorgestellt, eine Realitätsabgrenzung vorgenommen und
das dazugehörige mathematische Modell aufgestellt. Nach der Betrachtung grundlegen-
der Heuristiken zur Lösung kombinatorischer Optimierungsprobleme folgt im dritten
Kapitel die Konzeption des Verfahrens zur Untersuchung und Optimierung des VRPTW.
Dieses Verfahren wird im Anschluss in Kapitel vier in Form einer algorithmischen Be-
schreibung dargestellt. Die Auswertung des Verfahrens mit den von Solomon (1987)
und Homberger (2000) bereitgestellten Probleminstanzen bildet den Abschluss dieser
Arbeit.
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig

2. Grundlagen und Abgrenzung
Seite 3
2 Grundlagen und Abgrenzung
2.1
Tourenplanung im Allgemeinen
In der Tourenplanung sieht die Ausgangssituation wie folgt aus:
Anhand einer gegebenen Anzahl an Fahrzeugen, die sich an verschiedenen Depots befin-
den können, müssen eine bestimmte Anzahl an Kunden so bedient werden, dass gegebene
Restriktionen eingehalten und eine vorher definierte Zielfunktion optimiert wird.
Diese allgemeine Aussage trifft auf fast alle Probleme innerhalb der Klasse der Touren-
planungsprobleme zu. Darin enthalten sind unter anderem das Traveling Salesman Pro-
blem (TSP), das klassische Tourenplanungsproblem sowie das Pickup and Delivery Pro-
blem (PDP). Der Begriff ,,Depot" kennzeichnet hierbei den Ort, an dem die Auslieferungs-
bzw. Sammelaufträge beginnen und enden. Eine Übersicht der verschiedenen Problem-
zusammenhänge liefert Abb. 2.1. Um eine Abgrenzung der einzelnen Probleme zu errei-
chen, werden in der heutigen Literatur vier Kriterienklassen unterschieden (vgl. Domsch-
ke (1997)): ,,
Adressen", ,,Fahrzeuge", ,,Problemcharakteristika" und ,,Ziele".
Die Kriteriumklasse
Adressen lässt sich klassifizieren nach:
· Anzahl der gegebenen Depots,
· Anzahl der zu beliefernden Kunden,
· Art der Aufträge:
­ nur Belieferung oder nur Abholung oder gemischt,
­ kein, ein oder mehrere Zeitfenster vorhanden,
· Restriktionen an der Adressenauswahl:
­ alle Adressen müssen besucht werden,
­ nur eine Teilmenge der Adressen muss besucht werden,
­ wie oft dürfen Adressen besucht werden.
Armin Bayer
Hochschule für Technik, Wirtschaft und Kultur Leipzig
Ende der Leseprobe aus 113 Seiten

Details

Titel
Zweistufen-Metaheuristik zur Lösung des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen unter Verwendung Lokaler Suche in zufallsgesteuerten Nachbarschaften
Hochschule
Hochschule für Technik, Wirtschaft und Kultur Leipzig
Note
1,0
Autor
Jahr
2008
Seiten
113
Katalognummer
V123841
ISBN (eBook)
9783640285624
ISBN (Buch)
9783640286133
Dateigröße
947 KB
Sprache
Deutsch
Schlagworte
Zweistufen-Metaheuristik, Lösung, Standardproblems, Tourenplanung, Zeitfensterrestriktionen, Verwendung, Lokaler, Suche, Nachbarschaften
Arbeit zitieren
Armin Bayer (Autor:in), 2008, Zweistufen-Metaheuristik zur Lösung des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen unter Verwendung Lokaler Suche in zufallsgesteuerten Nachbarschaften, München, GRIN Verlag, https://www.grin.com/document/123841

Kommentare

  • Noch keine Kommentare.
Blick ins Buch
Titel: Zweistufen-Metaheuristik zur Lösung des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen unter Verwendung Lokaler Suche in zufallsgesteuerten Nachbarschaften



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden