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.

In the domain of route planning, the critical concern for travel efficiency has shifted towards optimizing travel time over distance due to the rise in congestion and the dynamic nature of modern road networks. Addressing this shift, we introduce Dynamic Route Optimization with Multi-Category Constraints (DROMC) for Point-of-Interest (POI) visits, which seeks to find the most time-efficient path that satisfies a user-defined list of requirements, considering both the spatial and temporal dimensions. This paper proposes a novel approach that leverages a path enumeration algorithm, which iteratively validates the k-fastest paths until all user queries are satisfied, ensuring adherence to time constraints and POI availability. To enhance the algorithm’s efficiency, we employ several key methodologies. First, we adapt the kSP algorithm to account for POI-focused path enumeration. We also introduce a Shared Prefix Tree (SPFT) with binary encoding, which significantly improves the storage and retrieval of path information. Moreover, we integrate a grid-based heuristic for quicker computation and implement strategic pruning methods to circumvent redundant calculations and manage POI business hours effectively. Our extensive experiments on real-world networks demonstrate the algorithm’s superiority in finding more efficient paths in shorter time frames compared to existing methods.

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.

Internet of Things (IoT) data provides rich data sources and application scenarios for trajectory representation learning. Trajectory representation learning aims to transform the original trajectory information into a general low-dimensional vector representation for many different downstream tasks (trajectory similarity calculation, anomaly detection, etc.). Current road network-based trajectory learning methods mainly focus on the spatial structure of the road network and often ignore the semantic information and complex feature information embedded in IOT data, in addition, the spatial and semantic properties of trajectories cannot be adequately preserved simultaneously. To this end, we propose a Trajectory Representation Learning framework based on Road network-TRLR. It first uses a graph attention network to learn the topological and semantic properties of road network segments, then it fuses node vectors and segment vectors as representations of node units, this is to support more data input types and enhanced node characteristics. Lastly, it learns the travel semantics of the trajectories through an information-enhanced transformer model, which captures the sequence information in the trajectory and generates the trajectory representation vector. In addition, we also propose four data augmentation methods to ensure that the trajectories can maintain both their spatial and semantic properties. To validate the effectiveness of our modeling approach, we conduct experiments on real datasets for similar trajectory search and mask prediction tasks. The experimental results demonstrate the performance improvement of our model.

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.

Low Earth Orbit (LEO) satellites have become important means of communication, and more and more transmission data flow query requests may arrive simultaneously due to the increasing number of users. Existing routing algorithms often prioritize individual data flow efficiency, neglecting satellite occupation and link utilization. This exacerbates queuing time and transmission delay. In this paper, Software Defined Network (SDN) is employed to obtain the information of satellite networks and focus on the overall transmission efficiency of a batch of data flows. A Large-Scale Query satellite routing Algorithm (LSQA) is proposed, which estimates the resources required for each data flow first and intends to find an optimal data flow query execution order to reduce satellite congestion. To speed up the estimation, we construct the node labels, so that the shortest path between satellites can be obtained quickly. Furthermore, we propose a strategy based on threshold filtering to obtain the optimal execution order more efficiently by finding out data flows whose execution order does not affect the overall transmission delay. Extensive experiments conducted on satellite network simulation show that LSQA has the superiority in terms of queuing delay and load-balancing compared with counterparts.

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.

Temporal information is critical for routing computation in the vehicular network. It plays a vital role in the vehicular network. Till now, most existing routing schemes in vehicular networks consider the networks as a sequence of static graphs. We need to find an appropriate method to process temporal information into routing computation. Thus, in this paper, we propose a routing algorithm based on the Hidden Markov Model (HMM) and temporal graph, namely, Prediction-Based Temporal Graph Routing Algorithm (PT-GROUT). This new algorithm considers the vehicular network as a temporal graph, in which each data transmission as an edge has its specific temporal information. To better capture the temporal information, we select Software-Defined Vehicular Network (SDVN) as our network architecture, which is a preferred architecture for processing the temporal graph regarding the vehicular network since all vehicle statuses can be easily managed. To compute the future routing path accurately and efficiently, the future temporal graph is predicted by applying HMM, in which we model the current vehicular network with dynamic programming and greedy strategies. With the temporal information and reasonable setting of HMM, PT-GROUT can better evaluate the vehicular network and discover the evolution of the internal structure of the network. The optimal routing path can be achieved more efficiently. The simulation results demonstrate that PT-GROUT can substantially improve the computation efficiency and reduce packet loss and delivery delay compared with its counterparts.

Existing electronic map apps, such as Baidu map, AutoNavi map, Google map, only provide the services “find k nearest POIs around me” and “give me the bus plan from s to d”. But they cannot answer “give me k POIs that I can reach earliest within one transfer by bus”. Such type of query is to find k nearest neighbors (kNN) on public transportation network (PTN), that is, returns k POIs whose arrival time are earliest starting from query location at some time and the number of required transfers is less than the user-specified constrain. Existing kNN algorithm on road network cannot be directly applied on PTN due to the more complex line combinations. Two algorithms TT-INE and TT-IER are proposed based on Incremental Network Expansion and Incremental Euclidean Restriction respectively. To address the loss of efficiency caused by the proliferation of alternative routes, a pruning strategy based on the route dominance relationship is designed. Moreover, to filter those stations who are not associated with POIs, a node compression method is also proposed, And a grid index is utilized to prune the POIs far away from the query based on the upper bound of arrival time. Extensive experiments have been conducted based on the real data of Beijing's PTN. Experimental results show that the TT-INE algorithm with pruning strategy is two orders of magnitude faster than the traditional incremental expansion method. When POIs are sparse, i.e. the percentage of POIs is 1 %, TT-IER is an order of magnitude faster than TT-INE.

In Software Defined Vehicular Networks (SDVNs), most existing studies of routing consider the vehicular network as a static graph and compute the flow table based on static information. However, a static graph could only contain partial network data. Routing computation based on the static graph could be inefficient because vehicular networks are temporal graphs. Thus, in this paper, we propose a novel routing algorithm based on the Markov model and the temporal graph. Unlike conventional routing algorithms, the proposed algorithm adopts the concept of the temporal graph where every edge has its specific temporal information. We apply the Markov model to predict the future routing of the network and adopt prediction data to get the optimal routing by running the temporal graph optimal path algorithm. A benefit of our proposal is, the proposed algorithm searched on the temporal graph of SDVNs can avoid generating additional routing overhead. Besides, based on the information of the vehicular network which is collected from the data plane, the controller can enhance the Markov model as time flows. By applying the above mechanisms, the flow table (route) could be calculated more precisely to enable efficient vehicular communication. The simulation experiments demonstrate the superiority of the proposed algorithm over its counterparts in high-density vehicular networks.