Das Brieftragerproblem

Studienarbeit aus dem Jahr 2003 im Fachbereich BWL - Unternehmensforschung, Operations Research, Note: 1,7, FernUniversitt 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 Brieftrgerproblem wurde 1962 erstmals von dem chinesischen Mathematiker Mei-Ko Kwan formuliert und ist dem Bereich kombinatorischer Optimierungsprobleme zuzuordnen.

Der Brieftrger mu in einem bestimmten Gebiet die Post fr nahezu alle Haushalte verteilen. Um dies zu erreichen mssen alle Straen oder Wege innerhalb seines Gebietes mindestens einmal durchlaufen werden. Start- und Endpunkt der Tour ist das Postamt. Gesucht ist eine Rundreise auf der jede Strae 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 Brieftrger bereits abgearbeitete Teilstrecken erneut durchlaufen.

Die Optimierungsaufgabe besteht darin, die Kosten dieser unproduktiven Teilstrecken zu minimieren. In bezug auf das zugrundeliegende Straen- bzw. Wegenetz ergibt sich eine Dreiteilung des Brieftrgerproblems. Es knnen zum Beispiel nur Straen oder Wege vorliegen die frei in beide Richtungen passierbar sind. Ebenfalls knnen auch nur Einbahnstraen 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 lsen. Bei einem Mix aus frei passierbaren Straen und Einbahnstraen stoen diese Verfahren jedoch an ihre Grenzen. Fr die Lsung dieser Problemausprgung sind sogenannte Meta-Heuristiken gut geeignet. Diese Methoden knnen selbstverstndlich auch auf die beiden zuerst genannten Problemformulierungen anwendet werden.

Sowohl Lsungsanstze unter Verwendung von Meta-Heuristiken als auch durch Zuhilfenahme klassischer Methoden der Graphentheorie werde