Goal Directed Speed-Up Techniques for Shortest Path Queries in Timetable Networks

31. Januar 2008, Thomas Pajor

Almost any transport company, like railway companies or air lines, have timetables for planning and scheduling their specific services. The problem of finding an optimal itinerary according to some optimization criterion like travel time can be reduced to a shortest path problem on an adequate graph with non-negative edge weights.

The most prominent algorithm for solving the shortest path problem on such graphs is Dijkstra's algorithm without a doubt. Unfortunately, the data sets are far too huge for a naive implementation of Dijkstra to perform quick enough. Therefore, lots of research has been put into developing speed-up techniques, which give really amazing results on road network graphs. However, on timetable networks the achieved speed-ups, as of today, are far from what can be done on road networks.

Due to time being a crucial aspect on timetable graphs (a road can be used at any time, but a train is only departing at specific times), speed-up techniques specially developed for road networks need to be adapted carefully in order to work properly. Some techniques like highway hierarchies do not work at all, because they require a bidirectional search, which can not be done on timetable networks, since we do not know the arrival time in advance when stating a query.

In this work we present several approaches to model timetable networks to support shortest path queries which minimize travel time. Furthermore, we adapt two unidirectional goal directed speed-up techniques which belong to the best on road networks to work with our time expanded model, namely Arc-Flags and ALT. Both techniques are goal directed in the sense that they try to optimize toward the target station, either geographically or in time. For that reason, we explore the combination of these techniques as well and see that they behave quite orthogonally, as the speed-up of the combined technique multiplies.

Finally, in our experimental study we conduct tests on huge sets of real world data to show the feasibility of our approaches which lead to some very good speed-ups with the combination of the Arc-Flags and the ALT approach.

Implementierung und Visualisierung des Planar-Separator-Algorithmus

1. April 2007, Dirk Achenbach, Thomas Pajor, Jonida Saqe

Im Rahmen des Praktikums "Algorithm Engineering" im Wintersemester 2006/2007 an der Universität Karlsruhe haben wir den Algorithmus zum Planar-Separator-Theorem in Java implementiert und mit Hilfe von Java3D visualisiert. Das Planar-Separator-Theorem besagt, dass jeder planare Graph mit Knoten durch Wegnahme einer Separatormenge, die weniger als Knoten enthält, so in zwei nicht-zusammenhängende Komponenten zerteilt werden kann, dass jede höchstens Knoten enthält. In dieser Ausarbeitung präsentieren wir unsere Implementierung des Algorithmus und möchten besonders auf die zum Teil nicht offensichtlichen Schwierigkeiten eingehen, die während der Implementierung aufgetreten sind. Abschließend stellen wir einige Ergebnisse von Experimenten bezüglich der Qualität des Algorithmus vor, die wir an drei Graphklassen durchgeführt haben.

Triangulierung eines Planaren Graphen

1. Februar 2007, Thomas Pajor

Das Triangulieren eines Graphen ist eine Grundoperation, die von vielen Algorithmen, die auf planaren Graphen operieren, benötigt wird. Der hier vorgestellte Algorithmus trianguliert einen Graphen mit Knoten in Zeit durch geeignetes Einfügen von Kanten.

Einige Kalküle der Logik

27. Februar 2006, Thomas Pajor

Dieses Dokument soll eine Zusammenfassung einiger Kalküle aus der Aussagenlogik und Prädikatenlogik erster Stufe sein. Kalküle dienen dazu innerhalb eines formalen Systems, beispielsweise eines Logiksystems, Aussagen zu beweisen oder zu widerlegen. Da dies ein wichtiger Bestandteil der Vorlesung "Formale Systeme" an der Universität Karlsruhe ist, erhoffe ich mir durch die Erstellung des Papiers einen kleinen Lerneffekt für mich. Aber vielleicht hilft es auch dem einen oder anderen beim Verständnis. Ich setze hier die Grundbegriffe der Logik wie "erfüllbar", "allgemeingültig" usw. voraus. Genauso sollte man wissen wie die Aussagenlogik und Prädikatenlogik syntaktisch definiert sind und was eine Interpretation bzw. ein Modell ist.

Das Symbol für Hochgradigkeit

2. Februar 2006, Dirk Achenbach & Thomas Pajor

Hochgradigkeit tritt im Alltag in vielen Situationen auf. Besonders oft wird man jedoch in mathematischen Beweisen oder Aussagen mit ihr konfrontiert. Folgende Symbole können (zum Beispiel als Randnotiz) in dazu benutzt werden, um dem geneigten Leser zu verdeutlichen - bzw. ihn zu warnen - dass eine hochgradige Stelle folgt.

Das Mysterium der Koordinatenvektoren bei Linearen Abbildungen

17. September 2005, Thomas Pajor

Teil der Vorlesung "Lineare Algebra und Analytische Geometrie" an der Universität Karlsruhe (TH) ist die Darstellung linearer Abbildungen durch Matrizen. Diese setzen ein Verständnis des Begriffs Koordinatenvektor voraus. Da dieses Thema extremst grundlegend und wichtig ist, und es meist nicht richtig verstanden wird, habe ich dieses kleine Paper geschrieben, um vielleicht ein wenig für Aufklärung zu sorgen...

Der Minus-Eins-Zeilen-Trick

1. Juni 2005, Thomas Pajor

Das Lösen von homogenen linearen Gleichungssystemen (LGS) ist in der linearen Algebra von zentraler Bedeutung. Als Standardverfahren wird dabei die Gauß-Elimination verwendet, bei der man das LGS als Matrix auffast und dann diese durch elementare Zeilenumformungen in Gaußnormalform (GNF) bringt.

Hat man als Endprodukt die GNF hergeleitet, und gilt , so hat man nun das Problem den Lösungsraum irgendwie abzulesen. Dieses Dokument soll dazu einen höchst geheimen Trick vorstellen, und zwar den sogenannten "Minus-Eins Zeilen-Trick", mit dem das Ablesen der Lösung in einem Bruchteil einer Sekunde möglich ist.

Der Mysteriöse Grenzwert

1. Juni 2005, Thomas Pajor

Ich möchte hier einen Beweis liefern, dass die Funktion für gegen unendlich gerade gegen strebt. Daraus folgt nämlich dass für sehr große gilt dass . Dies ist unter anderem beim Beweis der unteren Schranke für Sortieren relevant.