Multikriterielle Tourenplanung (eBook)

Dr. Wolf Wenger promovierte bei Prof. Dr. Walter Habenicht am Lehrstuhl für Industriebetriebslehre an der Universität Hohenheim.

Geleitwort 6
Vorwort 8
Inhaltsverzeichnis 9
Abbildungsverzeichnis 13
Tabellenverzeichnis 16
Algorithmenverzeichnis 18
Abkürzungsverzeichnis 19
Symbolverzeichnis 20
Kapitel 1 Einleitung 24
1.1 Problemstellung und Forschungsfragen 24
1.2 Aufbau der Arbeit 26
Kapitel 2 Entscheidungsfindung bei multiplen Zielsetzungen 28
2.1 Grundlagen der Entscheidungstheorie 28
2.1.1 Systematik eines Entscheidungsproblems 28
2.1.2 Entscheidungen unter Berücksichtigung multikriterieller Zielsysteme 29
2.1.3 Struktur multikriterieller Entscheidungen 30
2.2 Methoden zur Entscheidungsunterstützung bei multikriteriellen Zielsystemen 35
2.2.1 Klassifikation von Lösungstechniken 35
2.2.2 Funktionsbasierte Methoden 36
2.2.2.1 Grundlagen 36
2.2.2.2 Ausgewählte Verfahren 39
2.2.3 Relationenbasierte Methoden 43
2.2.3.1 Grundlagen 43
2.2.3.2 Ausgewählte Verfahren 44
2.2.4 Effizienzbasierte Methoden 48
2.2.4.1 Grundlagen 48
2.2.4.2 Ausgewählte Verfahren 53
2.3 Zur Wahl eines geeigneten multikriteriellen Entscheidungsunterstützungsverfahrens 56
Kapitel 3 Generelle Tourenplanungsprobleme 61
3.1 Standardprobleme der Tourenplanung und Erweiterungen 61
3.1.1 Allgemeine Charakteristik von Tourenplanungsproblemen 61
3.1.2 Erläuterung und formale Darstellung des CVRP 63
3.1.3 Erweiterungsmöglichkeiten des CVRP 67
3.2 Systematisierung der Klasse genereller Tourenplanungsprobleme 68
3.2.1 Verwendete Systematisierungskriterien 68
3.2.2 Auftragsstruktur 69
3.2.3 Depotstruktur 75
3.2.4 Transportmittelstruktur 77
3.2.5 Transportwegestruktur 80
3.2.6 Informationsstruktur 83
3.2.7 Zielsystemstruktur 86
3.3 Lösungsansätze für Tourenplanungsprobleme 89
3.3.1 Klassifizierung der Lösungsansätze 89
3.3.2 Exakte Lösungsverfahren 90
3.3.3 Heuristische Lösungsverfahren 91
3.3.3.1 Konstruierende Verfahren 92
3.3.3.2 Modifizierende Verfahren 95
3.3.4 Metaheuristiken 103
3.4 Tourenplanung unter Berücksichtigung multikriterieller Zielsysteme 107
3.4.1 Ausgestaltung multikriterieller Zielsystemstrukturen 107
3.4.2 Lösungsansätze multikriterieller Tourenplanungsprobleme 111
Kapitel 4 Empirische Relevanz multikriterieller Aspekte in Tourenplanungssystemen 115
4.1 Struktur und Ablauf der empirischen Untersuchung 115
4.1.1 Zielsetzungen und Aufbau der Befragungen 115
4.1.1.1 Branchenspezifischer Untersuchungsgegenstand 115
4.1.1.2 Leitfragen der Untersuchung 116
4.1.1.3 Verwendete Statistik 117
4.1.2 Grundgesamtheit und gezogene Stichproben 119
4.1.2.1 Grundgesamtheit der Probanden 119
4.1.2.2 Stichproben der ersten und zweiten Datenerhebung 119
4.1.3 Methodisches Vorgehen und erzielter Rücklauf 121
4.1.3.1 Vorgehen und Rücklauf der erstenn Datenerhebung 121
4.1.3.2 Vorgehen und Rücklauf der zweiten Datenerhebung 123
4.2 Ergebnisse und Implikationen der Untersuchungen 125
4.2.1 Charakterisierung praktischer Tourenplanungsprobleme in der Brauereibranche 125
4.2.1.1 Auftragsstruktur 125
4.2.1.2 Depotstruktur 128
4.2.1.3 Transportmittelstruktur 129
4.2.1.4 Transportwegestruktur 132
4.2.1.5 Informationsstruktur 134
4.2.2 Einsatz von Softwarelösungen zur Distribution in der Brauereibranche 136
4.2.3 Praktische Zielsystemstrukturen in der Brauereibranche 141
4.2.3.1 Tourenplanungsspezifischer Zielkriterienkatalog 141
4.2.3.2 Analyse der Bedeutung instrumenteller Zielkriterien 142
4.2.3.3 Analyse der Bedeutung fundamentaler Zielkriterien 145
4.2.3.4 Empirische Überprüfung der Fundamentalzieloperationalisierung durch den verwendeten Kriterienkatalog 149
4.2.3.5 Analyse der Umsetzung ausgewählter Aspekte in vorhandenen Systemen 153
Kapitel 5 Ein interaktives Entscheidungsunterstützungssystem zur multikriteriellen Tourenplanung 156
5.1 Konzeptionelle Rahmenbedingungen des Entscheidungsunterstützungssystems 156
5.2 Bestandteile und Struktur des Entscheidungsunterstützungssystems 158
5.2.1 Darstellung des Systemaufbaus 158
5.2.2 Aufgaben der Systemelemente 159
5.2.3 Handhabung problemspezifischer Inputdaten 162
5.3 Umsetzung einer multikriteriellen Zielsystemstruktur 165
5.3.1 Implementierte Zielkriterien 165
5.3.2 Systeminterne Modellierung partieller Wertfunktionen für die Zielkriterien 169
5.3.3 Globale Aggregation mittels interaktiver Zielgewichtung 177
5.3.4 Diskussion von Stärken und Schwächen eines additiven Modells zur interaktiven Variation der Zielsystemstruktur 179
5.4 Heuristische Suchstrategie zur Alternativengenerierung 184
5.4.1 Repräsentation von Alternativen 184
5.4.2 Implementierte konstruierende Strategien 185
5.4.3 Implementierte modifizierende Nachbarschaften 188
5.4.3.1 Rerouting 188
5.4.3.2 Reclustering 191
5.4.4 Kombinationen konstruierender und modifizierender Varianten in der interaktiven Suche 192
5.5 Experimenteller Ablauf 196
5.5.1 Verwendete Testdatensätze 196
5.5.2 Simulation beispielhafter Entscheidungsträger 197
5.5.2.1 Ausgewählte Entscheidungsträger mit spezifischen Zielsystemstrukturen 197
5.5.2.2 Simulation einer interaktiven Suche 199
5.6 Ergebnisse 202
5.6.1 Ergebnisevaluation 202
5.6.1.1 Adaptivität des Entscheidungsunterstützungssystems 202
5.6.1.2 Qualität der generierten Tourenpläne 203
5.6.2 Ergebnispräsentation 208
5.6.2.1 Adaptivität des Entscheidungsunterstützungssystems 208
5.6.2.2 Qualität der generierten Tourenpläne 219
Kapitel 6 Schlussbetrachtung 237
Anhang A Fragebögen der empirischen Untersuchungen 240
A.1 Fragebogen der ersten Datenerhebung 241
A.2 Fragebogen der zweiten Datenerhebung 247
Anhang B Ergänzendes zu Kapitel 5 251
B.1 Schwellenwerte der systemintern ermittelten und der für die ET-Typen angenommenen partiellen Wertfunktionen 251
B.2 Aggregierte Verläufe von Durchschnitts- und Streuungswerten zu UI für die Fälle (2) und (3) 253
Literaturverzeichnis 255

Kapitel 1 Einleitung (S. 1)

1.1 Problemstellung und Forschungsfragen

Logistikprozesse und deren planerische Gestaltung gewinnen im Zuge zunehmenden Wettbewerbsdrucks auf Lieferantenmärkten mehr und mehr an Bedeutung. Spezi.sche Kundenwünsche, wie etwa die Gewährleistung einer Just-in-Time-Lieferung sorgen hierbei dafür, dass neben einer hochwertigen und preislich attraktiven Ware bzw. Dienstleistung auch eine qualitative und kostengünstige Lieferung dieser Ware oder Dienstleistung bereitgestellt werden muss.

Eine für zahlreiche Unternehmen relevante Problemstellung in diesem Kontext ergibt sich durch den Wunsch nach einer möglichst optimalen Planung der Distributionslogistik, wobei sich hinter dem Optimalitätsbegriff je nach Planungssituation eine Vielzahl an relevanten Kriterien verbergen kann. Die Tourenplanung stellt als Teildisziplin der Distributionslogistik eine vor allem im Bereich des Operations Research viel beachtete Problemstellung dar.

Seit der initiierenden Publikation von Dantzig und Ramser im Jahr 1959 ist die Anzahl an veröffentlichten Beiträgen zum Themengebiet der Tourenplanung auf eine kaum überschaubare Zahl angestiegen. Nicht zuletzt die rasante Entwicklung leistungsfähiger Personalcomputer hat diese Tendenz in jüngerer Vergangenheit weiter verstärkt und die Konstruktion verschiedener Softwarepakete zur logistischen Tourenplanung unterstützt.

Obwohl hierbei verschiedenste reale Anwendungsfälle die Grundlage der analysierten Problemstellungen bilden, gilt die Aufmerksamkeit im Rahmen der Lösung bislang hauptsächlich der Identi.kation kostenminimaler Tourenpläne. Operationalisiert wird das verfolgte Ziel der Kostenminimierung häufig durch die Zielsetzung einer minimalen Gesamtstreckenlänge der ermittelten Tour, wohingegen weitere problemrelevante Aspekte in Form von Nebenbedingungen den Handlungsrahmen der Lösungskonzepte bilden.

In der Praxis finden sich allerdings eine Fülle spezifischer, bspw. von der betrachteten Branche abhängiger Rahmenbedingungen und Zielsetzungen, welche es bei der Ermittlung von Tourenplänen zu berücksichtigen gilt.

So können u. a. Aspekte des Lieferservices, der Mitarbeiterzufriedenheit oder des Umweltschutzes Einfluss auf die Entscheidung für oder gegen eine bestimmte Belieferungstour nehmen. Das Gebiet der Mehrzielforschung beschäftigt sich mit Entscheidungsprozessen bei Vorliegen mehrerer, teilweise konfliktärer Ziele.

Dabei kommen unterschiedliche Methoden zur Entscheidungsunterstützung zum Einsatz, wobei neuere Ansätze vermehrt ein interaktives Einbeziehen des Entscheidungsträgers in den Entscheidungsprozess vorschlagen. Auf diese Weise können vorhandene und veränderliche (Präferenz-) Informationen direkt in den Lösungsprozess einbezogen und gleichzeitig eine hohe Akzeptanz beim Anwender erreicht werden.

Die vorliegende Arbeit beschäftigt sich mit der Umsetzung einer geeigneten multikriteriellen Entscheidungsunterstützung für Tourenplanungsprobleme. In diesem Zusammenhang wird den folgenden Fragestellungen nachgegangen:

• Multikriterielle Entscheidungsunterstützung

Welche Verfahren zur Entscheidungsunterstützung bei Vorliegen einer multikriteriellen Zielsystemstruktur lassen sich unterscheiden, welche Anwendungsvoraussetzungen sind hierbei von Relevanz und worauf ist bei der Wahl eines geeigneten Entscheidungsunterstützungsverfahrens zu achten?

• Mono- und multikriterielle Tourenplanung

Durch welche Charakteristika sind in der wissenschaftlichen Literatur behandelte Tourenplanungsprobleme geprägt und wie lässt sich anhand dieser Charakteristika die Klasse genereller Tourenplanungsprobleme systematisieren? Welche Ziele und Zielsysteme sind hierbei von Relevanz und welche Lösungsansätze kommen in mono bzw. multikriterielle Problemstellungen der Tourenplanung zur Anwendung?