Association for Computing Machinery (ACM), ACM Transactions on Spatial Algorithms and Systems, 3(5), p. 1-41, 2019
DOI: 10.1145/3341818
Full text: Unavailable
In recent years, ridesharing has become a popular model that enables users to share their rides with others. In this article, we introduce a novel ridesharing service, an Activity-aware Ridesharing Group Trip Planning (ARGTP) query , in road networks that exhibits three novel features: (i) ensures a complete trip for visiting more than two locations, (ii) allows visiting both fixed and flexible locations, and (iii) provides true ridesharing services instead of taxilike ridesourcing services by matching a group of riders’ flexible trips with a driver’s fixed trip. A trip visits a point-of-interest (POI) like a bank, restaurant, or supermarket for an activity in between source and destination locations. In a fixed trip, the POI is predetermined (e.g., a specific branch of a bank) and in a flexible trip, the POI is a flexible one (e.g., any branch of a bank). Considering the spatial proximity of the riders’ trips with a driver’s trip, an ARGTP query returns an optimal ridesharing group that minimizes the group cost. We develop the first solution to process ARGTP queries in real time and extend our solution for generalized ARGTP queries with multiple POIs. The efficiency of ARGTP query processing algorithms depends on the number of candidate riders and POIs to be explored. We introduce novel pruning techniques to refine the riders and POI search space. We perform extensive experiments using both real and synthetic datasets to validate the efficiency and effectiveness of our approach and show that it outperforms two baseline approaches with a large margin.