Kompetitive Routenplanung bei ausfallenden Kanten

Das Ausgangsproblem ist auch als Canadian Traveller Problem bekannt, da man es sich wie folgt veranschaulichen kann. Ein kanadischer Reisender möchte mit dem Auto von seiner jetzigen Position s aus zu einer bestimmten Zielposition t fahren. Dabei möchte er eine möglichst kurze Strecke zurücklegen. Die prinzipiell zur 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 der Regel nicht aus, einfach den kürzesten Weg von s nach t zu berechnen. Denn Straßen können durch starken Schneefall unpassierbar werden. Ob auf diese Weise eine Kante in dem Graphen ausgefallen ist, erfährt der Reisende erst, wenn er an einem zu ihr inzidenten Knoten steht. Das Ziel des Reisenden ist es nun vereinfacht gesagt, so zu fahren, dass er höchstens um eine feste Konstante c länger fährt, als es nötig gewesen wäre. Das heißt, die zurückgelegte Strecke soll höchstens c mal so lang sein wie der kürzeste Weg von s nach t in dem um die ausgefallenen Kanten reduzierten Graphen. Was für Faktoren sind für bestimmte Graphklassen erreichbar? Welche Strategien sind optimal?

Sebastian Jacobi, Diplom-Informatiker, Uni Bonn. Seit 1.2.2008 Berater im Bereich Identity & Access Management bei Siemens Enterprise Communications in Essen.