Tourenplanung durch Einsatz naturanaloger Verfahren

Frontmatter

Kapitel 1. Einleitung

Zusammenfassung

Gemäß der normativen Entscheidungstheorie¹ werden betriebswirtschaftliche Entscheidungsprobleme durch die dem Entscheidungsträger offenstehenden Handlungsalternativen, die im Entscheidungskontext relevanten Umweltzustände sowie eine oder mehrere, die Präferenzen des Entscheidungsträgers repräsentierende(n) Zielfunktion(en) spezifiziert.

Oliver Wendt

Kapitel 2. Typologie der Tourenplanungsprobleme und ihrer Lösungsverfahren

Zusammenfassung

Nahezu alle Tourenplanungsprobleme stellen Generalisierungen oder Spezialisierungen des Traveling-Salesman-Problems dar. Daher wird dieses zunächst in seiner Grundversion diskutiert, bevor im Anschluß Erweiterungen zur Sprache kommen.

Oliver Wendt

Kapitel 3. Systematik klassischer Problemlösungsverfahren

Zusammenfassung

Kapitel 2 handelte bereits von Optimierungsverfahren und Heuristiken zur Lösung des TSP. Dabei wurde beim Leser ein intuitives Verständnis des Begriffes ‚Heuristik‘ vorausgesetzt, im Sinne von Algorithmen⁶⁶, die keine optimale Lösung des Problems garantieren können, dieser aber trotzdem mehr oder weniger gut nahe kommen. Das Ziel dieses Kapitels besteht darin, dieser Klassifikation von Problemlösungsverfahren eine weitere, für die Zwecke dieser Arbeit fruchtbarere, gegenüberzustellen.

Oliver Wendt

Kapitel 4. Genetische Algorithmen (GA)

Zusammenfassung

Adaptive Systeme sind gekennzeichnet durch einen Zustandsraum, Operatoren über diesem Zustandsraum, Inputs des Systems aus seiner Umwelt und ein Anpassungsverfahren [Holland 75, S. 28].

Oliver Wendt

5. Simulated Annealing (SA)

Zusammenfassung

Als ein weiteres, in Analogie zur (hier unbelebten) Natur gestaltetes Verfahren zur Lösung kombinatorischer Optimierungsprobleme soll im folgenden das sogenannte Simulated Annealing¹⁷⁵ betrachtet werden. Ebenso wie die genetischen Algorithmen zählt auch das Simulated Annealing zu den relativ rechenintensiven Verfahren, deren Einsatz erst mit der Verfügbarkeit leistungsfähiger Hardware möglich wurde.

Oliver Wendt

Kapitel 6. Sonstige naturanaloge Verfahren

Zusammenfassung

Nahezu zeitgleich zu den durch Holland im Laufe der sechziger Jahre entwickelten GA wurden unabhängig davon in Deutschland unter der Bezeichnung „Evolutionsstrategien“ von Rechenberg [Rechenberg 73] analoge Phänomene untersucht.

Oliver Wendt

Kapitel 7. Kombination von genetischen Algorithmen und Simulated Annealing

Zusammenfassung

Nachdem in den Kapiteln 4, 5 und 6 die grundlegenden Wirkungsprinzipien von GA und SA und anderen naturanalogen Verfahren ausführlich diskutiert wurden, ist das Ziel dieses Kapitels, für beide Konzepte Gemeinsamkeiten und Unterschiede deutlich herauszuarbeiten, um sie anschließend als Spezialisierungen eines einheitlichen ‚Meta-Verfahrens‘ auffassen zu können.

Oliver Wendt

Kapitel 8. Lösung von CVRP mittels naturanaloger Verfahren

Zusammenfassung

Um allgemeinere Tourenplanungsprobleme wie das Capacitated Vehicle Routing Problem (CVRP) für genetische Algorithmen zugänglich zu machen, stellen sich abermals alle im Rahmen des TSP beantworteten Fragen zu Problemrepräsentation, Mutations- und Crossover- Operatoren.

Oliver Wendt

Kapitel 9. Zusammenfassung und Ausblick

Zusammenfassung

In diesem abschließenden Kapitel werden die oben diskutierten Verfahren einem zusammenfassenden Kosten-/Nutzen-Vergleich unterzogen. Im Anschluß daran erfolgt eine thesenförmige Darstellung der in dieser Arbeit gewonnenen Erkenntnisse, bevor schließlich offene Fragestellungen angeschnitten werden.

Oliver Wendt

Backmatter