Fastest Paths and Stochastic Routing in Road Networks: A Survey

PhD Qualifying Examination


Title: "Fastest Paths and Stochastic Routing in Road Networks: A Survey"

by

Mr. Dimitris Tsakalidis


Abstract:

Given an origin and a destination node in a road network the shortest path 
query returns the path of minimum cost that connects the two nodes. The problem 
finds applications in route planning, nearest neighbor search, traffic analysis 
or social networks but also in other research fields such as mathematics, 
operational research and transportation engineering to name a few. Although the 
shortest path problem is considered to be one of the most famous in computer 
science for more than 50 years, today novel routing algorithms for 
transportation networks emerge, mainly because of the fast development of 
navigation systems and also the rising proliferation of sensors and mobile 
devices that are able to provide a vast majority of trajectory data. The 
increasing demand on location based services has resulted in greater need for 
efficient solutions evolving the problem from finding Shortest Paths on Road 
Networks to finding Fastest Paths, capturing the time dependency across the 
links of the road network.

In this work we survey the most important techniques that solve these problems 
efficiently. We provide a brief introduction to the static setting and focus on 
two different settings, the time dependent and the stochastic formulation of 
the problem. The static setting assumes constant edge costs. On the other hand, 
the time dependent model captures changes in the network, such as traffic 
congestion, by assigning functions of time as edge costs. While routing 
time-dependently provides more accurate results than the static approach, it 
does not take into account the uncertain events that can influence the travel 
times of the different links in a road network. So we present the stochastic 
setting of the shortest path problem, where links are formulated as random 
variables, a setting that can capture the uncertainty of the network more 
effectively and thus leading to more accurate solutions.


Date:			Tuesday, 16 February 2016

Time:                  	3:00pm - 5:00pm

Venue:                  Room 1504
                         Lifts 25/26

Committee Members:	Prof. Dimitris Papadias (Supervisor)
 			Dr. Wilfred Ng (Chairperson)
 			Dr. Qiong Luo
 			Dr. Raymond Wong


**** ALL are Welcome ****