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

Inhaltsverzeichnis

Vorwort

1 Einleitung
1.1 Anwendungsgebiete
1.2 Das CMCF Route-Guidance-Projekt an der TU Berlin
1.3 Das CNOP-Paket
1.4 Anforderungen an die Problemlösungen

2 Beschleunigungsmethoden für das Kürzeste-Wege-Problem mit nicht- negativen Kantengewichten
2.1 Problemstellung
2.2 Der Dijkstra-Algorithmus
2.2.1 Formulierung
2.2.2 Korrektheit und Laufzeit
2.3 Beschleunigungsmethoden für den Dijkstra-Ansatz
2.3.1 Der zielgerichtete Ansatz
2.3.2 Der bidirektionale Ansatz
2.3.3 Verbindung des zielgerichteten und des bidirektionalen Ansatzes

3 Ressourcenbeschränkte Wege
3.1 Problemstellung
3.1.1 Das ressourcenbeschränkte Kürzeste-Wege-Problem . . .
3.1.2 Pareto-optimale ressourcenbeschränkte Wege
3.1.3 Das doppelt beschränkte Problem
3.1.4 Beziehung zwischen den drei betrachteten Problemen . . .
3.2 Grundlegende Eigenschaften des ressourcenbeschränkten Kürzeste-Wege-Problems
3.2.1 Komplexität
3.2.2 Bisherige Ansätze
3.3 Der erweiterte Dijkstra-Algorithmus
3.3.1 Die Grundversion
3.3.2 Die zielgerichtete Version
3.3.3 Die bidirektionale Version
3.3.4 Die bidirektional zielgerichtete Version
3.3.5 Versionen mit zusätzlichem Abbbruchkriterium
3.4 Weitere Lösungsmethoden
3.4.1 Der Labeling-Ansatz im CMCF-Projekt
3.4.2 Die 2-Phasen-Methode im CNOP-Paket
3.5 ÜberblicküberdievorgestelltenAlgorithmen

4 Implementation und Geschwindigkeitsvergleiche
4.1 Angaben zur Implementation
4.1.1 Verwendete Datenstrukturen
4.1.2 Korrektur von Rechnerungenauigkeiten
4.1.3 Einlesen des Verkehrsnetzwerkes
4.1.4 Besonderheiten beim Aufruf des CMCF-Programms
4.2 Vergleiche
4.2.1 Tests auf LEDA-Graphen
4.2.2 Tests auf Raw-Graphen

5 Zusammenfassung
5.1 Interpretation der Ergebnisse
5.2 Empfehlung für das Route-Guidance-Projekt an der TU Berlin

Liste der Algorithmen

Literaturverzeichnis

Vorwort

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, so- genannte Navigationssysteme für ihre Wagen zu entwickeln, mit denen die Ver- kehrsteilnehmer 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 mathema- tisch durch das sogenannte Kürzeste-Wege-Problem mit nicht-negativen Kanten- gewichten modellieren, welches in polynomialer Zeit lösbar ist. Wie sich jedoch schon bald herausstellte, sind in der Praxis weitere Komponenten zu berücksich- tigen, 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 unterschied- lichen Beschleunigungsmethoden implementiert. Diese werden dann auf verschie- denen Beispielinstanzen sowohl untereinander als auch im Vergleich mit für ande- re Projekte verwendeten Lösungsverfahren getestet. Anhand der daraus folgenden Ergebnisse werden dann noch einmal zusammenfassend die Vorzüge und Nachtei- le der jeweiligen Ansätze diskutiert, bevor wir abschließend vorschlagen, welches Verfahren für den Gebrauch als Unterproblem in einem an der TU Berlin entwickel- tes Navigationssystem vorzuziehen ist.

Um dem Leser die Möglichkeit zu geben, die durch die zusätzliche Ressourcen- beschränkung vorgenommenen Änderungen am Ausgangsalgorithmus nachzuvoll- ziehen, werden in einer Einführung (Kapitel 2) noch einmal das Kürzeste-Wege- Problem sowie der Dijkstra-Algorithmus skizziert. Für ein besseres Verständnis setzt die Arbeit lediglich Grundkenntnisse in Graphentheorie und Optimierung vor- aus.

Ein besonderes Dankeschön geht an Dr. Ekkehard Köhler für die Betreuung während der Erstellung dieser Arbeit, an meine Korrekturleser für das Aufspüren von Fehlern und an die anderen Diplomanden der Arbeitsgruppe für die hilfreichen Ratschläge während der Programmierung der Algorithmen.

Einleitung

Kürzeste-Wege-Probleme entstehen immer dann, wenn Güter oder Daten in Netz- werken so schnell oder so günstig wie nur möglich von einem Punkt zu einem an- deren gelangen sollen. Meistens reicht es aus, die Wege nur bezüglich einer Kom- ponente zu betrachten, sei diese nun Zeitaufwand, Weglänge oder auch entstandene Kosten.

In der Praxis gibt es jedoch auch häufig komplexere Fragenstellungen; hin und wieder werden Wege gesucht, die hinsichtlich mehr als nur einer Komponente ef- fizient sein sollen. Dabei passiert es häufig, dass die daraus resultierenden Ziele im Widerspruch zueinander stehen und deswegen nicht gleichzeitig optimiert werden k önnen. Dies ist insbesondere bei betriebswirtschaftlichen Erwägungen der Fall. Ein Lastwagenfahrer hat zum Beispiel seine Waren so schnell wie möglich zum Zielort zu befördern, muss bei seiner Routenwahl aber auch darauf achten, dass er nicht zuviel Maut und Benzin zu zahlen hat. In solchen Fällen muss entschie- den werden, welcher Parameter am wichtigsten ist. Es wird dann eine Komponente optimiert, während alle anderen eine gewisse Schranke nichtüberschreiten dürfen.

In dieser Arbeit wird der Fall betrachtet, in dem es zusätzlich zu den zu minimie- renden Kosten genau eine andere Ressource gibt, die unter einem vorgegebenen Wert bleiben muss. Dieses Kapitel zeigt einige Verwendungsmöglichkeiten aus der Praxis für dieses Problem auf, wobei wir genaueres Augenmerk auf die Projektum- gebungen legen, in denen die hier erstellten Algorithmen getestet werden. Außer- dem wird darauf eingegangen, welche besonderen Eigenschaften die Lösungen des Problems haben müssen.

1.1 Anwendungsgebiete

Die Suche nach einem günstigen Weg bezüglich zweier Komponenten tritt in einer Großzahl von Praxisbeispielen auf. So ergibt sich in Kommunikationsnetzwerken der Fall, dass man sowohl günstig als auch relativ sicher Daten von einem Punkt zu einem anderen senden will. Dieses sogenannte Quality of Service-Problem wird unter anderen von Orda¹⁵ betrachtet. Gerade durch die in den letzten Jahren vorangetriebene Entwicklung des Internets hat diese Fragestellung an Wichtigkeit gewonnen. Insbesondere in IP-basierten Netzwerken gibt es eine Vielzahl an Pa- rametern, die als Nebenbedingung in Frage kommen, so dass IT -Firmen daran interessiert sind, eine Software zu entwickeln, welche für jede Systemumgebung die relevanten Parameter ermittelt und diese dann als Kostenarten für ein Kürzeste- Wege-Problem mit Nebenbedingungübernimmt.

Doch auch in traditionellen Industriebranchen gibt es interessante Einsatzmöglich- keiten. Elimam und Kohler⁶ untersuchen zunächst die optimale Abfolge von Abwasserflüssen einer gleichzeitig von einer industriellen und einer sanitären Or- ganisation benutzten Einrichtung in Kuwait und gehen danach auf das Problem ein, Gebäude möglichst günstig zu bauen unter der Voraussetzung, dass sie den staatli- chen Sicherheitsvorschriften der USA entsprechen. Sie stellen dabei fest, dass sich beide Fragestellungen als ressourcenbeschränkte Kürzeste-Wege-Probleme model- lieren lassen.

Auch Spaltengenerierungsmethoden in der linearen Optimierung benutzen häufig das Kürzeste-Wege-Problem mit Nebenbedingung als Unterproblem. Dieser Fall tritt zum Beispiel im Scheduling-Bereich oder auch bei komplexen Flußproblemen auf. Sowohl Lübbecke und Zimmermann¹³ in ihrer Betrachtung der Umlaufpla- nung im Güterverkehr bei Werks- und Industriebahnen als auch Borndörfer und L öbel⁴ bei ihrer Arbeitüber Terminplanung im Personenverkehr greifen darauf zurück.

Wie man sieht, gibt es eine große Anzahl von Situationen, in denen eine Nebenbedingung zusätzlich zu der zu minimierenden Komponente auftritt.

1.2 Das CMCF Route-Guidance-Projekt an der TU Ber-

Navigationssysteme, die einfach für jeden Wagen den kürzesten Weg von Start- zu Zielort berechnen, haben den fundamentalen Nachteil, dass sie nicht die Aus- wirkungen ihrer eigenen Routenwahl auf das Verkehrsnetz betrachten. Aus die- sem Grund funktioniert ein solches System nur, solange es von einer kleinen Zahl von Fahrern benutzt wird; denn sollte eine zu große Anzahl von Autos denselben schnellen Weg benutzen, so würde auf dieser Straße schon bald ein Stau entste- hen, der diesen Vorteil zunichte machen würde. Wie Beccaria und Bolelli³ vor- schlagen, ist es also ratsam, ein System zu entwickeln, welches die Verkehrsnetz- belastung minimiert, aber gleichzeitig die individuellen Routen für jeden Fahrer erträglich hält. Diese Nebenbedingung ist wichtig, da es sich bei von Navigati- onssystemen errechneten Wegen nur um Vorschläge handelt und sich kaum ein Fahrer freiwillig auf eine für ihn inakzeptable Route einlassen würde, nur weil es der Gesamtheit des Verkehrsflusses nützt. In diesem Projekt wird dies durch eine Längenbeschränkung für jeden berechneten Weg umgesetzt, d.h. jede Route darf nur um eine vorgebene Prozentzahl größer als der bezüglich der Länge optimale Weg sein.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1.1: Einbettung des ressourcenbeschränkten Kürzeste-Wege-Problems in das Hauptproblem beim CMCF-Projekt

Das ressourcenbeschränkte Kürzeste-Wege-Problem wird somit zu einem Teilpro- blem des sogenannten Constrained Multi-Commodity Flow Problems (CMCF), welches während des Programmablaufs wiederholt aufgerufen wird. Genau ge- nommen wird dabei eine Adaptation des sogenannten Frank-Wolfe-Algorithmus angewendet. Das Ausgangsproblem wird linearisiert und daraufhin mit dem Sim- plex-Algorithmus für lineare Optimierungsprobleme bearbeitet. Da dabei exponen- tiell viele Variablen entstehen, werden diese nicht alle gespeichert, sondern bei Be- darf mit der Spaltengenerierungsmethode erzeugt. Wie bereits erwähnt, wird dabei das Kürzeste-Wege-Problem mit Nebenbedingung als Unterproblem aufgerufen.

Als Lösungsansatz wird hier bisher eine mit einigen Beschleunigungsmethoden versehene Erweiterung des Dijkstra-Algorithmus verwendet. Jahn, Möhring und Schulz¹⁰ stellen fest, dass bei der derzeitigen Implementation rund 95% des Gesamtaufwands mit der Ermittlung dieser Wege verbracht werden; ein besserer Algorithmus würde also zu großen Zeitersparnissen führen.

1.3 Das CNOP-Paket

Das Constrained Network Optimization Package wurde an der Universität des Saar- landes in Saarbrücken entwickelt. Es behandelt Optimierungsprobleme in Netz- werken, welche durch die Einführung einer Ressourcenbeschränkung nicht mehr in polynomialer Zeit lösbar sind. Diese werden in einem ersten Schritt durch obere und untere Schranken approximiert, bevor aus demübriggebliebenen Bereich die L ösung ermittelt wird. Es werden hierbei mehrere Problemstellungen betrachtet; neben dem Table Layout Problem, Kurvenapproximationen und der Suche nach ei- nem kostenminimalen aufspannenden Baum mit Nebenbedingung wird auch hier auf ein Routenplanungsmodell eingegangen, welches das ressourcenbeschränkte Kürzeste-Wege-Problem beinhaltet. Das verwendete Modell ist relativ simpel, so dass sich das für diese Arbeit relevante Teilproblem auch autonom ausführen lässt, was den Vergleich mit anderen Implementationen erleichtert.

Ziegelmann ²¹ hat sowohl für die Ermittlung der Schranken als auch für das darauffolgende Suchen der Optimallösung mehrere Algorithmen miteinander ver- glichen und hat schließlich mit seinen besten Ansätzen bei selbst durchgeführten Tests sehr gut abgeschnitten. Es bleibt jedoch die Frage, ob dieses Verfahren gene- rell zu sehr schnellen Resultaten führt oder ob es für gewisse Situationen wie zum Beispiel dem Einsatz als Unterprogramm im CMCF-Projekt ungeeignet ist.

1.4 Anforderungen an die Problemlösungen

Hauptziel der vorliegenden Arbeit ist es letztlich zu untersuchen, ob ein schneller- er Lösungsansatz für das ressourcenbeschränkte Kürzeste-Wege-Problem zu einer spürbaren Reduzierung der Gesamtlaufzeit beim CMCF-Projekt führen kann. Um dies zu ermitteln, vergleichen wir unsere neu erstellten Algorithmen mit den in den letzten beiden Abschnitten vorgestellten Ansätzen. Voraussetzung dafür ist jedoch, dass alle Verfahren genau das gleiche Problem lösen. Deswegen sollten unsere Me- thoden den Anforderungen der vorgestellten Routenplanungssysteme genügen.

Da die Applikation des CNOP-Pakets eher einfach aufgebaut ist, sind für diesen Fall keine zusätzlichen Bedingungen zu beachten. Gesucht wird ein bezüglich einer Kostenkomponente minimaler Weg zwischen zwei Punkten, der hinsichtlich einer anderen Kostenart eine vorgegebene Schranke nichtüberschreitet.

Komplexer sieht es beim CMCF-Problem aus. Hier wird nicht nur der kostenmini- male ressourcenbeschränkte Weg gesucht, sondern es reicht teilweise auch, wenn er für beide Kostenarten unter vorgegebenen Schranken liegt. Ein hinsichtlich einer Komponente optimierter Weg würde zwar diese Bedingung erfüllen, jedoch kann man davon ausgehen, dass dessen Ermittlung mit einem zeitlichen Mehraufwand verbunden sein dürfte.

Zusätzlich zu dieser Anforderung besitzen einige der neu erstellten Algorithmen die Eigenschaft, eine gewisse Anzahl an effektiven Wegen zu ermitteln, wobei die Effektivität darin besteht, dass ein Weg, der hinsichtlich der ersten Komponente etwas schwächer ist, dafür einen günstigeren Wert bezüglich der zweiten Komponente vorzuweisen hat. Dies ist zum Beispiel für Fragestellungen von Interesse, in denen mehrere alternative Wegvorschläge benötigt werden.

Somit ergeben sich drei verschiedene Problemstellungen für diese Arbeit:

Berechnung eines bezüglich einer Kostenkomponente minimalen Weges bei Einhaltung einer oberen Schranke für eine zweite Komponente Berechnung eines Weges, der bezüglich beider Komponenten unterhalb der vorgegebenen Schranken liegt Berechnung mehrerer gleichermaßen effektiver Wege, die allesamt unterhalb einer vorgegebenen Schranke für eine Kostenart liegen Da versucht werden soll, den für das klassische Kürzeste-Wege-Problem mit nichtnegativen Kantengewichten normalerweise benutzten Dijkstra-Algorithmus so zu erweitern, dass diese drei Probleme effizient gelöst werden, gehen wir im folgenden Kapitel zunächst auf grundlegende Eigenschaften des Algorithmus von Dijkstra ein und beschreiben für ihn einige Beschleunigungsmöglichkeiten, bevor wir die zur Erweiterung benötigten Schritte erläutern.

Kapitel 2 Beschleunigungsmethoden für das Kürzeste-Wege-Problem mit nicht-negativen Kantengewichten

Im folgenden Kapitel werden einige für den weiteren Verlauf der Arbeit relevan- te Eigenschaften des Kürzeste-Wege-Problems zusammengetragen. Zusätzlich zur allgemeinen Problemstellung und zum Dijkstra-Algorithmus wird auch auf mögli- che Beschleunigungsmethoden zur Ermittlung der Lösung eingegangen.

2.1 Problemstellung

Ein Verkehrsnetz lässt sich als ein gerichteter Graph modellieren, indem man jede Straße als Kante und jede Kreuzung als Knoten darstellt. Weist man nun jeder Kante einen Kostenwert zu, so entspricht die Suche nach dem günstigsten Weg zwischen zwei Orten der Ermittlung des kürzesten Weges zwischen zwei Knoten auf dem erstellten Graphen.

Sei also ein gerichteter Graph G V E gegeben, und für jede Kante e E exi- stiere ein nicht-negatives Kantengewicht ce. Dann lässt sich das Kürzeste-Wege- Problem von einem gegebenen Knoten s V zu einem gegebenen Knoten t V schreiben als

Abbildung in dieser Leseprobe nicht enthalten

so dass p ein Weg von s nach t ist.

Da wir uns auf den Fall mit nicht-negativen Kantengewichten beschränken, stellen wir nun den Dijkstra-Algorithmus vor, der die Standardmethode zur Lösung eines solchen Problems ist.

2.2 Der Dijkstra-Algorithmus

2.2.1 Formulierung

Der Dijkstra-Algorithmus ist relativ simpel aufgebaut, löst das Kürzeste-Wege- Problem jedoch in polynomialer Zeit. In einer Initialisierungsphase wird zunächst allen Knoten ein Distanzwert zugewiesen, der dem bisher gefundenen kürzesten Weg vom Startknoten zum betrachteten Knoten entspricht. Somit bekommt der Startknoten s die Distanz 0 und alle anderen Knoten bekommen die Distanz ∞ zugewiesen. Zusätzlich benötigen wir ein Vorgängerarray, welches zunächst für jeden Knoten mit 0 initialisiert wird.

In der Hauptschleife wird nun der unmarkierte Knoten v mit der kleinsten endlichen Distanz gesucht und markiert; im ersten Schritt ist dies automatisch der Startknoten. Anschließend werden alle Knoten w betrachtet, für die eine Kante e v w existiert. Sollte die Distanz von w größer als die Distanz von v plus dem Kantengewicht ce sein, so wird sie mit dem kleineren Wert aktualisiert, da wir damit einen günstigeren Weg zu diesem Knoten gefunden haben. Im Vorgängerarray wird in diesem Fall dem Knoten w der Knoten v zugewiesen, da dieser auf dem derzeit kürzesten s-w-Weg der direkte Vorgänger von w ist.

Abbildung in dieser Leseprobe nicht enthalten

”Esgibtkeinens-t-Weg.“; Algorithmus 1: Der Dijkstra-Algorithmus

Der Algorithmus terminiert, sobald entweder der Zielknoten t markiert, also der kürzeste Weg gefunden ist, oder aber kein unmarkierter Knoten mit endlicher Di- stanz mehr existiert. In diesem Fall gibt es keinen Weg von s nach t. Falls eine L ösung gefunden wird, so lässt sich anhand des Vorgängerarrays der kürzeste s-t- Weg ermitteln.

2.2.2 Korrektheit und Laufzeit

Die Korrektheit des Algorithmus basiert auf folgender Festellung:

Satz 2.1. Ist ein Knoten v markiert, so entspricht die ihm zugewiesene Distanz dem kürzesten Weg vom Startknoten nach v.

Beweis. Wir führen einen Beweis durch Widerspruch aus. Sei also [Abbildung in dieser Leseprobe nicht enthalten] der erste Knoten, auf den diese Eigenschaft nicht zutrifft. Dann gibt es einen Weg[Abbildung in dieser Leseprobe nicht enthalten] , dessen Länge kleiner als dist v ist. Wären alle Knoten auf diesem Weg bereits markiert, so hätte v diese Länge als Distanzwert bekommen; es muss also mindestens ein unmarkierter Knoten vorhanden sein. Sei u der erste unmarkierte Punkt auf der Wegstrecke. Der Distanzwert von u kann nur noch von einemüber einen bisher unmarkierten Knoten führenden Weg verringert werden. Da jedoch gerade v markiert worden ist, würde kein solcher Weg eine kleinere Länge als der bisherige Distanzwert von u erreichen. Somit muss der Distanzwert von u schon der Länge δ s u des kürzesten Weges von s nach u entsprechen. Es gilt also: Abbildung in dieser Leseprobe nicht enthalten Wir haben jedoch gerade v als kleinsten unmarkierten Distanzwert ermittelt, woraus ein Widerspruch folgt.

Da der Algorithmus abbricht, wenn der Zielknoten markiert ist, folgt aus dem Satz unmittelbar:

Korollar 2.2. Der Dijkstra-Algorithmus arbeitet korrekt und terminiert.

Es ergibt sich hieraus auch eine andere für den weiteren Verlauf der Arbeit wichtige Folgerung:

Korollar 2.3. Lässt man den Dijkstra-Algorithmus solange weiterlaufen, bis kein unmarkierter Knoten mit endlicher Distanz mehr existiert, so entsprechen die ermittelten Distanzen für jeden markierten Knoten v V dem kürzesten Weg vom Startknoten zu ihm. Zu allen bei Programmende unmarkierten Knoten gibt es keinen Weg vom Startknoten aus.

Dies bedeutet, dass die Berechnung aller kürzesten Wege von einem Startknoten aus eine Laufzeit gleicher Größenordnung wie die Berechnung eines kürzesten Weges von einem Start- zu einem Zielknoten hat.

Generell hängt die Laufzeit von der bei der Implementierung verwendeten Datenstruktur zur Verwaltung der unmarkierten Knoten und ihrer Distanzen ab. Wie in Tabelle 2 1 zu sehen ist, ist die Laufzeit aber polynomial.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: Aufwand des Dijkstra-Algorithmus bei Verwendung verschiedener Datenstrukturen

2.3 Beschleunigungsmethoden für den Dijkstra-Ansatz

Wie im vergangenen Abschnitt beschrieben wurde, ist der Dijkstra-Algorithmus im Grunde genommen darauf spezialisiert, kürzeste Wege von einem Start- zu meh- reren Zielknoten zu berechnen. Möchte man nur den Weg zu einem bestimmten Knoten berechnen, so ändert sich der eigentliche Verlauf des Verfahrens nicht. Wei- terhin breitet sich der Dijkstra-Algorithmus mehr oder weniger kreisförmig vom Startknoten aus, um in alle Richtungen kürzeste Wege zu erstellen, unabhängig davon, wo sich der Zielknoten befindet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Der Suchverlauf der verschiedenen Ansätze im Vergleich

Um die Suche effizienter zu gestalten, scheint es also naheliegend, sich Methoden zuüberlegen, welche entweder zusätzlich vom Zielknoten aus operieren oder sich etwas zielgerichteter in dessen Richtung verbreiten. Möglicherweise lässt sich der sich auf diese Weise ergebende Beschleunigungseffekt noch weiter verstärken, wenn beide Ideen miteinander kombiniert werden.

2.3.1 Der zielgerichtete Ansatz

Der zielgerichtete Ansatz versucht, den kürzesten Weg schneller zu finden, indem er Teilwege, die offensichtlich zu einem langem s-t-Weg führen, nicht weiter betrachtet. Dies wird erreicht, indem die Kantengewichte transformiert werden, so dass genau die Kanten, welche in die Richtung des Zielknotens führen, vom Algorithmus bevorzugt werden, während solche, die in die entgegengesetzte Richtung laufen, mit einem ungünstigeren Kostenwert bestraft werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Transformation der Kantengewichte.

Zur korrekten Ausführung werden untere Schranken LBvt für die kürzesten Wege von allen Knoten v V zum Zielknoten t benötigt. Die folgenden modifizierten Kantenbewertungen werden dann benutzt:

Abbildung in dieser Leseprobe nicht enthalten

Wie wir in Abbildung (2.2) gut erkennen können, wird somit der gewünschte Effekt erreicht. Die Kante v w1 wird gegenüber v w2 bevorzugt behandelt, da die untere Schranke für den restlichen w1-t-Weg kleiner als LB w2 t ist.

Der Dijkstra-Algorithmus funktioniert wie bereits erwähnt nur für nicht-negative Kantengewichte. Möchte man deswegen das Verfahren mit den transformierten Kantenkosten benutzen, so muss für die unteren Schranken folgende Konsistenzbedingung gelten:

Abbildung in dieser Leseprobe nicht enthalten

Diese Eigenschaft wird von vielen Bewertungsfunktionen erfüllt. Bei der Suche nach einem Weg mit der kürzesten Länge wäre zum Beispiel der geographische Abstand zwischen den jeweiligen Knoten als untere Schranke benutzbar.

Wenden wir nun den Dijkstra-Algorithmus auf die neuen Kantengewichte an, so liefert er einen kürzesten s-t-Weg der Länge dist t . Es lässt sich zeigen, dass dies auch der kürzeste Weg bezüglich der ursprünglichen Kosten dist t ist.

Satz 2.4. Seien auf einem Graphen G V E für Wege von jedem Knoten v zum Zielknoten t untere Schranken LB v t gegeben, die die Konsistenzbedingung (2.2) erfüllen. Wird der Dijkstra-Algorithmus mit anhand der Transformation (2.1) mo- difizierten Kantengewichten gestartet, so ist die ermittelte Lösung ein kürzester s- t-Weg bezüglich der ursprünglichen Kantengewichte, und für die Kosten des Weges gilt:

Abbildung in dieser Leseprobe nicht enthalten

Die Länge eines s-t-Weges unterscheidet sich also bei Benutzung der modifizierten Kantengewichte nur um einen kostanten Wert von der ursprünglichen Weglänge. Daraus folgt, dass der ermittelte kürzeste s-t-Weg auch ein kürzester Weg bezüglich des Ausgangsproblems sein muss.

Abbildung in dieser Leseprobe nicht enthalten

Algorithmus 2: Der zielgerichtete Dijkstra-Ansatz

Es ist zwar offensichtlich, dass der Beschleunigungseffekt dieses Ansatzes im Wesentlichen von der Qualität der benutzten unteren Schranken abhängt, dennoch benötigt der zielgerichtete Ansatz nie länger als der klassische DijkstraAlgorithmus. Für viele Verteilungen der Kantenlängen werden sogar im Mittel lineare Laufzeiten erreicht¹⁶.

2.3.2 Der bidirektionale Ansatz

Beim bidirektionalen Ansatz wird nicht versucht, vom Startknoten aus einen Weg zum Zielknoten zu erstellen, vielmehr werden gleichzeitig kürzeste Wege vom Start- und Zielknoten aus berechnet, die, sobald sie sich an einem Knoten treffen, zu einem kürzesten s-t-Weg zusammengefügt werden können.

Der Dijkstra-Algorithmus wird hierbei gleichzeitig vom Startknoten s und vom Zielknoten t aus gestartet, bei letzterem allerdings mit umgedrehten Kantenorien- tierungen. Jeder Knoten v hat somit zwei Distanzwerte dists v und distt v , und es werden diesmal zwei Vorgängerarrays benötigt. Laut Ahuja, Magnanti und Or- lin¹ kann die Suche beendet werden, sobald ein Knoten von beiden Richtun- gen aus markiert worden ist. Der kürzeste Weg besitzt dann eine Länge der Form dists u cuv distt v , wobei u ein von s aus markierter Knoten ist und v ein von t aus markierter Knoten.

Die Ermittlung des kürzesten Weges wird dannüber eine Minimumssuche aus- geführt. Gesucht wird der Knoten, der im Schritt vor der erstmaligen beidseitigen Markierung eines Knotens den kleinsten Summenwert der Distanzen hatte, also

Abbildung in dieser Leseprobe nicht enthalten

diese Knoten zum Zeitpunkt des Abbruchs in den Datenstrukturen zur Ermittlung des unmarkierten Knotens mit der kleinsten Distanz befinden, ist die Verwaltung eines solchen Minimums nicht allzu aufwendig.

Es lässt sich jedoch noch eine effektivere Abbruchbedingung formulieren.

Satz 2.5. Sei z : min dists u cuv distt v u von s aus markiert, v von t aus markiert und z0 : min dr v , r s t , v nicht von r aus markiert) . Gilt 2 z0 z, so ist z die kürzeste Weglänge des Problems und der dazugehörige Weg der kürzeste s-t-Weg.

Beweis. Würde man den Algorithmus laufen lassen, bis keine unmarkierten Kno- ten mit endlichen Distanzwerten mehr existieren, so wäre z offensichtlich die kürzeste Weglänge für unser Problem. Da z im Laufe des Algorithmus fällt und z0 steigt, reicht es zu zeigen, dass kein s-t-Weg mit kleineren Kosten als z existiert, sobald 2 z0 z gilt.

Es gelte also unsere Voraussetzung. Wir berücksichtigen alle Kanten e E als m ögliche Verbindungen von zwei Halbwegen. Sind beide adjazenten Knoten der betrachteten Kante bereits markiert, so wurde der daraus resultierende s-t-Weg bei der Minimumsbildung von z bereits berücksichtigt. Sind wiederum beide unmarkiert, so kann aufgrund unserer Voraussetzung dieser Weg unsere bisher minimale Weglänge nicht unterbieten, da jeder neu markierte Knoten einen Distanzwert erhalten wird, der mindestens so groß wie z0 ist.

Für den Fall, dass nur ein adjazenter Knoten markiert ist, nehmen wir o.B.d.A. an, dass es sich dabei für die Kante e u v um u handelt. Dann ist v zwar noch nicht vom Startknoten aus markiert, es gibt jedoch keinen s-v-Weg, derüber e führt und einen besseren Kostenwert hat. Somit entspricht die Länge dieses Weges mindestens den Distanzwerten des von beiden Seiten aus unmarkierten Knotens v und ist aufgrund der Voraussetzung ebenfalls größer als z. while Es existiert unmarkierter Knoten mit minimaler Distanz do Markiere unmarkierten Knoten v mit minimaler Distanz distmin; if 2 distmin best val then return gefundenen Weg; if Knoten von s aus markiert then

Abbildung in dieser Leseprobe nicht enthalten

Algorithmus 3: Der bidirektionale Dijkstra-Ansatz (Hauptschleife)

Um diese Bedingung nutzen zu können, müssen gewisse Anpassungen am Dijkstra-Algorithmus vorgenommen werden. Führt bei der Betrachtung der aus- gehenden Kanten eines gerade erst markierten Knotens eine Kante zu einem Kno- ten, der bereits von der anderen Seite aus markiert worden ist, so merke man sich diesen Knoten und die bei der Zusammensetzung dieser beiden Pfade entstehende Weglänge, falls bisher noch kein kürzerer Weg gefunden wurde. Sobald der Di- stanzwert des unmarkierten Knotens mit der kleinsten Distanz mehr als die Hälfte der bisher ermittelten kleinsten Weglänge beträgt, kann abgebrochen werden, weil diese dann nicht mehr unterboten werden kann. Dies passiert offensichtlich, bevor ein Knoten von beiden Seiten markiert worden ist, womit diese Bedingung zu be- vorzugen ist. In der Praxis scheinen sich jedoch die Laufzeiten kaum zu verringern, da die Anzahl der betrachteten Knoten nur unwesentlich sinkt.

Unabhängig davon, welche Abbruchbedingung man letztendlich bevorzugt, entfällt im Gegensatz zum unidirektionalen Dijkstra-Algorithmus die Überprüfung, ob der betrachtete Teilweg gerade den Zielknoten markiert hat, wenn er von s gestartet ist, bzw. ob er den Startknoten markiert hat, wenn er von t kommt. Start- und Ziel- knoten werden bereits bei der Initialisierung einseitig markiert, so dass wir hierbei nichts anderes als eine Überprüfung durchführen würden, ob ein Knoten von bei- den Seiten aus markiert ist. Wie wir gesehen haben, erreicht unser Abbruchkriteri- um nie diesen Zustand, während das von Ahuja, Magnanti und Orlin vorgestellte Kriterium bei Erreichen dieses Zustandes noch im selben Schleifendurchlauf ab- brechen würde.

In den meisten Fällen stellt das bidirektionale Verfahren eine Beschleunigung zum allgemeinen Dijkstra-Algorithmus dar. Geht man von einer kreisförmigen Verbrei- tung dieses Algorithmus aus, so entstehen beim bidirektionalen Ansatz zwei Kreise mit halb so großem Radius wie der beim unidirektionalen Ansatz benötigte Kreis. Da das Verhältnis der Fläche der kleineren Kreise zum größeren Kreis durch

Abbildung in dieser Leseprobe nicht enthalten

beschrieben wird, halbiert sich also bei gewünschtem Verlauf die Anzahl der betrachteten Knoten. Allerdings ist dieses Verfahren nicht zu empfehlen, wenn kein s-t-Weg existiert, denn dann wird ein doppelt so hoher Aufwand wie beim klassischen Ansatz betrieben.

2.3.3 Verbindung des zielgerichteten und des bidirektionalen Ansat-

Durch eine gleichzeitige Verwendung des zielgerichteten und des bidirektionalen Ansatzes erhofft man sich, die Vorteile beider Methoden miteinander zu vereinen und so eine weitere Beschleunigung zu erzielen. Leider liefert der auf die zielgerichteten Kantengewichte angewendete bidirektionale Ansatz jedoch nicht den kostenminimalen Weg bezüglich des Ausgangsproblems.

Betrachten wir einen Distanzwert, der einen vom Startknoten aus gestarteten s-u- Weg beschreibt, so lässt sich in gleicher Art und Weise wie beim Beweis von Satz (2.4) das Verhältnis zwischen transformierten Distanzwerten und Distanzwerten hinsichtlich der Originalkosten durch

Abbildung in dieser Leseprobe nicht enthalten

darstellen. Für den Fall, dass wir vom Zielknoten aus gestartet sind, ergibt sich eine analoge Formel. Ist e u v die Verbindungskante der in Frage kommenden Halbwege, so lassen sich also die Kosten des sich ergebenden Weges p wie folgt ausdrücken:

Abbildung in dieser Leseprobe nicht enthalten

Offensichtlich verfälschen die unteren Schranken zu den Knoten der Verbindungskante das Ergebnis. Wir benötigen deswegen ein Abbruchkriterium, welches sich auf die modifizierten Distanzwerte dist bezieht, aber bezüglich der OriginalWeglänge cp Optimalität garantiert.

while Es existiert unmarkierter Knoten mit endlicher Distanz do Markiere unmarkierten Knoten v mit minimaler Distanz distmin; if dist min best val LB s t then return gefundenen Weg; if Knoten von s aus markiert then

Abbildung in dieser Leseprobe nicht enthalten

Algorithmus 4: Der bidirektional zielgerichtete Dijkstra-Ansatz (Ausschnitt)

Satz 2.6. Sei best val die beim bidirektional zielgerichteten Ansatz bisher kürzeste gefundene s-t-Weglänge bezüglich der Originalkosten. Gilt für den kleinsten unmarkierten Distanzwert dist min die Ungleichung

Abbildung in dieser Leseprobe nicht enthalten

so lässt sich kein kostengünstigerer s-t-Weg mehr finden.

Beweis. Sei o.B.d.A. der kleinste Distanzwert aus einem vom Startknoten aus ge- starteten Weg zum Knoten u entstanden. Wie wir in (2.3) sehen, entspricht eine solche modifizierte Distanz genau der Länge des s-u-Teilweges plus dem Wert der unteren Schranke für einen u-t-Weg minus der unteren Schranke für einen s-t-Weg, welche für alle transformierten Distanzwerte gleich ist. Gilt unsere Ungleichung, dann kann aus dem betrachteten s-u-Weg kein kostengünstigster s-t-Weg mehr wer- den. Da wir immer den kleinsten Distanzwert markieren, kann in diesem Fall also best val nicht mehr unterboten werden.

Dieses Kriterium hat den Nachteil, dass es die Tatsache, dass wir einen bidirektio- nalen Ansatz verfolgen,überhaupt nicht ausnutzt. Es ist also zu erwarten, dass der Algorithmus, nachdem er den besten Weg gefunden hat, noch eine Weile weiter läuft.

Insgesamt ergibt sich nunmehr folgender Algorithmus: Wir starten den bidirektio- nalen Dijkstra-Algorithmus auf einem Graphen mit transformierten Kantengewich- ten. Finden wir einen Weg, so transformieren wir seine Länge zurück, um seine Originalkosten zu ermitteln, und speichern ihn, wenn er kostenminimal bezüglich des Ausgangsproblems ist. Der Algorithmus bricht ab, sobald die in (2.6) formu- lierte Abbruchbedingung gilt.

Kapitel 3 Ressourcenbeschränkte Wege

Ausgehend von den in Kapitel 2 erworbenen Kenntnissen bei der Lösung des Kürzeste-Wege-Problems zwischen zwei Knoten erweitern wir nun unsere Frage- stellung. Besitzt jede Kante noch ein zweites Kantengewicht, so führen wir für dieses Gewicht eine obere Schranke ein; kein zulässiger Weg darf einen höheren Verbrauch dieser Kostenart vorweisen. Wir untersuchen drei Probleme, die zusätz- lich diese Nebenbedingung erfüllen müssen: die Suche nach einem kürzesten Weg zwischen zwei Knoten, die Ermittlung von k sogenannten Pareto-optimalen We- gen zwischen zwei Punkten, sowie die Suche nach einem Weg, dessen durch das erste Kantengewicht bestimmte Kosten ebenfalls unter einer vorgegebenen oberen Schranke bleiben müssen. Wir erweitern den Dijkstra-Algorithmus derart, dass er den neuen Problemstellungen gerecht wird und lösen somit unsere neuen Frage- stellungen. Die in allen drei Fällen auftretende Einführung der oberen Ressourcen- schranke erhöht den Aufwand erheblich; so ist das in diesem Kapitel eingeführte ressourcenbeschränkte Kürzeste-Wege-Problem nicht in polynomialer Zeit lösbar, sondern schwach NP-vollständig. Aus diesem Grund machen wir von diversen Be- schleunigungsmethoden Gebrauch. Schließlich werden die Methoden vorgestellt, die zur Lösung des ressourcenbeschränkten Kürzeste-Wege-Problems im CMCF- Projekt und dem CNOP-Paket verwendet werden.

3.1 Problemstellung

Wie im vorangegangenen Kapitel betrachten wir ein Verkehrsnetzmodell, in dem die Straßen in einem Graphen als Kanten und die Kreuzungen als Knoten dargestellt werden. Jede dieser Kanten hat nun zwei verschiedene Kostenwerte, zum Beispiel Zeitverbrauch und Weglänge.

Sei also G V E ein gerichteter Graph und für jede Kante e E gebe es ein nicht-negatives Kostenpaar ce re . Wir bezeichnen im weiteren Verlauf der Arbeit die ce als Kosten und re als Ressource. Seien nun ein Startknoten s, ein Zielknoten t sowie eine obere Ressourcenschranke U BR (U pper Bound Resource) gegeben.

Wir werden im Folgenden unsere drei Problemstellungen anhand dieser Ausgangsdaten definieren.

3.1.1 Das ressourcenbeschränkte Kürzeste-Wege-Problem

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Beispielgraph

Schauen wir uns zunächst den Beispielgraphen aus Abbildung (3.5) an. Die Wege

Abbildung in dieser Leseprobe nicht enthalten

allesamt von s nach t. Das klassische Kürzeste-Wege-Problem würde p1 als Op- timallösung ermitteln, da dieser Weg Kosten von 4 aufweist. Führen wir nun als obere Schranke für das zweite Kantengewicht den Wert 6 ein, so ist p1 nicht mehr zulässig, da sein Ressourcenverbrauch zu hoch ist. Der kostenminimale zulässige Weg ist in diesem Fall p2. Er ist somit der ressourcenbeschränkte kürzeste Weg auf unserem Graphen.

Abbildung in dieser Leseprobe nicht enthalten

Wir werden im weiteren Verlauf diese Fragestellung mit dem Kürzel CSP (Constrained Shortest Path-Problem) bezeichnen.

[...]