Reliable Routing in Road Networks

MPhil Thesis Defence


Title: "Reliable Routing in Road Networks"

By

Mr. Dimitrios TSAKALIDIS


Abstract

Finding optimal routes in road networks is a fine example of the benefit people 
acquire from the development of algorithms in our everyday lives. Shortest path 
algorithms have been applied in route planning, nearest neighbor search and 
traffic analysis among others. Given an origin and a destination in a road 
network, the shortest path query returns the network path of minimum cost that 
connects the two locations. Although the shortest path problem dates back to 
the sixties, today novel routing algorithms for transportation networks emerge, 
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 changing the 
problem of finding shortest paths on road networks, to finding either the 
fastest or the most reliable paths. We examine collectively these problems 
under three different settings based on the formulation of the edge weights, 
namely the static, the time dependent and the probabilistic. The static setting 
assumes constant edge weights, the time dependent model captures changes in the 
network (e.g., traffic delays, peak/off-peak hours, construction sites etc.) by 
assigning functions of time as edge costs, and the stochastic shortest path 
problem models edge costs as random variables. In this work we emphasize on the 
stochastic shortest path problem and its different approaches, as it is the 
most accurate way to capture the uncertain nature of traffic systems.


Date:			Wednesday, 27 June 2018

Time:			2:00pm - 4:00pm

Venue:			Room 5560
 			Lifts 27/28

Committee Members:	Prof. Dimitris Papadias (Supervisor)
 			Dr. Pedro Sander (Chairperson)
 			Dr. Dimitris PAPADOPOULOS


**** ALL are Welcome ****