Algorithms for Constrained Route Planning in Road Networks
- Author(s): Rice, Michael Norris
- Advisor(s): Tsotras, Vassilis J
- et al.
This dissertation examines advanced pre-processing techniques and query algorithms for efficiently solving several practical, real-world route planning problems for personalized navigation in road networks. Unlike most prior research in this domain, where shortest paths are assumed to be static, this research supports dynamically-constrained shortest path queries in which the resulting solution paths can vary depending on each traveler's unique requirements. Specifically, this research is comprised of two parts, each focusing on a high-level class of constrained route planning problems in road networks. In the first part, we consider route planning problems with avoidance constraints, in which the route is required to avoid certain types of roads (e.g., toll roads, unpaved roads, etc.). In the second part, we consider route planning problems with detour constraints, in which the route is required to visit one or more categorical points of interest along the way (e.g., gas stations, coffee shops, etc.). We consider several specific sub-problems for each of these high-level problems and present extensive experimental results of our proposed algorithms on the continental road networks of North America and Europe (with over 50 million edges and 90 million edges, respectively).