Search

In its current form, ride-sharing is responsible for a small fraction of traffic load compared to other transportation modes, especially private vehicles. As its benefits became more evident, and obstacles, e.g., lack of liability legislation, that may hinder its larger scale adoption are being overcome, ride-sharing will be a more common mode of transportation. In particular, autonomous vehicles (AVs) are showing their proficiency on the roads, which may also catalyze ride-sharing ubiquity. For example, while an AV owner is at work, he may find it appealing to offer his AV as a service or rent it to Uber so that the vehicle serves others’ transportation requests. Furthermore, this disruptive technology is backed up by companies like Google (Waymo), Tesla, and Uber. Therefore, ride-sharing will soon become a source of traffic congestion itself. In this article, we present an efficient congestion-aware ride-sharing algorithm which, instead of finding optimal travel plans based on traffic load generated by other means of transportation, it computes optimal travel plans for thousands of ride-sharing requests within a time interval. Note that in this problem, an optimal travel plan for a group of requests may affect an already computed travel plan for another concurrent group of requests, therefore plans cannot be isolated from each other.

Nowadays, people can access location-based services (LBSs) as a group via mobile devices to plan their daily activities with friends and relatives. In this article, we introduce an important class of group-oriented LBSs, group optimal accessible location (GOAL) queries that enable users to identify the location of a point of interest (POI) that has the minimum total distance to a given set of paths. GOAL queries have many applications, such as the selection of an optimal location for group meet-ups or for a mobile facility such as a food truck. In a GOAL query, each trip or path is represented as a set of line segments, and the distance of a POI from a path is computed as the minimum distance of the POI to any line segment of the path. We develop an efficient approach to evaluate GOAL queries. The novelty of our GOAL query processing algorithm in contrast to other spatial query processing algorithms is the reformulation of a GOAL query by considering only a subset of path segments from the given set of paths, which is also the key factor behind the efficiency of our proposed algorithm. We exploit geometric properties and develop pruning techniques to eliminate both POIs and path segments that cannot provide the optimal solution for a GOAL query. Our experimental results demonstrate that we provide a readily deployable solution for real-life applications.