Kompetitive Routenplanung bei ausfallenden Kanten : Canadian Traveller Problem

ISBN-13: 9783639004632 / Niemiecki / Miękka / 2008 / 164 str.

Sebastian Jacobi; Manuel Wedemeier

Opis

Das Ausgangsproblem ist auch als Canadian Traveller Problembekannt, da man es sich wie folgt veranschaulichen kann. Einkanadischer Reisender möchte mit dem Auto von seiner jetzigenPosition s aus zu einer bestimmten Zielposition t fahren. Dabeimöchte er eine möglichst kurze Strecke zurücklegen. Die prinzipiellzur Verfügung stehenden Straßen (Kanten) und deren Kreuzungen(Knoten) bilden einen mit den Streckenlängen gewichteten Graphen,der dem Reisenden bekannt ist. Es reicht aber im Winter in derRegel nicht aus, einfach den kürzesten Weg von s nach t zuberechnen. Denn Straßen können durch starken Schneefallunpassierbar werden. Ob auf diese Weise eine Kante in dem Graphenausgefallen ist, erfährt der Reisende erst, wenn er an einem zu ihrinzidenten Knoten steht. Das Ziel des Reisenden ist es nunvereinfacht gesagt, so zu fahren, dass er höchstens um eine festeKonstante c länger fährt, als es nötig gewesen wäre. Das heißt, diezurückgelegte Strecke soll höchstens c mal so lang sein wie derkürzeste Weg von s nach t in dem um die ausgefallenen Kantenreduzierten Graphen. Was für Faktoren sind für bestimmteGraphklassen erreichbar? Welche Strategien sind optimal?

O autorze

Jacobi, Sebastian Sebastian Jacobi, Diplom-Informatiker, Uni Bonn. Seit 1.2.2008 Berater im Bereich Identity & Access Management bei Siemens Enterprise Communications in Essen. Wedemeier, Manuel Manuel Wedemeier, Diplom-Informatiker, Uni Bonn. Seit 1.2.2008 Consultant SAP for Insurance (FS-CD) bei der ConVista in Köln.