Browsing by Author "Buchholz, Friedhelm"

Now showing 1 - 2 of 2

Open Access
Erfahrungen mit dem System TROSS beim DRK
(2000) Buchholz, Friedhelm; Wagner, Frank
Die Projektgruppe Transportoptimierung hat in einem Jahr (WS~97/98, SS~98) das System 'Transportorganisation für soziale Serviceanbieter' (TROSS) zur Disposition für die Fahrdienste des Deutschen Roten Kreuzes (DRK) Stuttgart erstellt. In den Fakultätsberichten Nr. 1998/10 und 1998/06 wird TROSS im Detail vorgestellt. Weil keine Wartung gewährleistet werden kann und das System auch noch einige Fehler hat, wird TROSS vom DRK nicht bei der täglichen Disposition benutzt. Trotzdem ist das Interesse vom DRK an einer computerunterstützten Planung und Optimierung bei der Organisation der Fahrdienste sehr groß. Aus diesem Grund hat man sich dort intensiv mit TROSS beschäftigt. Die dabei gesammelten Erfahrungen und daraufhin durchgeführten Korrekturen an TROSS werden in diesem Bericht zusammengefasst. Am Ende des Berichts werden dann mögliche Erweiterungen des Systems vorgestellt.
Open Access
Hierarchische Graphen zur Wegesuche
(2000) Buchholz, Friedhelm; Claus, Volker (Prof. Dr.)
In dieser Arbeit wird ein Zwei-Phasenmodell zur effizienten Entfernungsberechnung in gewichteten Graphen untersucht. Bekannte Anwendungsgebiete sind Verkehrsinformationssyteme, VLSI Design, Verteiltes Rechnen und geometrische und parallele Algorithmen. In einer Preprocessing-Phase wird zu einem Graphen ein Hierarchischer Graph (HG) konstruiert, der in der Online-Phase zur Entfernungsberechnung eingesetzt wird. Es werden die Laufzeit (T) der Preprocessing-Phase, die Groesse (S) des HG'en und die Laufzeit (Q) der Online-Phase untersucht. Zwei kontraere Modellierungsansaetze werden vorgestellt: Geeignete Knoten und ein rekursives Separationskonzept. Das Konzept mit Geeigneten Knoten wird auf Levelgraphen verallgemeinert und es wird gezeigt, dass die Berechnung einer minimalen Geeigneten Knotenmenge NP-vollstaendig ist. Die Approximation bzgl. der Groesse der Geeigneten Knotenmenge kann bis auf einen logarithmischen Faktor und bezueglich des Umgebungsabstands bis auf einen konstanten Faktor in polynomieller Laufzeit durchgefuehrt werden. Im Falle von planaren Graphen wird mittels eines erweiterten Separationskonzepts (Ideen von Lingas 1990 und von Didjev 1996 werden kombiniert) gezeigt, dass HG'en von fast linearer Groesse genuegen, um Q in O(n {1.5} log 3 n) zu gewaehrleisten. Dieses Resultat ist modulo logarithmischer Faktoren optimal. Ausserdem wird ein neuer Parameter 'Separatorweite' fuer Graphen eingefuehrt und es wird konstruktiv gezeigt, dass die Separatorweite unabhaengig von der Baumweite ist, aber hoechstens um einen logarithmischen Faktor von der Baumweite abweicht. Am Beispiel wird gezeigt, dass eine logarithmische Abweichung auftreten kann.