No icon

An Efficient Ride-Sharing Framework for Maximizing Shared Route

An Efficient Ride-Sharing Framework for Maximizing Shared Route

Abstract:

Ride-sharing (RS) has great values in saving energy and alleviating traffic pressure. Existing studies can be improved for better efficiency. Therefore, we propose a new ride-sharing model, where each driver has a requirement that if the driver shares a ride with a rider, the shared route percentage (i.e., the ratio of the shared route’s distance to the driver’s total travel distance) exceeds an expectation rate of the driver, e.g., 0.8. We consider two variants of this problem. The first considers multiple drivers and multiple riders and aims to compute driver-rider pairs to maximize the overall shared route percentage (SRP). We model this problem as the maximum weighted bigraph matching problem, where the vertices are drivers and riders, edges are driver-rider pairs, and edge weights are driver-rider’s SRP. However, it is rather expensive to compute the SRP values for large numbers of driver-rider pairs on road networks. To address this problem, we propose an efficient method to prune many unnecessary driver-rider pairs and avoid computing the SRP values for every pair. To improve the efficiency, we propose an approximate method with error bound guarantee. The basic idea is that we compute an upper bound and a lower bound for each driver-rider pair in constant time. Then, we estimate an upper bound and a lower bound of the graph matching. Next, we select some driver-rider pairs, compute their real shortest-route distance, and update the lower and upper bounds of the maximum graph matching. We repeat above steps until the ratio of the upper bound to the lower bound is not larger than a given approximate rate. The second considers multiple drivers and a single rider and aims to find the top-k drivers for the rider with the largest SRP. We first prune a large number of drivers that cannot meet the SRP requirements. Then, we propose a best-first algorithm that progressively selects the drivers with high probability to be in the top-k results and prunes the drivers that cannot be in the top-k results. Extensive experiments on real-world datasets demonstrate the superiority of our method.

 

 

Existing System:

The performance is rather crucial in ride sharing because the riders will not wait for long time and we require to compute the driver-rider pairs within a minute. To meet such requirement, we propose an efficient ride-sharing framework. For Join-basedRS, we model this problemas the maximum weighted bigraph matching problem, where the vertices are drivers and riders, edges are driver-rider pairs, and edge weights are driver-rider’ SRP values. However it is rather expensive to compute the SRP values for large numbers of driver-rider pairs on road networks.

Proposed System:

We propose an efficient method to prune many unnecessary driver-rider pairs and avoid computing the SRP values for such pairs. To further improve the efficiency, we propose an approximate method with any given approximate rate. The basic idea is that we compute an upper bound and a lower bound for each driver-rider pair in constant time. Then we estimate an upper bound and a lower bound of the maximum graph matching. Next we select some driver-rider pairs, compute their real shortest-route distances, and update the lower bound and upper bound of the graph matching.We repeat the above steps until the ratio of the upper bound to the lower bound is not larger than the given approximate rate.

Comment As:

Comment (0)