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.
In the @math problem, given a cluster of co-located sources, and another of co-located destinations, we are to find an optimal pair of end-stops for a vehicle, which will carry the passengers from the source cluster to the destination cluster. Users demanding a vehicle, using a location-based service, do not automatically form clusters. The initial task is to group them in a way that satisfies our input requirements. In this paper, we do not provide an algorithm for grouping passengers. Instead, we assume that an existing clustering algorithm such as @cite_25 , which partitions the queries into batches, has already performed the grouping. @cite_25 divides the path queries into groups, where each group comprises the queries from a source cluster to a destination cluster. We take each output query group of @cite_25 as input to our algorithm and focus on determining the optimal end-stoppages for the corresponding vehicle.
@cite_25
68380453
The advancement of mobile technologies and map-based applications enables a user to access a wide variety of location-based services that range from information queries to navigation systems. Due to the popularity of map-based applications among the users, the service provider often requires to answer a large number of simultaneous (or contemporary) queries. Thus, processing queries efficiently on spatial networks (i.e., road networks) have become an important research area in recent years. In this paper, we focus on path queries that find the shortest path between a source and a destination of the user. In particular, we address the problem of finding the shortest paths for a large number of simultaneous path queries in road networks. Traditional systems that consider one query at a time are not suitable for many applications due to high computational and service cost overhead. We propose an efficient group based approach that provides a practical solution with reduced cost. The key concept of our approach is to group queries that share a common travel path and then compute the shortest path for the group. Experimental results show the effectiveness and efficiency of our group based approach.