| 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 | |
| Citation statistics | |
| 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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment