Path Planning in Road Network

Route planning software, of the type used for in-car navigation, is among the most ubiquitous applications of AI. Here, the environment is modelled as a graph, with each node representing a road intersection and each edge representing a traversable road segment between two adjacent nodes. From the users’ point of view, various types of paths (e.g. shortest distance, fastest travel time, etc.) may be preferred for their daily travel, but the main objective is to make the journey as efficient or economical as possible. From the system perspective, each path recommendation requires a pathfinding query on a large scale road network (e.g., city sized). Every day, millions of requests that need to be processed, making it a challenging task to provide high-quality paths that meet user criteria while maintaining fast response times. Effective algorithms for route planning are ones that: (i) find a feasible path from each start to each intended destination on the graph; (ii) minimise the user’s objective; and (iii) solve each problem as quickly as possible.

Shortest Path Problem

Static Road Networks are a widely used route planning model where the travel cost for each road segment remains fixed. We propose a novel oracle, CH-CPD [1], designed to efficiently answer shortest path queries in such networks. CH-CPD mitigates the disadvantages of the leading oracle approach, Compressed Path Databases (CPD), by investigating connections with another family of successful search-based speedup techniques called Contraction Hierarchies (CH). The figure on the left illustrates an example of CH-CPD, where the first-move data stored in the oracle now accounts for the contracted edges of CH. While CH-CPD extracts the shortest path fast, we further propose more advanced techniques to improve the preprocessing time, and a partial CH-CPD search that allows users to trade off between memory cost and query performance. In a range of experiments on road networks, we show that CH-CPD substantially improves on conventional CPDs in terms of pre-processing costs and online performance. We also report convincing query time improvements against a range of methods from the recent literature.

Time-dependent Road Networks is a more sophisticated type of route planning model where travel time on the network are allowed to vary during the day. These models can more accurately represented actual road conditions, since traffic congestion (among other issues) can affect travel times throughout the day. Figure left shows an example of a time-dependent network, where the graph G is undirected and only the edges that are highlighted in red have non-constant TTF with T = [0, 180). We focus on enhancing the Time-Dependent Contraction Hierarchies (TCH) algorithm, which computes optimal paths in such networks. Building on the success of CH-CPD, we adapt two heuristics: landmarks and CH-CPD, which rely on free-flow cost data and remain efficient despite the time dimension. We also introduce Single-layer TCH (STCH) and Multi-layer TCH (MTCH) [2], which use smaller TCHs for different time intervals, improving performance while retaining optimality. Our experiments on real and synthetic datasets show significant improvements over the baseline TCH.

Alternative Pathfinding

Alternative route planning requires finding k alternative paths (including the shortest path) between a given source and target. These paths should be significantly different from each other and meaningful/natural (e.g., must not contain loops or unnecessary detours). While there exists many work on finding high-quality alternative paths, the existing techniques are computationally expensive and are unable to accommodate the high volume of queries required by modern navigation systems. To address this, we propose an efficient algorithm, Hub-based Viable Alternative Routing (Hub-VAR) [3] to compute high-quality alternative paths. Hub-VAR employs hub-labeling to efficiently identify candidate alternative paths. The candidate paths are then ranked considering multiple quality metrics and the top-k alternative paths are returned. We propose several non-trivial optimizations to significantly improve the computation time. In our experimental study, we conduct experiments on three diverse real-world road networks and compare our proposed algorithm against six state-of-the-art algorithms. The results demonstrate that our algorithm is not only up to 3 orders of magnitude faster compared to most algorithms but also consistently generates alternative paths that are comparable or even superior in terms of quality across various metrics.

Other Location-based Service Queries

• Reverse Nearest Neighborhood Queries [4]: Reverse nearest neighborhood (RNH) queries find neighborhoods that consider a query facility as their nearest among other facilities. Unlike reverse nearest neighbor (RNN) queries, RNH focuses on groups of users rather than individuals. Given user locations U, facility locations F, query location q, distance ρ, and integer k, an RNH query returns all ρ-radius circles enclosing at least k users where q is closer to the circle than any other facility. RNH queries have practical applications, such as facility placement and urban planning. We propose an efficient R-tree-based method, validated through experiments with real datasets.

• Surrounding Object Retrieval Queries [5]: Retrieving arbitrary-shaped surrounding objects has many applications, such as nearby object-of-interest retrieval in spatial databases. We introduce the directional zone concept to assess directional similarity among spatial objects and propose a novel direction-based spatial skyline (DSS) query to retrieve non-dominated surrounding objects. The DSS query is rotationally invariant and fair. We develop efficient DSS algorithms using R-Tree indexing and novel pruning techniques. Extensive experiments with real datasets validate the effectiveness and efficiency of our approach.

• Surrounding PoI Retrieval Queries [6]: Retrieving surrounding objects in spatial databases has applications like nearby point-of-interest retrieval and digital gaming. We introduce a novel query, the direction-based spatial skyline (DSS), which retrieves surrounding objects that are not directionally dominated by others relative to a query object. The DSS query is rotationally invariant, fair, and stable. We also present efficient algorithms for processing DSS queries using novel pruning techniques with R-Tree indexing. Extensive experiments with real and synthetic datasets validate the effectiveness and efficiency of the proposed methods.