An efficient ride-sharing framework for maximizing shared Routes
Ta N.1; Li G.4; Zhao T.4; Feng J.4; Ma H.3; Gong Z.2
Source PublicationProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
AbstractRide-sharing (RS) has great values in saving energy and alleviating traffic pressure. In this paper, we propose a new ride-sharing model, where each driver requires that the shared route percentage (SRP, the ratio of the shared route's distance to the driver's total traveled distance) exceeds her expected rate (e.g., 0.8) when sharing with a rider. We consider two variants of this problem. The first considers multiple drivers and multiple riders, and aims to compute a set of driver-rider pairs to maximize the overall SRP. We model this problem as the maximum weighted bigraph matching problem. We propose an effective exact algorithm, and an efficient approximate solution with error-bound guarantee. 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 devise pruning techniques and propose a best-first algorithm to progressively selects drivers with high probability to be in the top-k results.
KeywordBigraph matching Join based sharing Ride sharing Search based sharing Shared route percentage
URLView the original
Fulltext Access
Citation statistics
Cited Times [WOS]:0   [WOS Record]     [Related Records in WOS]
Document TypeConference paper
Affiliation1.Renmin University of China
2.Universidade de Macau
3.Washington State University Pullman
4.Tsinghua University
Recommended Citation
GB/T 7714
Ta N.,Li G.,Zhao T.,et al. An efficient ride-sharing framework for maximizing shared Routes[C],2018:1795-1796.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Ta N.]'s Articles
[Li G.]'s Articles
[Zhao T.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Ta N.]'s Articles
[Li G.]'s Articles
[Zhao T.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Ta N.]'s Articles
[Li G.]'s Articles
[Zhao T.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.