Shortest Paths on Road Networks

PhD Qualifying Examination


Title: "Shortest Paths on Road Networks"

by

Mr. Panagiotis Parchas


Abstract:

Given two locations in a road network the shortest path query returns the 
network path of minimum cost that connects the two locations. The problem finds 
applications in route planning, nearest neighbor search, traffic analysis etc. 
Although the shortest path problem dates back to the sixties, new approaches 
have appeared in the past decade, mainly because of the fast development of 
navigation systems, including the Global Positioning System (GPS). The 
increasing demand on location based services has resulted in greater need for 
efficient solutions to the problem of Shortest Paths on Road Networks (here 
after also termed SP). The new methods proposed are basically based on offline 
precomputation, in order to reduce the response time of online queries. In this 
work we survey the most important techniques that solve the problem 
efficiently. We focus on two different settings, namely the static and the time 
dependent. The static setting assumes constant edge costs. On the other hand, 
the time dependent model captures changes in the network (e.g., traffic delays, 
closed roads, construction sites etc.) by assigning functions of time as edge 
costs. In addition to an extensive literature survey, we present experiments 
with real traffic datasets that evaluate the differences and the challenges of 
the two settings.


Date:                   Tuesday, 18 December 2012

Time:                   10:00am - 12:00noon

Venue:                  Room 3401
                         lifts 17/18

Committee Members:	Prof. Dimitris Papadias (Supervisor)
                         Dr. Lei Chen (Chairperson)
 			Prof. Chi-Keung Tang
 			Dr. Raymond Wong


**** ALL are Welcome ****