An Efficient Ride-Sharing Framework for Maximizing Shared Route
An Efficient Ride-Sharing Framework for Maximizing Shared Route
复制标题
最大化共享路线的高效乘车共享框架
DOI：
10.1109/tkde.2017.2760880
复制
发表时间：
2018-02
影响因子：
8.9
通讯作者：
Zhiguo Gong
中科院分区：
文献类型：
--
作者：
Na Ta;Guoliang Li;Tianyu Zhao;Jianghua Feng;Hanchao Ma;Zhiguo Gong
拼车（RS）在节约能源、缓解交通压力方面具有巨大价值。可以改进现有研究以提高效率。因此，我们提出了一种新的拼车模型，其中每个司机都有一个要求，如果司机与乘客拼车，共享路线百分比（即共享路线的距离与司机总行程距离的比率）超过司机的期望率，例如0.8。我们考虑这个问题的两种变体。第一个考虑多个司机和多个乘客，旨在计算司机-乘客对以最大化总体共享路线百分比（SRP）。我们将此问题建模为最大加权双图匹配问题，其中顶点是驾驶员和骑手，边是驾驶员-骑手对，边权重是驾驶员-骑手的SRP。然而，计算道路网络上大量驾驶员-乘客对的 SRP 值相当昂贵。为了解决这个问题，我们提出了一种有效的方法来修剪许多不必要的驾驶员-乘客对，并避免计算每对的 SRP 值。为了提高效率，我们提出了一种具有误差界限保证的近似方法。基本思想是我们在恒定时间内计算每个驾驶员-乘客对的上限和下限。然后，我们估计图匹配的上限和下限。接下来，我们选择一些司机-乘客对，计算他们的真实最短路线距离，并更新最大图匹配的下限和上限。我们重复上述步骤，直到上限与下限的比率不大于给定的近似速率。第二个考虑多个车手和单个车手，旨在为具有最大 SRP 的车手找到顶级<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives> <inline-graphic xlink:href="li-ieq1-2760880.gif"/></alternatives></inline-formula> 车手。我们首先修剪大量不能满足SRP要求的驱动程序。然后，我们提出了一种最佳优先算法，该算法逐步选择最有可能出现在前 <inline-formula> <tex-math notation="LaTeX">$k$</tex-math><alternatives><inline-graphic xlink:href="li-ieq2-2760880.gif"/></alternatives> </inline-formula> 结果中的驱动程序，并修剪不能出现在结果中的驱动程序。 top-<inline-formula><tex-math notation="LaTeX"> $k$</tex-math><alternatives><inline-graphic xlink:href="li-ieq3-2760880.gif"/></alternatives></inline-formula> 结果。对现实世界数据集的大量实验证明了我们方法的优越性。
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-<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives> <inline-graphic xlink:href="li-ieq1-2760880.gif"/></alternatives></inline-formula> 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-<inline-formula> <tex-math notation="LaTeX">$k$</tex-math><alternatives><inline-graphic xlink:href="li-ieq2-2760880.gif"/></alternatives> </inline-formula> results and prunes the drivers that cannot be in the top-<inline-formula><tex-math notation="LaTeX"> $k$</tex-math><alternatives><inline-graphic xlink:href="li-ieq3-2760880.gif"/></alternatives></inline-formula> results. Extensive experiments on real-world datasets demonstrate the superiority of our method.
登录
查看更多内容
DOI：
10.1109/icde.2016.7498229
发表时间：
2016-05
期刊：
2016 IEEE 32nd International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Huiqi Hu;Yudian Zheng;Z. Bao;Guoliang Li;Jianhua Feng;Reynold Cheng
通讯作者：
Huiqi Hu;Yudian Zheng;Z. Bao;Guoliang Li;Jianhua Feng;Reynold Cheng
DOI：
10.1109/icde.2016.7498228
发表时间：
2016-05
期刊：
2016 IEEE 32nd International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Yongxin Tong;Jieying She;Bolin Ding;Libin Wang;Lei Chen
通讯作者：
Yongxin Tong;Jieying She;Bolin Ding;Libin Wang;Lei Chen
DOI：
10.2307/3616070
发表时间：
1973-12
期刊：
The Mathematical Gazette
影响因子：
--
作者：
K. Fraughnaugh
通讯作者：
K. Fraughnaugh
DOI：
10.1145/2996913.2996974
发表时间：
2016-10
期刊：
Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
影响因子：
--
作者：
M. Asghari;Dingxiong Deng;C. Shahabi;Ugur Demiryurek;Yaguang Li
通讯作者：
M. Asghari;Dingxiong Deng;C. Shahabi;Ugur Demiryurek;Yaguang Li
DOI：
10.1007/978-3-8348-9329-1_2
发表时间：
2010
期刊：
--
影响因子：
--
作者：
M. Loebl
通讯作者：
M. Loebl