Reliable routing in road networks

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 of Award	2018
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology