coRide: carpool service with a win-win fare model for large-scale taxicab networks
coRide: carpool service with a win-win fare model for large-scale taxicab networks
复制标题
DOI：
10.1145/2517351.2517361
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
Desheng Zhang;Ye Li;Fan Zhang;Mingming Lu;Yunhuai Liu;T. He
中科院分区：
文献类型：
--
作者：
Desheng Zhang;Ye Li;Fan Zhang;Mingming Lu;Yunhuai Liu;T. He
长期以来，拼车一直承诺通过减少里程来减少汽油消耗。虽然临时拼车已经存在于真实的世界中，通过私人安排，很少有关于这个主题的研究已经完成。在本文中，我们提出了第一个系统的工作，设计，实施和评估拼车服务，称为coRide，在一个大规模的出租车网络，旨在减少总里程减少汽油消耗。我们的coRide系统由三个组件组成，即调度云服务器、乘客客户端和称为TaxiBox的车载定制设备。在coRide设计中，响应于乘客的交付请求，调度云服务器为出租车司机计算具有成本效益的拼车路线，从而降低单个乘客的票价。为了提高coRide的效率，减少里程，我们制定了一个NP-硬路径计算问题，在不同的实际约束。然后，我们提供（i）使用线性规划的最优算法，（ii）具有多项式复杂度的2近似算法，以及（iii）其相应的在线版本。为了鼓励coRide的采用，我们提出了一个双赢的票价模型，作为乘客和司机参与的激励机制。我们使用超过14，000辆出租车的真实的世界数据集对coRide进行评估，结果显示，与地面事实相比，我们的服务可以减少33%的总里程;通过我们的双赢票价模型，我们可以将乘客票价降低49%，同时将司机利润提高76%。
Carpooling has long held the promise of reducing gas consumption by decreasing mileage to deliver co-riders. Although ad hoc carpools already exist in the real world through private arrangements, little research on the topic has been done. In this paper, we present the first systematic work to design, implement, and evaluate a carpool service, called coRide, in a large-scale taxicab network intended to reduce total mileage for less gas consumption. Our coRide system consists of three components, a dispatching cloud server, passenger clients, and an onboard customized device, called TaxiBox. In the coRide design, in response to the delivery requests of passengers, dispatching cloud servers calculate cost-efficient carpool routes for taxicab drivers and thus lower fares for the individual passengers. To improve coRide's efficiency in mileage reduction, we formulate a NP-hard route calculation problem under different practical constraints. We then provide (i) an optimal algorithm using Linear Programming, (ii) a 2 approximation algorithm with a polynomial complexity, and (iii) its corresponding online version. To encourage coRide's adoption, we present a win-win fare model as the incentive mechanism for passengers and drivers to participate. We evaluate coRide with a real world dataset of more than 14,000 taxicabs, and the results show that compared with the ground truth, our service can reduce 33% of total mileage; with our win-win fare model, we can lower passenger fares by 49% and simultaneously increase driver profit by 76%.