CoRide: Carpool service with a win-win fare model for large-scale taxicab networks

Desheng Zhang, Ye Li, Fan Zhang, Mingming Lu, Yunhuai Liu, Tian He

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Citations (Scopus)

Abstract

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%.

Original languageEnglish (US)
Title of host publicationSenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems
PublisherAssociation for Computing Machinery
ISBN (Print)9781450320276
DOIs
StatePublished - Jan 1 2013
Externally publishedYes
Event11th ACM Conference on Embedded Networked Sensor Systems, SenSys 2013 - Rome, Italy
Duration: Nov 11 2013Nov 15 2013

Publication series

NameSenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems

Other

Other11th ACM Conference on Embedded Networked Sensor Systems, SenSys 2013
CountryItaly
CityRome
Period11/11/1311/15/13

Fingerprint

Taxicabs
Servers
Approximation algorithms
Gases
Linear programming
Profitability
Polynomials
Costs

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications

Cite this

Zhang, D., Li, Y., Zhang, F., Lu, M., Liu, Y., & He, T. (2013). CoRide: Carpool service with a win-win fare model for large-scale taxicab networks. In SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems [9] (SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems). Association for Computing Machinery. https://doi.org/10.1145/2517351.2517361
Zhang, Desheng ; Li, Ye ; Zhang, Fan ; Lu, Mingming ; Liu, Yunhuai ; He, Tian. / CoRide : Carpool service with a win-win fare model for large-scale taxicab networks. SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems. Association for Computing Machinery, 2013. (SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems).
@inproceedings{60fd7af03c064609953d80c476fd86f9,
title = "CoRide: Carpool service with a win-win fare model for large-scale taxicab networks",
abstract = "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{\%}.",
author = "Desheng Zhang and Ye Li and Fan Zhang and Mingming Lu and Yunhuai Liu and Tian He",
year = "2013",
month = "1",
day = "1",
doi = "https://doi.org/10.1145/2517351.2517361",
language = "English (US)",
isbn = "9781450320276",
series = "SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems",
publisher = "Association for Computing Machinery",
booktitle = "SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems",

}

Zhang, D, Li, Y, Zhang, F, Lu, M, Liu, Y & He, T 2013, CoRide: Carpool service with a win-win fare model for large-scale taxicab networks. in SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems., 9, SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems, Association for Computing Machinery, 11th ACM Conference on Embedded Networked Sensor Systems, SenSys 2013, Rome, Italy, 11/11/13. https://doi.org/10.1145/2517351.2517361

CoRide : Carpool service with a win-win fare model for large-scale taxicab networks. / Zhang, Desheng; Li, Ye; Zhang, Fan; Lu, Mingming; Liu, Yunhuai; He, Tian.

SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems. Association for Computing Machinery, 2013. 9 (SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - CoRide

T2 - Carpool service with a win-win fare model for large-scale taxicab networks

AU - Zhang, Desheng

AU - Li, Ye

AU - Zhang, Fan

AU - Lu, Mingming

AU - Liu, Yunhuai

AU - He, Tian

PY - 2013/1/1

Y1 - 2013/1/1

N2 - 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%.

AB - 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%.

UR - http://www.scopus.com/inward/record.url?scp=84905684509&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905684509&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/2517351.2517361

DO - https://doi.org/10.1145/2517351.2517361

M3 - Conference contribution

SN - 9781450320276

T3 - SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems

BT - SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems

PB - Association for Computing Machinery

ER -

Zhang D, Li Y, Zhang F, Lu M, Liu Y, He T. CoRide: Carpool service with a win-win fare model for large-scale taxicab networks. In SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems. Association for Computing Machinery. 2013. 9. (SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems). https://doi.org/10.1145/2517351.2517361