An efficient ride-sharing framework for maximizing shared Routes

doi:10.1109/ICDE.2018.00255

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

	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 Publication	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
Pages	1795-1796
Abstract	Ride-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.
Keyword	Bigraph matching Join based sharing Ride sharing Search based sharing Shared route percentage
DOI	10.1109/ICDE.2018.00255
URL	View the original
Language	英語
Fulltext Access	View Full-Text via DOI View Full-Text via Web of Science View Full-Text via Scopus
Citation statistics	Cited Times [WOS]:0 [WOS Record] [Related Records in WOS]
Document Type	Conference paper
Collection	DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation	1.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.

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：	*
Institution:
Verification Code:	Refresh

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