Zusammenfassung / Abstract
Das Briefträgerproblem wurde 1962 erstmals von dem chinesischen Mathematiker Mei-Ko Kwan formuliert und ist dem Bereich kombinatorischer Optimierungsprobleme zuzuordnen.
Der Briefträger muß in einem bestimmten Gebiet die Post für nahezu alle Haushalte verteilen. Um dies zu erreichen müssen alle Straßen oder Wege innerhalb seines Gebietes mindestens einmal durchlaufen werden. Start- und Endpunkt der Tour ist das Postamt. Gesucht ist eine Rundreise auf der jede Straße oder jeder Weg genau einmal durchlaufen wird, da dies eine kostenminimale Tour darstellt. Eine solche Tour ist aber nicht immer gegeben. In einem solchen Fall muß der Briefträger bereits abgearbeitete Teilstrecken erneut durchlaufen.
Die Optimierungsaufgabe besteht darin, die Kosten dieser unproduktiven Teilstrecken zu minimieren. In bezug auf das zugrundeliegende Straßen- bzw. Wegenetz ergibt sich eine Dreiteilung des Briefträgerproblems. Es können zum Beispiel nur Straßen oder Wege vorliegen die frei in beide Richtungen passierbar sind. Ebenfalls können auch nur Einbahnstraßen vorhanden sein, oder es kann ein Mix aus beiden gegeben sein. Die ersten beiden Varianten sind gut mit exakten Algorithmen aus dem Bereich der Graphentheorie zu lösen. Bei einem Mix aus frei passierbaren Straßen und Einbahnstraßen stoßen diese Verfahren jedoch an ihre Grenzen. Für die Lösung dieser Problemausprägung sind sogenannte Meta-Heuristiken gut geeignet. Diese Methoden können selbstverständlich auch auf die beiden zuerst genannten Problemformulierungen anwendet werden.
Sowohl Lösungsansätze unter Verwendung von Meta-Heuristiken als auch durch Zuhilfenahme klassischer Methoden der Graphentheorie werden in dieser Arbeit vorgestellt.
Schlüsselwörter
Briefträgerproblem, optimale Briefträgertour, Eulerscher Graph, Meta-Heuristiken, A* - Algorithmus.
Inhaltsverzeichnis
1. Das Briefträgerproblem als Optimierungsaufgabe
2. Klassische Konstruktionsverfahren
2.1 Optimierung einer Briefträgertour in Graphen
2.2 Optimierung einer Briefträgertour in Digraphen
2.3 Das Briefträgerproblem in gemischten Multigraphen
3. Lösungsmöglichkeiten mittels heuristischer Algorithmen
3.1 Anwendungsmöglichkeiten von Meta-Heuristiken
3.2 Anwendung des A* - Algorithmus
4. Abschließende Bemerkungen
Zielsetzung und Themenfelder
Das Hauptziel dieser Arbeit besteht in der Untersuchung verschiedener Verfahren zur Lösung des Briefträgerproblems, um kostenoptimale Routen in unterschiedlichen Graphenstrukturen zu finden. Dabei wird analysiert, wie klassische graphentheoretische Konstruktionsverfahren und moderne Meta-Heuristiken zur Minimierung unproduktiver Teilstrecken eingesetzt werden können.
- Grundlagen des Briefträgerproblems und dessen historische Entwicklung
- Klassische Lösungsansätze in Graphen, Digraphen und gemischten Multigraphen
- Einsatz von Meta-Heuristiken wie Tabu Search, Simulated Annealing und Genetischen Algorithmen
- Demonstration des A*-Algorithmus als Bestensuchverfahren für komplexe Tourenoptimierungen
- Transformation des kantenorientierten Problems in ein knotenorientiertes Traveling Salesman Problem (TSP)
Auszug aus dem Buch
2.1 Optimierung einer Briefträgertour in Graphen
Zunächst müssen einige wesentliche Annahmen an den Graphen gestellt werden. Der Graph muß mindestens aus einer Kante und somit aus zwei Knoten bestehen. Des weiteren ist G zusammenhängend, d.h. alle Knoten von G sind direkt oder indirekt über eine Kantenfolge miteinander verbunden. Eine Briefträgertour ist im folgenden eine geschlossene Kantenfolge, die jede in G enthaltene Kante mindestens einmal enthält. Bezüglich der Bewertung der Kanten ist anzumerken, das cij nicht negativ sein darf. Würden negativ bewertete Kanten existieren, so könnten diese beliebig oft durchlaufen werden ohne Kosten zu verursachen bzw. die auf den positiv bewerteten Kanten entstandenen Kosten reduzieren.
Hilfreich für die Konstruktion einer optimalen Briefträgertour in G ist der Zusammenhang zwischen einer Briefträgertour und einer geschlossenen Eulerschen Linie. Eine geschlossene Eulersche Linie in G ist eine geschlossene Kantenfolge, die jede Kante von G genau einmal enthält. Wenn ein solcher Weg in G existiert, wird G auch Eulerscher Graph genannt. Der schweizer Mathematiker und Physiker Leonard Euler (1707 – 1783) legte, so wird gesagt, bereits 1736 mit dem Königsberger Brückenproblem den Grundstein der Graphentheorie. Bei diesem Problem wird ein Weg über die sieben Brücken des Flusses Pregel gesucht wobei Start- und Endpunkt der Route identisch sein sollen und jede Brücke nur einmal passiert werden soll. Ein solcher Weg existiert jedoch für dieses spezielle Problem nicht.
Ein Weg, der jede Kante von G genau einmal enthält und zudem geschlossen ist, existiert genau dann, wenn der Grad eines jeden Knotens i eines Graphen gerade ist. Ein Eulerscher Graph liegt somit genau dann vor, wenn G zusammenhängend ist und sämtliche Knoten in G einen geraden Grad aufweisen.
Zusammenfassung der Kapitel
1. Das Briefträgerproblem als Optimierungsaufgabe: Einführung in die Problemstellung des Briefträgerproblems und dessen Bedeutung für die Tourenplanung.
2. Klassische Konstruktionsverfahren: Erläuterung der graphentheoretischen Grundlagen zur Optimierung in verschiedenen Graphentypen.
2.1 Optimierung einer Briefträgertour in Graphen: Detaillierte Darstellung des Algorithmus zur Lösung in ungerichteten Graphen mittels Eulerscher Linien und Matchings.
2.2 Optimierung einer Briefträgertour in Digraphen: Beschreibung der Lösungswege für gerichtete Graphen unter Rückgriff auf klassische Transportprobleme.
2.3 Das Briefträgerproblem in gemischten Multigraphen: Diskussion der Komplexität und der exakten Lösbarkeit bei gemischten Netzstrukturen.
3. Lösungsmöglichkeiten mittels heuristischer Algorithmen: Einführung in heuristische Ansätze zur effizienten Bewältigung komplexer Optimierungsprobleme.
3.1 Anwendungsmöglichkeiten von Meta-Heuristiken: Vorstellung von Strategien wie Tabu Search, Simulated Annealing und Genetischen Algorithmen zur Lösungsverbesserung.
3.2 Anwendung des A* - Algorithmus: Analyse des A*-Algorithmus als spezialisiertes Bestensuchverfahren für Briefträgertouren.
4. Abschließende Bemerkungen: Zusammenfassender Ausblick auf verwandte Routing-Probleme und die Praxisrelevanz der vorgestellten Methoden.
Schlüsselwörter
Briefträgerproblem, Chinese Postman Problem, Graphentheorie, Optimierung, Eulerscher Graph, Meta-Heuristiken, Tabu Search, Simulated Annealing, Genetische Algorithmen, A*-Algorithmus, Traveling Salesman Problem, Tourenplanung, Kombinatorische Optimierung.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit dem sogenannten Briefträgerproblem, bei dem eine kostenminimale Rundreise in einem definierten Wegenetz gesucht wird, um alle Kanten mindestens einmal zu durchlaufen.
Was sind die zentralen Themenfelder?
Die zentralen Felder umfassen die Graphentheorie, klassische mathematische Optimierungsverfahren für verschiedene Graphentypen sowie moderne heuristische Strategien zur Problemlösung.
Was ist das primäre Ziel der Untersuchung?
Das primäre Ziel ist es, Methoden aufzuzeigen, mit denen die Kosten für unproduktive Strecken bei der Postverteilung minimiert werden können.
Welche wissenschaftliche Methode wird verwendet?
Es wird ein kombinierter Ansatz verfolgt: Zum einen klassische Verfahren der Graphentheorie (z.B. Eulersche Vergrößerungen) und zum anderen Meta-Heuristiken wie Tabu Search oder Genetische Algorithmen.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die mathematische Modellierung mittels Graphen und Digraphen sowie die Anwendung intelligenter Suchalgorithmen zur Findung optimaler Touren.
Welche Schlüsselwörter charakterisieren die Arbeit?
Zu den wichtigsten Begriffen gehören Briefträgerproblem, Eulerscher Graph, Meta-Heuristiken, A*-Algorithmus und die Transformation in ein Traveling Salesman Problem.
Warum wird eine Transformation in ein Traveling Salesman Problem (TSP) diskutiert?
Die Transformation ermöglicht es, knotenorientierte Algorithmen zu nutzen, da das kantenorientierte Briefträgerproblem bei der Definition von Nachbarschaftsstrukturen für Meta-Heuristiken ohne diese Anpassung schwierig handhabbar ist.
Welchen Vorteil bietet der A*-Algorithmus gegenüber Meta-Heuristiken?
Der A*-Algorithmus ist ein exaktes Verfahren, das direkt auf Ausgangsgraphen anwendbar ist, ohne dass eine vorherige Transformation des Graphen oder eine zulässige Startlösung zwingend erforderlich sind.
- Quote paper
- Lars Laboch (Author), 2003, Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche, Munich, GRIN Verlag, https://www.grin.com/document/22155
