Hausarbeiten logo
Shop
Shop
Tutorials
En De
Shop
Tutorials
  • How to find your topic
  • How to research effectively
  • How to structure an academic paper
  • How to cite correctly
  • How to format in Word
Trends
FAQ
Go to shop › Business economics - Operations Research

Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche

Title: Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche

Seminar Paper , 2003 , 64 Pages , Grade: 1,7

Autor:in: Lars Laboch (Author)

Business economics - Operations Research

Excerpt & Details   Look inside the ebook
Summary Excerpt Details

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.

Excerpt


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

Excerpt out of 64 pages  - scroll top

Details

Title
Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche
College
University of Hagen  (FB WiWi, insbes. Operations Research)
Course
Seminar: Intelligente Strategien in Theorie und Praxis, 29/30 Jan. 2004 in Hagen
Grade
1,7
Author
Lars Laboch (Author)
Publication Year
2003
Pages
64
Catalog Number
V22155
ISBN (eBook)
9783638255752
ISBN (Book)
9783640865208
Language
German
Tags
Briefträgerproblem Konstruktionsverfahren Nachbarschaftssuche Seminar Intelligente Strategien Theorie Praxis Hagen
Product Safety
GRIN Publishing GmbH
Quote paper
Lars Laboch (Author), 2003, Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/22155
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • https://cdn.openpublishing.com/images/brand/2/preview_popup_advertising.jpg
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  64  pages
Hausarbeiten logo
  • Facebook
  • Instagram
  • TikTok
  • Shop
  • Tutorials
  • FAQ
  • Payment & Shipping
  • About us
  • Contact
  • Privacy
  • Terms
  • Imprint