Hybride Ansätze zur Optimierung Kürzester-Wege-Probleme in gerichteten Graphen

Angebotsnetze im Extended Value Chain Management

Diplomarbeit, 2006
197 Seiten, Note: 1,0

Informatik - Wirtschaftsinformatik

Leseprobe

Inhaltsverzeichnis

Einführung

Gegenstand der Arbeit
Dokumentstruktur

Theoretische Grundlagen

Grundlagen der Graphentheorie

Gerichtete Graphen
Wichtige Eigenschaften von Graphen

Grundlagen der Komplexitätstheorie

Komplexitätsmaße
Komplexitätsklassen P und NP
Problemrelationen und polynomielle Reduktion

Diskrete und kombinatorische Optimierung

Problemdefinition und Eigenschaften
Ausgewählte Optimierungsprobleme

Optimierung bei Mehrfachzielsetzung

Mehrkriterielle Probleme

Problemstellung
Zielbeziehungen

Optimalität bei mehrfacher Zielsetzung

Paretooptimalität
Eigenschaften der paretooptimalen Lösungsmenge
Idealpunkte und Nadir-Punkt der Front

Multikriterielle kombinatorische Optimierung

Klassifizierung entscheidungstheoretischer Ansätze
A-priori-Methoden als reduktive Verfahren
A-posteriori-Methoden als nicht-reduktive Verfahren

Reduktive Entscheidungsmodelle

Lexikographische Ordnung
Haupt- und Nebenziele
Methode der gewichteten Summen und Produkte
AHP
Fuzzy Decision Making
Goal Programming und Compromise Programming

Fazit

Beurteilung der A-priori-Methoden
Beurteilung der A-posteriori-Methoden

Optimierung von Angebotsnetzen im EVCM

Extended Value Chain Management

Phasenmodell
Prozessvariantenplan und Prozessplan
Angebotsnetze
Problemstellung bei der Kompetenzzellenauswahl

Formalisierung des Problems

Problemgraph
Restriktionssystem
Lösungskonstruktion und Problemstellung

Zielsetzungen der Optimierung

Preis
Lieferwahrscheinlichkeit
Liefertermin

Angebote mit unvollständigen Mengen

Ansatz mit impliziter Behandlung von Teilmengen
Ansatz mit Behandlung expliziter Fehlmengen

Problemkomplexität

Dynamic Programming

Theoretische Grundlagen

Einführung
Problemstellung und Lösungsprinzip
Verfahren

Problemspezifische Modellierung

Problemspezifischer Basisalgorithmus
Umgang mit Divergenzen

Komplexitätsbetrachtungen

Ant Colony Optimization

Einführung

Einordnung des Verfahrens
Naturanalogie
ACO-Metaheuristik

Verschiedene Ansätze

Ant System
Ant Colony System

Mehrkriterielle Ameisenalgorithmen

Überblick
Paretooptimierung mit ACO
Gewichtung bei beliebiger Zielanzahl

Problemspezifische Modellierung

Ant Family Heuristic
Lösungskonstruktion
Heuristikwerte für das Angebotsnetz
Konvergenzverhalten und Pheromoninitialisierung

Hybride Methoden und Erweiterungen

Pheromonaktualisierung bei Paretooptimierung

Eigenschaften der bisherigen Strategie
Nadir-Punkt-Strategie

Paretooptimierung mit Auswahl nach Fuzzy Decision Making

Ausgangssituation
Auswahlwahrscheinlichkeiten über Fuzzy Decision Making

Problemreduktion

Dominanz von Teilgraphen
Algorithmisches Konzept

Die Look-Ahead-Heuristic

Ausgangssituation
Konzept der Look-Ahead-Heuristic

Evaluierung

Evaluierung des Parallel Path Problems und des dynamischen Programms

Verwendete Evaluierungsmaße
Abhängigkeiten zwischen Komplexität und Zielkriterien
Abhängigkeiten zwischen Paretofront und Zielfunktionen
Komplexität von Angebotsnetzen
Probleme mit divergenten Prozessplänen

Evaluierung ACO und hybride Ansätze

Verwendete Evaluierungsmaße
Problemlösungsverhalten der Ameisenalgorithmen
Verwendung von Routingtabellen und Tabulisten
Aktualisierungsstrategien
Analyse verschiedener Aggregationsmethoden
Standard-Heuristik und Look-Ahead-Heuristic
Problemreduktion

Fazit und Ausblick
Ergänzungen und Detailinformationen zur Evaluierung

Evaluierte Problemgraphen und Prozesspläne
Verwendete Konfigurationen und Parameter von ACO

Beispielrechnung

Häufig gestellte Fragen

Was ist das Ziel der Optimierung im Extended Value Chain Management (EVCM)?

Ziel ist die optimale Auswahl von Partnern (Kompetenzzellen) in einem Produktionsnetzwerk unter Berücksichtigung mehrerer Ziele wie Preis, Lieferzeit und Lieferwahrscheinlichkeit.

Was versteht man unter Pareto-Optimierung?

Eine Lösung ist pareto-optimal, wenn kein Ziel verbessert werden kann, ohne ein anderes Ziel gleichzeitig zu verschlechtern. Das Ergebnis ist eine Menge von optimalen Kompromisslösungen.

Wie funktioniert die Ant Colony Optimization (ACO)?

ACO ist eine Metaheuristik, die das Verhalten von Ameisen bei der Futtersuche imitiert. Künstliche Ameisen hinterlassen „Pheromonspuren“ auf guten Wegen, um anderen den Weg zu einer optimalen Lösung zu weisen.

Was sind hybride Methoden in diesem Kontext?

Hybride Methoden kombinieren verschiedene Ansätze, wie zum Beispiel Dynamic Programming mit ACO, um die Vorteile beider Verfahren (Exaktheit und Schnelligkeit) zu vereinen.

Warum ist das Kürzeste-Wege-Problem hier relevant?

Die Auswahl der optimalen Partnerkette in einem Produktionsnetzwerk lässt sich mathematisch als ein mehrkriterielles Kürzeste-Wege-Problem in einem gerichteten Graphen modellieren.

Ende der Leseprobe aus 197 Seiten - nach oben

Details

Titel: Hybride Ansätze zur Optimierung Kürzester-Wege-Probleme in gerichteten Graphen
Untertitel: Angebotsnetze im Extended Value Chain Management
Hochschule: Technische Universität Chemnitz
Note: 1,0
Autor: Dipl.-Wirt.-Inf. Sascha Häckel (Autor:in)
Erscheinungsjahr: 2006
Seiten: 197
Katalognummer: V90934
ISBN (eBook): 9783638051712
Dateigröße: 10885 KB
Sprache: Deutsch
Anmerkungen: Die Arbeit wurde mit dem Universitätspreis 2007 der Fakultät für Wirtschaftswissenschaften der Technischen Universität Chemnitz ausgezeichnet. Abweichend zur eingereichten Originalfassung wurde die Titelseite geändert, einige Orthographiefehler behoben sowie Teile des Anhangs gekürzt.
Schlagworte: Hybride Ansätze Dynamic Programming Colony Optimization Optimierung Kürzester-Wege-Probleme Graphen Beispiel Angebotsnetzen Extended Value Chain Management
Produktsicherheit: GRIN Publishing GmbH
Preis (Ebook): US$ 42,99

Arbeit zitieren: Dipl.-Wirt.-Inf. Sascha Häckel (Autor:in), 2006, Hybride Ansätze zur Optimierung Kürzester-Wege-Probleme in gerichteten Graphen, München, Page::Imprint:: GRINVerlagOHG, https://www.diplomarbeiten24.de/document/90934