General information:
This site is about the Bachelor-Project "Multicriteria Multimodal
Routeplanning", realised in Winter Semester 2012, from September 2011
until January 2012.
It was written at the University of Freiburg by Simon Skilevic and Robin Schirrmeister and supervised by Prof. Hannah Bast.
The goal was to write a program that can perform shortest path
queries in a hybrid network of public transportation lines and roads.
These queries should use both the time of the path as well as the
amount of transfers as criteria, thus "multi-criteria".
The program should also be able to create some basic visualization of the Dijkstra computation.
More Algorithmic Details:
- The algorithm used to perform the shortest path queries was a
multi-label multi-criteria dijkstra, using both transfers and time as
criterias for the labels.
- We created both time-dependent and time-expanded networks
for the representation of the public transporation networks (of course
then only actually using one for a given query).
- For connections between the public transportation network
and the road network, we simply used the k (in our case, 4)
geographically closest road nodes of a given station and connected the
station with each of these road nodes (in both directions).
- We only actually modelled one day of the week in the
transit network and defined that, when the day is over, the same day
begins again(e.g. modelling just monday but defining monday 0:01 to be 2
minutes after monday 23:59). More technically, we always connected the
last "event" (departure of a bus etc.) at a station to the first
"event", using the time between the last event and the first event, if
it were on the next day,as the waiting time. This way, you could always
take any line leaving from a certain station, if you waited long enough,
even if you were arrived there late in the day.
Program Architecture:
We used C++ in the backend, including boost (only for the server communication).
For the multi-label multi-criteria multi-modal Dijsktra we used just
one class (i.e. one and the same for the time-dependent network and the
time-expanded network). For this, we implemented general functions for
getting the possible connections at a specific node at a specific time
and returning them as Connection objects. This way, the Dijkstra
algorithm could be kept relatively unaware of which underlying modelling
the public transportation network used. Also the Dijkstra could be kept
unaware if the connections that he worked on were coming from a road
network or a public transportation network.
We used general classes as well for the labels and the labelsets at
given nodes to allow for abstraction about the underlying types of
nodes/networks.
The program used OSM-Files and GTFS-Files as input to create the hybrid network.
For the frontend, we used javascript including jQuery, jQuery UI and the
google maps javascript API as our GUI. We sent requests for queries by
javascript to our server.
For the visualization of the dijkstra, we
always send parts of the labels used in the dijkstra (including time
needed to reach a given label, which label a given label was expanded
from, etc.) to the GUI to visualize them.
Documentation, Code:
Documentation is
here.
Download code
here.
Installation, Usage:
You need to have the boost libraries present on your
system for the server to work.
For the installation, just use the provided makefile
with make compile.
Start the server with: ./HybridServerMain -p Port
GTFSFolder OSMFile
Set the same port at the top of the transitPlaner.js file of the UI :)
Contact:
firstauthor.lastname AT gmail DOT com
secondauthor.firstname PLUS tibor AT gmail DOT com