Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche
-
- Taschenbuch ausgewählt
- eBook
-
Sprache:Deutsch
Fr. 58.90
inkl. gesetzl. MwSt.,
Beschreibung
Produktdetails
Einband
Taschenbuch
Erscheinungsdatum
15.03.2011
Verlag
GRINSeitenzahl
68
Maße (L/B/H)
21/14.8/0.6 cm
Gewicht
112 g
Auflage
2. Auflage
Sprache
Deutsch
ISBN
978-3-640-86520-8
Studienarbeit aus dem Jahr 2003 im Fachbereich BWL - Unternehmensforschung, Operations Research, Note: 1,7, FernUniversität Hagen (FB WiWi, insbes. Operations Research), Veranstaltung: Seminar: Intelligente Strategien in Theorie und Praxis, 29/30 Jan. 2004 in Hagen, Sprache: Deutsch, Abstract: 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 muss in einem bestimmten Gebiet die Post für nahezu alle Haushalte verteilen. Um dies zu erreichen müssen alle Strassen oder Wege innerhalb seines Gebietes mindestens einmal durchlaufen werden. Start- und Endpunkt der Tour ist das Postamt. Gesucht ist eine Rundreise auf der jede Strasse 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 muss der Briefträger bereits abgearbeitete Teilstrecken erneut durchlaufen. Die Optimierungsaufgabe besteht darin, die Kosten dieser unproduktiven Teilstrecken zu minimieren. In bezug auf das zugrundeliegende Strassen- bzw. Wegenetz ergibt sich eine Dreiteilung des Briefträgerproblems. Es können zum Beispiel nur Strassen oder Wege vorliegen die frei in beide Richtungen passierbar sind. Ebenfalls können auch nur Einbahnstrassen 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 Strassen und Einbahnstrassen stossen 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.
Kundinnen und Kunden meinen
Verfassen Sie die erste Bewertung zu diesem Artikel
Helfen Sie anderen Kund*innen durch Ihre Meinung