PAV-A-<i>k</i>NN: A Novel Approachable <i>k</i>NN Query Method in Road Network Environments

Ride-hailing (e.g., DiDi and Uber) has become an important tool for modern urban mobility. To improve the utilization efficiency of ride-hailing vehicles, a novel query method, called Approachable k-nearest neighbor (A-kNN), has recently been proposed in the industry. Unlike traditional kNN queries, A-kNN considers not only the road network distance but also the availability status of vehicles. In this context, even vehicles with passengers can still be considered potential candidates for dispatch if their destinations are near the requester’s location. The V-Tree-based query method, due to its structural characteristics, is capable of efficiently finding k-nearest moving objects within a road network. It is a currently popular query solution in ride-hailing services. However, when vertices to be queried are close in the graph but distant in the index, the V-Tree-based method necessitates the traversal of numerous irrelevant subgraphs, which makes its processing of A-kNN queries less efficient. To address this issue, we optimize the V-Tree-based method and propose a novel index structure, the Path-Accelerated V-Tree (PAV-Tree), to improve query performance by introducing shortcuts. Leveraging this index, we introduce a novel query optimization algorithm, PAV-A-kNN, specifically designed to process A-kNN queries efficiently. Experimental results show that PAV-A-kNN achieves query times up to 2.2–15 times faster than baseline methods, with microsecond-level latency.