Recently, with the advancement of the GPS-enabled cellular technologies, the location-based services (LBS) have gained in popularity. Nowadays, an increasingly larger number of map-based applications enable users to ask a wider variety of queries. Researchers have studied the ride-sharing, the carpooling, the vehicle routing, and the collective travel planning problems extensively in recent years. Collective traveling has the benefit of being environment-friendly by reducing the global travel cost, the greenhouse gas emission, and the energy consumption. In this paper, we introduce several optimization problems to recommend a suitable route and stops of a vehicle, in a road network, for a group of users intending to travel collectively. The goal of each problem is to minimize the aggregate cost of the individual travelers' paths and the shared route under various constraints. First, we formulate the problem of determining the optimal pair of end-stops, given a set of queries that originate and terminate near the two prospective end regions. We outline a baseline polynomial-time algorithm and propose a new faster solution - both calculating an exact answer. In our approach, we utilize the path-coherence property of road networks to develop an efficient algorithm. Second, we define the problem of calculating the optimal route and intermediate stops of a vehicle that picks up and drops off passengers en-route, given its start and end stoppages, and a set of path queries from users. We outline an exact solution of both time and space complexities exponential in the number of queries. Then, we propose a novel polynomial-time-and-space heuristic algorithm that performs reasonably well in practice. We also analyze several variants of this problem under different constraints. Last, we perform extensive experiments that demonstrate the efficiency and accuracy of our algorithms.
Our @math query is different from the point-to-point shortest path query in two aspects. First, it takes multiple source-destination pairs as input. Second, it aims to optimize a different cost function, which is a summation of the vehicle's path cost and the passenger's solo travel costs. Therefore, the traditional shortest path algorithms such as the @math @cite_40 , @cite_44 , and the @math @cite_0 cannot answer our query. Similarly, we cannot use faster hierarchy based approaches like @cite_42 , @cite_37 , and @cite_38 either. However, we benefit from the @math 's algorithm @cite_40 , @cite_44 , the bidirectional search @cite_30 , and the group shortest path approach @cite_10 . @cite_10 introduces a technique to process a batch of shortest path queries simultaneously, based on the path-coherence property of road networks. Although @cite_10 cannot solve our problem, we borrow the intuition behind its simultaneous search to develop an efficient algorithm in that answers the @math query.
@cite_30 @cite_38 @cite_37 @cite_42 @cite_44 @cite_0 @cite_40 @cite_10
1504126076 2151954369 2019003829 1985248597
The recent advancement of GPS-enabled mobile technologies and the proliferation of map-based applications are attracting an increasing number of people to use location based services (LBSs). Processing a larger number of simultaneous queries efficiently have become an important research topic in recent years. In this paper, we focus on an important class of LBSs, shortest path queries (SP-queries) in road networks. Given a source and a destination in a road network, an SP-query returns the path from the source to the destination that minimizes the travel time. We particularly focus on batch processing of simultaneous SP-queries in road networks. Traditional systems that process one query at a time usually provide slow responses, causing the machine to flood with incoming queries. Existing fast solutions for SP-queries require expensive pre-processing steps and are incapable of adapting with the continuous change in traffic on the roads. We propose an efficient group based approach that provides an approximate solution with reduced cost and high accuracy. An important benefit of our approach is that it does not require expensive pre-processing. The key concept is to exploit the path-coherence property of road networks by grouping queries that share substantial common paths in their shortest paths and processing the group in a single pass. Our approach incurs an average relative error of 0.5 and is on average 6 times faster than the straightforward approach that evaluates each SP-query individually. Shortest paths and shortest path distances are important primary queries for users to query in a large graph. In this paper, we propose a new approach to answer shortest path and shortest path distance queries efficiently with an error bound. The error bound is controlled by a user-specified parameter, and the online query efficiency is achieved with prepossessing offline. In the offline preprocessing, we take a reference node embedding approach which computes the single-source shortest paths from each reference node to all the other nodes. To guarantee the user-specified error bound, we design a novel coverage-based reference node selection strategy, and show that selecting the optimal set of reference nodes is NP-hard. We propose a greedy selection algorithm which exploits the submodular property of the formulated objective function, and use a graph partitioning-based heuristic to further reduce the offline computational complexity of reference node embedding. In the online query answering, we use the precomputed distances to provide a lower bound and an upper bound of the true shortest path distance based on the triangle inequality. In addition, we propose a linear algorithm which computes the approximate shortest path between two nodes within the error bound. We perform extensive experimental evaluation on a large-scale road network and a social network and demonstrate the effectiveness and efficiency of our proposed methods. We consider the point-to-point (approximate) shortest-path query problem, which is the following generalization of the classical single-source (SSSP) and all-pairs shortest-path (APSP) problems: we are first presented with a network (graph). A so-called preprocessing algorithm may compute certain information (a data structure or index) to prepare for the next phase. After this preprocessing step, applications may ask shortest-path or distance queries, which should be answered as fast as possible. Due to its many applications in areas such as transportation, networking, and social science, this problem has been considered by researchers from various communities (sometimes under different names): algorithm engineers construct fast route planning methods; database and information systems researchers investigate materialization tradeoffs, query processing on spatial networks, and reachability queries; and theoretical computer scientists analyze distance oracles and sparse spanners. Related problems are considered for compact routing and distance labeling schemes in networking and distributed computing and for metric embeddings in geometry as well. In this survey, we review selected approaches, algorithms, and results on shortest-path queries from these fields, with the main focus lying on the tradeoff between the index size and the query time. We survey methods for general graphs as well as specialized methods for restricted graph classes, in particular for those classes with arguable practical significance such as planar graphs and complex networks. The problem of processing shortest pa th queries in graphs arises in application areas such as intelligent t ranspor ta t ion system (ITS), geographic information system (GIS), and robotics. In this paper, we present an efficient algorithmic solution for processing shortest pa th queries in undirected planar graphs with non-negative edge weights. Previous algorithms for this problem on planar graphs all have a tradeoff between the query t ime and the da ta structure space used by the solutions. The previously best known trade-off on an n-vertex planar graph G in the worst case is O(v -r) t ime for a pa th length query and O(v -r + L) t ime for report ing an actual shortest path, with a da ta structure of O(n2 x ) space, where r is an integer parameter with 1 < r _< n and L is the number of edges on the output shortest path. We present a new scheme, called frame search, that exploits the graph planari ty in a novel fashion. Wi th this scheme, we build an improved da ta structure of O(n + pv -r + p2 r) space (in O(n + p2 v + pr 3 4) time), where p is the minimum cardinality of a face-covering of the planar embedding of G with 1 < p < O(n), and r is an integer parameter with 1 < r < p. This da ta structure enables us to process each length query in O(v -rlog r + a(n)) t ime and report an actual shortest path in an addit ional O(L) time, where a(n) is the inverse of Ackermann's function. In the worst case, our approach reduces the previously best query t ime by a factor of up to O(n 1 4) if the same amount of space is used. Our technique can also be applied to improve the previous query algorithms for some geometric shortest pa th problems on the plane.