Sie sind hier
E-Book

Schnelle Algorithmen für ressourcenbeschränkte kürzeste Wege in Verkehrsnetzen

AutorFabian Zenzinger
VerlagGRIN Verlag
Erscheinungsjahr2004
Seitenanzahl85 Seiten
ISBN9783638247320
FormatePUB/PDF
Kopierschutzkein Kopierschutz/DRM
GerätePC/MAC/eReader/Tablet
Preis10,99 EUR
Diplomarbeit aus dem Jahr 2002 im Fachbereich Mathematik - Angewandte Mathematik, Note: 1,3, Technische Universität Berlin (Fachbereich Mathematik), Sprache: Deutsch, Abstract: Die Anzahl registrierter Autos hat in vielen Industrienationen inzwischen einen kritischen Stand erreicht. Da sie allem Anschein nach weiter wachsen wird, die Infrastruktur jedoch nicht mehr beliebig ausbaubar ist, droht aufgrund der daraus folgenden Verkehrsdichte schon bald ein rapides Zunehmen an Staus. Um dies zu vermeiden, versuchen einige Automobilhersteller seit einiger Zeit, sogenannte Navigationssysteme für ihre Wagen zu entwickeln, mit denen die Verkehrsteilnehmer möglichst schnell durch den Verkehr geleitet werden sollen. Der nächstliegende Ansatz bestand zuerst darin, für jeden Teilnehmer den schnellsten Weg von seinem Start- zu seinem Zielort zu berechnen. Dies lässt sich mathematisch durch das sogenannte Kürzeste-Wege-Problem mit nicht-negativen Kantengewichten modellieren, welches in polynomialer Zeit lösbar ist. Wie sich jedoch schon bald herausstellte, sind in der Praxis weitere Komponenten zu berücksichtigen, die die Berechnung eines für jeden Fahrer akzeptablen Weges erschweren. So wäre es zum Beispiel denkbar, bei der Berechnung des schnellsten Weges zu fordern, dass der Fahrer keinen allzu grossen Umweg zu nehmen hat. Ein solcher ressourcenbeschränkter kürzester Weg lässt sich leider nicht in polynomialer Zeit ermitteln, da es sich dabei um ein sogenanntes schwach NP-vollständiges Problem handelt. Ziel der vorliegenden Arbeit ist es, Algorithmen zu entwickeln, die dieses Problem möglichst schnell lösen, und zu untersuchen, welche am besten für den Einsatz in einem solchen Route-Guidance-System geeignet sind. Zu diesem Zweck wird der für das klassische Kürzeste-Wege-Problem häufig benutzte Di jkstra-Algorithmus an die neue Problemstellung angepasst und in mehreren Varianten mit unterschiedlichen Beschleunigungsmethoden implementiert. Diese werden dann auf verschiedenen Beispielinstanzen sowohl untereinander als auch im Vergleich mit für andere Projekte verwendeten Lösungsverfahren getestet. Anhand der daraus folgenden Ergebnisse werden dann noch einmal zusammenfassend die Vorz¨uge und Nachteile der jeweiligen Ansätze diskutiert, bevor wir abschließend vorschlagen, welches Verfahren für den Gebrauch als Unterproblem in einem an der TU Berlin entwickeltes Navigationssystem vorzuziehen ist. [...]

Kaufen Sie hier:

Horizontale Tabs

Blick ins Buch

Weitere E-Books zum Thema: Mathematik - Algorithmik - Arithmetik

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Gewöhnliche Differenzialgleichungen

E-Book Gewöhnliche Differenzialgleichungen
Differenzialgleichungen in Theorie und Praxis Format: PDF

Im Anschluss an Vorlesungen in Analysis und Linearer Algebra folgen an nahezu allen technischen und wirtschaftswissenschaftlich orientierten Studiengängen an Hochschulen und Universitäten als eine…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Weitere Zeitschriften

FESTIVAL Christmas

FESTIVAL Christmas

Fachzeitschriften für Weihnachtsartikel, Geschenke, Floristik, Papeterie und vieles mehr! FESTIVAL Christmas: Die erste und einzige internationale Weihnachts-Fachzeitschrift seit 1994 auf dem ...

Archiv und Wirtschaft

Archiv und Wirtschaft

"Archiv und Wirtschaft" ist die viermal jährlich erscheinende Verbandszeitschrift der Vereinigung der Wirtschaftsarchivarinnen und Wirtschaftsarchivare e. V. (VdW), in der seit 1967 rund 2.500 ...

Berufsstart Bewerbung

Berufsstart Bewerbung

»Berufsstart Bewerbung« erscheint jährlich zum Wintersemester im November mit einer Auflage von 50.000 Exemplaren und ermöglicht Unternehmen sich bei Studenten und Absolventen mit einer ...

cards Karten cartes

cards Karten cartes

Die führende Zeitschrift für Zahlungsverkehr und Payments – international und branchenübergreifend, erscheint seit 1990 monatlich (viermal als Fachmagazin, achtmal als ...

Das Grundeigentum

Das Grundeigentum

Das Grundeigentum - Zeitschrift für die gesamte Grundstücks-, Haus- und Wohnungswirtschaft. Für jeden, der sich gründlich und aktuell informieren will. Zu allen Fragen rund um die Immobilie. Mit ...

Gastronomie Report

Gastronomie Report

News & Infos für die Gastronomie: Tipps, Trends und Ideen, Produkte aus aller Welt, Innovative Konzepte, Küchentechnik der Zukunft, Service mit Zusatznutzen und vieles mehr. Frech, offensiv, ...

dima

dima

Bau und Einsatz von Werkzeugmaschinen für spangebende und spanlose sowie abtragende und umformende Fertigungsverfahren. dima - die maschine - bietet als Fachzeitschrift die Kommunikationsplattform ...

IT-BUSINESS

IT-BUSINESS

IT-BUSINESS ist seit mehr als 25 Jahren die Fachzeitschrift für den IT-Markt Sie liefert 2-wöchentlich fundiert recherchierte Themen, praxisbezogene Fallstudien, aktuelle Hintergrundberichte aus ...