Carpooling has long held the promise of reducing gas consumption by decreasing mileage to deliver coriders. Although ad hoc carpools already exist in the real world through private arrangements, little research on the topic has been done. In this article, 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 an NP-hard route calculation problem under different practical constraints. We then provide (1) an optimal algorithm using Linear Programming, (2) a 2-approximation algorithm with a polynomial complexity, and (3) its corresponding online version with a linear complexity. To encourage  coRide ’s adoption, we present a win-win fare model as the incentive mechanism for passengers and drivers to participate. We test the performance of  coRide  by a comprehensive evaluation with a real-world trial implementation and a data-driven simulation with 14,000 taxi data from the Chinese city Shenzhen. The results show that compared with the ground truth, our service can reduce 33p of total mileage; with our win-win fare model, we can lower passenger fares by 49p and simultaneously increase driver profit by 76p.
['Desheng Zhang', 'Tian He', 'Fan Zhang', 'Mingming Lu', 'Yunhuai Liu', 'Haengju Lee', 'Sang Hyuk Son']
Carpooling Service for Large-Scale Taxicab Networks