UM
An Efficient Ride-Sharing Framework for Maximizing Shared Route
Ta, Na; Li, Guoliang; Zhao, Tianyu; Feng, Jianhua; Ma, Hanchao; Gong, Zhiguo
2018-02
Source PublicationIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
ISSN1041-4347
Volume30Issue:2Pages:219-233
AbstractRide-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.
KeywordRide-sharing shared route percentage bigraph matching join-based sharing search-based sharing
DOI10.1109/TKDE.2017.2760880
URLView the original
Indexed BySCI
Language英语
WOS Research AreaComputer Science ; Engineering
WOS SubjectComputer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS IDWOS:000422711800002
PublisherIEEE COMPUTER SOC
The Source to ArticleWOS
Fulltext Access
Citation statistics
Cited Times [WOS]:8   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Recommended Citation
GB/T 7714
Ta, Na,Li, Guoliang,Zhao, Tianyu,et al. An Efficient Ride-Sharing Framework for Maximizing Shared Route[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2018,30(2):219-233.
APA Ta, Na,Li, Guoliang,Zhao, Tianyu,Feng, Jianhua,Ma, Hanchao,&Gong, Zhiguo.(2018).An Efficient Ride-Sharing Framework for Maximizing Shared Route.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,30(2),219-233.
MLA Ta, Na,et al."An Efficient Ride-Sharing Framework for Maximizing Shared Route".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 30.2(2018):219-233.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Ta, Na]'s Articles
[Li, Guoliang]'s Articles
[Zhao, Tianyu]'s Articles
Baidu academic
Similar articles in Baidu academic
[Ta, Na]'s Articles
[Li, Guoliang]'s Articles
[Zhao, Tianyu]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Ta, Na]'s Articles
[Li, Guoliang]'s Articles
[Zhao, Tianyu]'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.