VDM Jacobi, S: 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 Strassen (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 Strassen 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 heisst, 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?