Evaluation of Shortest Path and Distance Queries on Road using PRP

Abstract

We research a scenario for route path in road networks, where the aim to be optimized may change between every shortest path query. Since this invalidates many of the known speedup techniques for road networks that are based on data pre-processing of shortest path structures, we investigate optimizations exploiting simply the topological structure of networks. We experimentally estimate our technique on a large dataset of real-world road networks of various data sources. With lightweight data pre-processing our technique response long distance queries across continental networks significantly faster than previous approaches towards the same problem formulation.