UM  > 科技學院  > 電腦及資訊科學系
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
2018-10-24
Source PublicationProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
Pages1795-1796
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
DOI10.1109/ICDE.2018.00255
URLView the original
Language英語
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
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.
Related Services
Recommend this item
Bookmark
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.