An Efficient Ride-Sharing Framework for Maximizing Shared Route

UM > Faculty of Science and Technology > DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE

Status	已發表Published
	An Efficient Ride-Sharing Framework for Maximizing Shared Route
	Ta, N.; Li, G.; Zhao, T.; Feng, J.; Ma, H.; Gong, Z. G.
	2018-02-01
Source Publication	IEEE Transactions on Knowledge an Engineering
ISSN	1041-4347
Pages	219-232
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.
Keyword	Ride-sharing shared route percentage bigraph matching join-based sharing search-based sharing
URL	View the original
Language	英語English
The Source to Article	PB_Publication
PUB ID	41336
Document Type	Journal article
Collection	DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Recommended Citation GB/T 7714	Ta, N.,Li, G.,Zhao, T.,et al. An Efficient Ride-Sharing Framework for Maximizing Shared Route[J]. IEEE Transactions on Knowledge an Engineering, 2018, 219-232.
APA	Ta, N.., Li, G.., Zhao, T.., Feng, J.., Ma, H.., & Gong, Z. G. (2018). An Efficient Ride-Sharing Framework for Maximizing Shared Route. IEEE Transactions on Knowledge an Engineering, 219-232.
MLA	Ta, N.,et al."An Efficient Ride-Sharing Framework for Maximizing Shared Route".IEEE Transactions on Knowledge an Engineering (2018):219-232.

Files in This Item:
There are no files associated with this item.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Affiliation No.
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh