NRP: An Efficient Index for Stochastic Routing in Road Networks

The pervasiveness of shortest path queries is evident in real life, particularly in online mapping applications. However, in practice, the travel times of road segments can be uncertain due to various reasons, such as traffic congestion, which leads to the shortest path not to be the fastest, resulting in an unreliable path. The Reliable Shortest Path (RSP) query has been developed to fulfill individuals' reliability requirements by considering travel times as random variables. Extensive solutions have been proposed to efficiently find RSPs in stochastic road networks. However, they are either unscalable to large networks or incapable of handling rapid streams of routing queries. In this paper, we propose an efficient index-based solution for RSP queries, called Non-dominated Reliable Path (NRP). It stores partial path answers to support fast query processing and utilizes several tailored pruning techniques that can significantly reduce the query time. Experiments conducted on large city road networks verified the superiority of our solution, which can answer each query in around 100 microseconds and beat competitors by orders of magnitude.