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
- Das Briefträgerproblem als Optimierungsaufgabe.
- Klassische Konstruktionsverfahren
- Optimierung einer Briefträgertour in Graphen......
- 2.1 Optimierung einer Briefträgertour in Digraphen.......
- 2.2 Das Briefträgerproblem in gemischten Multigraphen.........
- Lösungsmöglichkeiten mittels heuristischer Algorithmen..........\n
- 3.1 Anwendungsmöglichkeiten von Meta-Heuristiken..\n
- 3.2 Anwendung des A* - Algorithmus
- Abschließende Bemerkungen
Zielsetzung und Themenschwerpunkte
Die Arbeit befasst sich mit dem Briefträgerproblem, einer Optimierungsaufgabe, bei der es darum geht, eine effiziente Tour für einen Briefträger zu finden, um alle zu beliefernden Adressen zu erreichen.
- Klassische Konstruktionsverfahren zur Lösung des Briefträgerproblems
- Anwendung von heuristischen Algorithmen zur Optimierung von Briefträgertouren
- Einsatz von Meta-Heuristiken und des A*-Algorithmus zur Verbesserung der Tour-Planung
- Die Darstellung des Briefträgerproblems in verschiedenen Graphenmodellen
- Abschließende Reflexion über die Effizienz und Komplexität der verschiedenen Lösungsansätze
Zusammenfassung der Kapitel
- Kapitel 1: Das Briefträgerproblem wird als Optimierungsaufgabe vorgestellt und klassische Konstruktionsverfahren zur Lösung des Problems werden erläutert.
- Kapitel 2: Das Optimieren einer Briefträgertour in Graphen wird anhand verschiedener Modelle, darunter gerichtete und ungerichtete Graphen, sowie gemischte Multigraphen, behandelt.
- Kapitel 3: Es werden Lösungsansätze mittels heuristischer Algorithmen, insbesondere Meta-Heuristiken und der A*-Algorithmus, vorgestellt, um die Optimierung von Briefträgertouren zu verbessern.
Schlüsselwörter
Briefträgerproblem, Optimierung, Graphen, Algorithmen, Heuristik, Meta-Heuristik, A*-Algorithmus, Tourplanung, Kostenminimierung, effiziente Routenplanung
- Quote paper
- Lars Laboch (Author), 2003, Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche, Munich, GRIN Verlag, https://www.grin.com/document/22155
