SciDok - Wissenschafts-Server der Universitaet des Saarlandes
Home
Home
Suchen
Suche
Volltextsuche
Volltextsuche
Browsen
Browsen
Veröffentlichen
Veröffentlichen
Uni-Homepage

Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:291-scidok-2515
URL: http://scidok.sulb.uni-saarland.de/volltexte/2004/251/

Ziegelmann, Mark

Constrained shortest paths and related problems

pdf-Format:
Dokument 1.pdf (2.040 KB)

Kurzfassung in Englisch

The classical shortest path problem, to find a path of minimal cost between two nodes in a graph, is efficiently solvable in polynomial time. However, in many applications we also have additional budget or resource constraints on a path. This problem is known as constrained shortest path problem and unfortunately belongs to the class of "hard" problems for which no polynomial time algorithm is known. In this thesis, we propose a 2-step method for the constrained shortest path problem. We first solve a relaxation to get upper and lower bounds and then close the gap with clever path ranking to obtain the exact solution. We compare different old and new methods both theoretically and experimentally. The 2-step method also works for a more general class of constrained network optimization problems. We illustrate the generic a approach using several examples. We have also developed a software package CNOP that provides this generic 2-step approach as well as all state of the art algorithms for constrained shortest paths.

Kurzfassung in Deutsch

Das klassische Kürzeste-Wege-Problem, bei dem man einen Pfad minimaler Kosten zwischen zwei Knoten eines Graphen sucht, ist effizient in polynomieller Zeit lösbar. In vielen praktischen Anwendungen wollen wir jedoch, dass ein Pfad bestimmte Budget- oder Ressourcenbedingungen erfüllt. Dies ist das Kürzeste-Wege-Problem mit Nebenbedingungen, das zur Klasse der "schweren" Probleme gehört, für die wir keinen polynomiellen Algorithmus kennen. In dieser Arbeit stellen wir eine 2-Schritt-Methode für das Kürzeste-Wege-Problem mit Nebenbedingungen vor. Wir lösen zuerest eine Relaxierung des Problems und erhalten eine obere und untere Schranke, um dann durch Schließen der Lücke durch geschicktes Auflisten von Pfaden das Optimum zu bestimmen. Wir vergleichen bekannte und neue Verfahren sowohl theoretisch als auch experimentell. Die 2-Schritt-Methode ist auch auf eine allgemeinere Klasse von Netzwerkoptimierungsproblmen mit Nebenbedinungen anwendbar. Wir illustrieren die generische Methode anhand einiger Beispiele. Danach stellen wir unser Softwarepaket CNOP vor, das dieses generische Verfahren implementiert, sowie alle bekannten Verfahren für das Kürzeste-Wege-Problem mit Nebenbedingungen zur Verfügung stellt.

SWD-Schlagwörter: Kürzester-Weg-Problem ; Nebenbedingung ; Relaxationsmethode ; Mehrschrittverfahren
Institut: Sonstige Einrichtungen
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Prof. Dr. Kurt Mehlhorn
Sprache: Englisch
Tag der mündlichen Prüfung: 30.07.2001
Erstellungsjahr: 2001
Publikationsdatum: 19.05.2004
Home Hilfe Policy Viewer SULB SaarDok Impressum Kontakt