DIPLOMARBEIT

HYBRIDE ANSÄTZE BASIEREND AUF DYNAMIC PROGRAMMING

UND ANT COLONY OPTIMIZATION ZUR MEHRKRITERIELLEN

OPTIMIERUNG KÜRZESTER-WEGE-PROBLEME IN GERICHTETEN

GRAPHEN AM BEISPIEL VON ANGEBOTSNETZEN IM

EXTENDED VALUE CHAIN MANAGEMENT

eingereicht von

SASCHA HÄCKEL

zur Erlangung des akademischen Grades

Diplom-Wirtschaftsinformatiker (Dipl.-Wirt.-Inf.)

an der

Technischen Universität Chemnitz

Fakultät für Wirtschaftswissenschaften

Professur für Produktionswirtschaft und Industriebetriebslehre

Chemnitz, den 24. August 2006

---

---

Inhaltsverzeichnis

Abbildungsverzeichnis

vii

Tabellenverzeichnis

ix

Algorithmenverzeichnis

x

Abkürzungsverzeichnis

xi

Verwendete Notationen

xiii

Symbolverzeichnis

xiv

1

Einführung

1

1.1

Gegenstand der Arbeit .

1

1.2

Dokumentstruktur .

2

2

Theoretische Grundlagen

3

2.1

Grundlagen der Graphentheorie .

3

2.1.1

Gerichtete Graphen .

3

2.1.2

Wichtige Eigenschaften von Graphen .

4

2.2

Grundlagen der Komplexitätstheorie .

4

2.2.1

Komplexitätsmaße .

5

2.2.2

Komplexitätsklassen P und NP .

5

2.2.3

Problemrelationen und polynomielle Reduktion .

6

2.3

Diskrete und kombinatorische Optimierung .

7

2.3.1

Problemdefinition und Eigenschaften .

7

2.3.2

Ausgewählte Optimierungsprobleme .

7

3

Optimierung bei Mehrfachzielsetzung

11

3.1

Mehrkriterielle Probleme .

11

3.1.1

Problemstellung .

11

3.1.2

Zielbeziehungen .

12

3.2

Optimalität bei mehrfacher Zielsetzung .

13

3.2.1

Paretooptimalität .

13

3.2.2

Eigenschaften der paretooptimalen Lösungsmenge .

14

3.2.3

Idealpunkte und Nadir-Punkt der Front .

14

3.3

Multikriterielle kombinatorische Optimierung .

15

3.3.1

Klassifizierung entscheidungstheoretischer Ansätze .

16

3.3.2

A-priori-Methoden als reduktive Verfahren .

19

3.3.3

A-posteriori-Methoden als nicht-reduktive Verfahren .

20

iii

---

INHALTSVERZEICHNIS

3.4

Reduktive Entscheidungsmodelle .

22

3.4.1

Lexikographische Ordnung .

22

3.4.2

Haupt- und Nebenziele .

23

3.4.3

Methode der gewichteten Summen und Produkte .

23

3.4.4

AHP .

26

3.4.5

Fuzzy Decision Making .

27

3.4.6

Goal Programming und Compromise Programming .

29

3.5

Fazit .

29

3.5.1

Beurteilung der A-priori-Methoden .

30

3.5.2

Beurteilung der A-posteriori-Methoden .

30

4

Optimierung von Angebotsnetzen im EVCM

33

4.1

Extended Value Chain Management .

33

4.1.1

Phasenmodell .

33

4.1.2

Prozessvariantenplan und Prozessplan .

35

4.1.3

Angebotsnetze .

37

4.1.4

Problemstellung bei der Kompetenzzellenauswahl .

39

4.2

Formalisierung des Problems .

41

4.2.1

Problemgraph .

41

4.2.2

Restriktionssystem .

42

4.2.3

Lösungskonstruktion und Problemstellung .

45

4.3

Zielsetzungen der Optimierung .

46

4.3.1

Preis .

46

4.3.2

Lieferwahrscheinlichkeit .

46

4.3.3

Liefertermin .

50

4.4

Angebote mit unvollständigen Mengen .

52

4.4.1

Ansatz mit impliziter Behandlung von Teilmengen .

53

4.4.2

Ansatz mit Behandlung expliziter Fehlmengen .

55

4.5

Problemkomplexität .

57

5

Dynamic Programming

61

5.1

Theoretische Grundlagen .

61

5.1.1

Einführung .

62

5.1.2

Problemstellung und Lösungsprinzip .

62

5.1.3

Verfahren .

68

5.2

Problemspezifische Modellierung .

69

5.2.1

Problemspezifischer Basisalgorithmus .

69

5.2.2

Umgang mit Divergenzen .

72

5.3

Komplexitätsbetrachtungen .

79

5.3.1

Komplexität bei einkriteriellen Problemen mit rein konvergierenden Prozessplänen 80

5.3.2

Komplexität bei einkriteriellen Problemen mit allgemeinen Prozessplänen .

80

6

Ant Colony Optimization

83

6.1

Einführung .

83

6.1.1

Einordnung des Verfahrens .

83

6.1.2

Naturanalogie .

84

6.1.3

ACO-Metaheuristik .

86

6.2

Verschiedene Ansätze .

88

6.2.1

Ant System .

89

iv

---

INHALTSVERZEICHNIS

6.2.2

Ant Colony System .

91

6.3

Mehrkriterielle Ameisenalgorithmen .

93

6.3.1

Überblick .

93

6.3.2

Paretooptimierung mit ACO .

94

6.3.3

Gewichtung bei beliebiger Zielanzahl .

97

6.4

Problemspezifische Modellierung 100

6.4.1

Ant Family Heuristic 100

6.4.2

Lösungskonstruktion 102

6.4.3

Heuristikwerte für das Angebotsnetz 108

6.4.4

Konvergenzverhalten und Pheromoninitialisierung 109

7

Hybride Methoden und Erweiterungen

111

7.1

Pheromonaktualisierung bei Paretooptimierung 111

7.1.1

Eigenschaften der bisherigen Strategie 111

7.1.2

Nadir-Punkt-Strategie 112

7.2

Paretooptimierung mit Auswahl nach Fuzzy Decision Making 115

7.2.1

Ausgangssituation 115

7.2.2

Auswahlwahrscheinlichkeiten über Fuzzy Decision Making 116

7.3

Problemreduktion 117

7.3.1

Dominanz von Teilgraphen 117

7.3.2

Algorithmisches Konzept 119

7.4

Die Look-Ahead-Heuristic 120

7.4.1

Ausgangssituation 120

7.4.2

Konzept der Look-Ahead-Heuristic 122

8

Evaluierung

125

8.1

Evaluierung des Parallel Path Problems und des dynamischen Programms 125

8.1.1

Verwendete Evaluierungsmaße 125

8.1.2

Abhängigkeiten zwischen Komplexität und Zielkriterien 127

8.1.3

Abhängigkeiten zwischen Paretofront und Zielfunktionen 128

8.1.4

Komplexität von Angebotsnetzen 130

8.1.5

Probleme mit divergenten Prozessplänen 132

8.2

Evaluierung ACO und hybride Ansätze 133

8.2.1

Verwendete Evaluierungsmaße 133

8.2.2

Problemlösungsverhalten der Ameisenalgorithmen 136

8.2.3

Verwendung von Routingtabellen und Tabulisten 137

8.2.4

Aktualisierungsstrategien 140

8.2.5

Analyse verschiedener Aggregationsmethoden 141

8.2.6

Standard-Heuristik und Look-Ahead-Heuristic 142

8.2.7

Problemreduktion 146

Fazit und Ausblick

149

A Ergänzungen und Detailinformationen zur Evaluierung

151

A.1 Evaluierte Problemgraphen und Prozesspläne 151

A.1.1 Technologiegraphen 151

A.1.2 Problemgraphen 153

A.2 Verwendete Konfigurationen und Parameter von ACO 154

A.2.1 Verwendete Konfiguration 154

v

---

INHALTSVERZEICHNIS

A.2.2 Verwendete Parameter 155

B Beispielrechnung

157

B.1 Dynamisches Programm 159

B.2 Lösungskonstruktion ACO 164

Literaturverzeichnis

167

Register

175

vi

---

Abbildungsverzeichnis

1.1

Strukturelle Abhängigkeit der Kapitel .

2

2.1

Beispielhaftes Kürzeste-Wege-Problem .

9

3.1

Vergleich von MODM und MADM sowie der kombinatorischen Optimierung .

17

3.2

Indifferenzkurven bei Verfahren mit und ohne Kompensation .

18

3.3

Grafische Darstellung von Zielfunktionen der Methode der gewichteten Summe .

25

4.1

Phasenmodell des EVCM .

34

4.2

Beispielhafter Graph eines Prozessplans für die Herstellung eines Produktes .

36

4.3

Beispielhaftes Angebotsnetz für ein Produkt .

37

4.4

Konvergenzreihen bei der Multiplikation vieler kleiner Werte für C#-Datentypen .

48

4.5

Schematische Darstellung eines Fließkommadatentyps .

49

4.6

Rucksackproblem als bikriterielles Shortest Path Problem .

59

5.1

Einordnung von Dynamic Programming als Verfahren .

62

5.2

Schematisches Modell eines dynamischen Optimierungsproblems .

64

5.3

Paretooptimierung bei dynamischen Programmen .

67

5.4

Beispielhafte Segmentierung des Angebotsnetzes in Stufen .

70

5.5

Minimalbeispiel für die Nichteignung von Mittelwertfunktionen bei dynamischen Pro-

grammen .

71

5.6

Beispiel für die Verletzung der MARKOV-Eigenschaft bei divergenten Prozessen .

75

5.7

Teilproblembildung bei divergierenden Prozessen .

75

5.8

Komplexer Prozessplan mit exponentiellen Aufwand .

81

6.1

Einordnung von Ant Colony Optimization als heuristisches Verbesserungsverfahren . . .

84

6.2

Doppelbrückenexperiment mit argentinischen Ameisen .

85

6.3

Kriteriengewichtung auf Basis des Durchmusterungsparameters .

98

6.4

Suchdurchmusterung bei drei Kriterien .

99

7.1

Vergleich der mehrkriteriellen Aktualisierungsstrategien 113

7.2

Problemreduktion mit dynamischer Programmierung am Beispiel 118

8.1

Komplexität und Anzahl der Zielkriterien 127

8.2

Konvexe Paretofront des Problems T010 129

8.3

Konkave Paretofront des Problems T011 129

8.4

Paretofront des Problems G036 mit typischem Verlauf für Angebotsnetze 130

8.5

Vergleich der Approximation der verschiedenen Algorithmenvarianten für G030 138

8.6

Vergleich des Diversitätsmaßes der verschiedenen Algorithmenvarianten für G030 138

8.7

Branching-Faktor bei der Anwendung der verschiedenen Algorithmen auf G030 139

vii

---

ABBILDUNGSVERZEICHNIS

8.8

Paretofront und nichtdominierte Fronten verschiedener ACO-Läufe für G040 142

8.9

Approximation als Distanzmaß im Vergleich von Standard-Heuristik und LAH für G040

144

8.10 Diversität als Distanzmaß im Vergleich von Standard-Heuristik und LAH für G040 144

8.11 Vergleich der nichtdominierten Fronten von LAH und Standard-Heuristik 146

A.1 Prozesspläne der Technologiegraphen TG01 und TG01a-c 152

B.1 Darstellung des Problemgraphen von B001 158

B.2 Zugrunde liegender Prozessplan des Problems B001 159

viii

---

Tabellenverzeichnis

3.1

(1-9)-Bewertungsskala des Analytical Hierarchy Process .

26

8.1

Zielfunktionen der Probleme T010, T011 und G036 128

8.2

Übersicht über die exakte Lösbarkeit beziehungsweise Nichtlösbarkeit von Problemen . . 131

8.3

Übersicht über die exakte Lösbarkeit beziehungsweise Unlösbarkeit von Problemen mit

Divergenzen 132

8.4

Eingesetzte Parameterkonfigurationen von verschiedenen ACO-Algorithmen 136

8.5

Ergebnisse der Evaluierungsläufe mit mehrkriteriellen Ameisenalgorithmen 137

8.6

Ergebnisse der Evaluierungsläufe mit und ohne Verwendung von Routing 139

8.7

Testergebnisse bei Verwendung verschiedener Update-Strategien 141

8.8

Testergebnisse bei Verwendung verschiedener Aggregationsmethoden 141

8.9

Approximation, Diversität und Größe der ermittelten Front im Vergleich bei Verwendung

der Standard-Heuristik und der Look-Ahead-Heuristic 143

8.10 Evaluierung der Schwellwertübertretungen der Diversität bei Verwendung der Standard-

Heuristik und der Look-Ahead-Heuristic 145

8.11 Testergebnisse für den Vergleich von LAH in der Best- und Worst-Case-Variante hinsicht-

lich Distanz, Diversität und Frontgröße 146

8.12 Testergebnisse für den Vergleich von LAH in der Best- und Worst-Case-Variante hinsicht-

lich der Diversität 147

8.13 Auswirkungen der Problemreduktion auf die Eingabelänge und Lösungsraumgröße . . . 147

8.14 Testergebnisse mit den Auswirkungen der Problemreduktion auf ACS 148

A.1 Übersicht über alle verwendeten Prozesspläne (Technologiegraphen) 151

A.2 Übersicht über alle verwendeten Problemgraphen 153

A.3 Parameter der verwendeten Konfigurationen (1) 154

A.4 Parameter der verwendeten Konfigurationen (2) 155

A.5 Parameter der verwendeten Konfigurationen (3) 155

B.1 Zielfunktionsbeiträge der Angebote des bikriteriellen Problems B001 157

ix

---

Algorithmenverzeichnis

1

Automatisierte Generierung des Restriktionssystems eines Angebotsnetzes .

44

2

Testalgorithmus zur Analyse der Präzision des Datentyps double .

47

3

Dynamisches Programm zur Lösung rein konvergierender Parallel Path Probleme . . . .

73

4

Hilfsfunktionen für das dynamische Programm für rein konvergierende Probleme . . . .

74

5

Auflösung von Restriktion und restriktionsbehaftete Pfadkonstruktion .

77

6

Dominanzvergleiche bei Divergenzen .

78

7

Generierung von Lösungskombinationen bei Problemen mit Divergenzen .

79

8

Algorithmenskelett der ACO-Metaheuristik .

87

9

Generierung von Routingtabellen für das Forwarding von Ameisenagenten 104

10

Lösungskonstruktion der Ameisen unter Nutzung von Routing und Restriktionen 106

11

Generierung von Tabulisten für Knoten als Agentenrestriktionen 107

12

Erstellen von zulässigen Auswahlmengen auf Basis von Tabulisten 108

13

Dynamisches Programm zur Problemreduktion 119

14

Hilfsfunktionen zur Problemreduktion 120

15

Berechnung von Look-Ahead-Heuristic-Werten für das Parallel Path Problem 123

16

Bestimmung der Lösungsraumgröße 126

x

---