Route Planning in Road Networks

The last 15 years have seen astonishing progress in the performance of shortest path algorithms for road networks, many of them now being used in systems serving hundreds of millions of users every day.

This talk discusses challenges when adapting these algorithms to practical applications, and presents a new approach how to compute routes avoiding traffic. This turns out to be harder than expected, because imperfections in real-time traffic feeds may yield the presumably fastest route to cut through parking lots or residential areas.