Given a source, destination, and required keywords, the Optimal Route with Collective Spatial Keywords ( ORCSK ) query aims to find the shortest route covering all keywords. Existing Point of Interest (POI) candidate set-based and path expansion-based methods frequently produce inferior route quality or excessive time overhead, particularly under large-scale query keywords. To address this challenge, we introduce the DO framework, which pioneers the employ Deep Reinforcement Learning for the ORCSK. Specifically, DO first integrates the spatial index with the H2H index to generate and refine high-quality candidate sets. Subsequently, DO utilizes a Transformer-based model to determine the optimal route from the sets. To effectively combine spatial distance and POI attributes, we propose a novel dual-cross encoder architecture. Furthermore, leveraging this architecture, we introduce a multi-route generating strategy, exploiting parallel computing to enhance route quality. Our experiments on real-life road networks demonstrate superior route quality and response time compared to the state-of-the-art method, with an average improvement of 1-2 orders of magnitude in response time, and maintain high efficiency even under large-scale query keywords or dynamic POI attributes scenarios.

Abstract With the development of location-based services, smart cities, and intelligent transportation, route planning has evolved beyond shortest path finding to satisfy user’s flexible travel purposes through the Optimal Routes with Collective Spatial Keywords (ORCSK) routing. Because different Points of Interest (POIs) contain different sets of keywords, the user usually needs to visit multiple POIs to fulfill all needs. Moreover, the POIs’ stop hardness (time and cost) also influences user experience, but it was ignored by the existing solutions. Therefore, this work proposes to extend the ORCSK problem into Skyline Optimal Routes with Collective Spatial Keyword (Sky-ORCSK) by considering both distance and stop hardness. Specifically, we first propose the IG-Sky algorithm from the spatial keyword search perspective by extending the IG-Tree. Then we propose the DA-Sky algorithm from the path enumeration perspective by extending our previous DA-CSK. Furthermore, five optimization strategies are proposed to improve efficiency by pruning the search space. Extensive experimental evaluations on real-world datasets demonstrate the algorithms’ efficacy and reliability, marking a significant step forward in refined route planning for modern urban environments.

Shortest distance computation is a fundamental operation in graph-related applications, especially in location-based services. The most efficient method is hop-labeling, which can answer queries in microseconds. However, when the traffic condition changes dynamically, they need a long time to maintain or an even longer time to re-construct, making it hard to catch up with numerous or frequent updates. As a result, real-life applications still rely on slow graph searching algorithms. To improve the hop labeling construction efficiency, we resort to GPU for its high parallelism power and propose the G2H index. Specifically, we first analyze the relation of the graph partitions, index performance, and parallelism to identify the most suitable partition scheme for G2H, with a hybrid scheme and optimized node ordering for faster contraction. Then, we propose a label-pruning method to reduce the label construction workload with several strategies designed to balance and improve the parallel label construction. Finally, experiments on real-life networks show that our G2H can finish construction within seconds for large urban networks and under one minute for large region networks with 6M vertices, which is several times faster than the state-of-the-art methods. Besides, G2H can answer hundreds of millions of queries per second, achieving two orders of magnitude acceleration.

As more detailed POI (Point of Interest) information has been incorporated into road network, routing has evolved from finding paths from one place to another, to satisfying users’ needs (keywords) along the trip. However, the existing solutions either only support one keyword per POI, or require a fixed visiting order, or only provide one option to choose from. Therefore, we study the top-k Optimal Routes with Collective Spatial Keywords (k-ORCSK) problem, which is the most general keyword-aware routing problem that supports multiple keywords, arbitrary orders, and top-k results. To solve this problem, we apply an enumeration framework and reduce the complexity by contracting non POI-related vertices and taking the keywords into account. After that, we propose a best-first path expansion method DA-CSK based on deviation to convert the enumeration paradigm from the distance-oriented to the keyword-oriented. Finally, several optimization techniques are provided to further improve the query efficiency. Extensive experiments conducted on multiple real-life road networks show that our method can provide higher quality results more efficiently.

Abstract In this paper, we study the Time-Dependent k Nearest Neighbor (TD- k NN) query on moving objects that aims to return k objects arriving at the query location with the least traveling cost departing at a given time t . Although the k NN query on moving objects has been widely studied in the scenario of the static road network, the TD- k NN query tends to be more complicated and challenging because under the time-dependent road network, the cost of each edge is measured by a cost function rather than a fixed distance value. To tackle such difficulty, we adopt the framework of GLAD and develop an advanced index structure to support efficient fastest travel cost query on time-dependent road network. In particular, we propose the Time-Dependent H2H (TD-H2H) index, which pre-computes the aggregated weight functions between each node to some specific nodes in the decomposition tree derived from the road network. Additionally, we establish a grid index on moving objects for candidate object retrieval and location update. To further accelerate the TD- k NN query, two pruning strategies are proposed in our solution. Apart from that, we extend our framework to tackle the time-dependent approachable k NN (TD-A k NN) query on moving objects targeting for the application of taxi-hailing service, where the moving object might have been occupied. Extensive experiments with different parameter settings on real-world road network show that our solutions for both TD- k NN and TD-A k NN queries are superior to the competitors in orders of magnitude.