Optimal assignment and incentive design in the taxi group ride problem

Xinwu Qian, Wenbo Zhang, Satish V. Ukkusuri and Chao Yang

Transportation Research Part B: Methodological, 2017, vol. 103, issue C, 208-226

Abstract: Taxi group ride (TGR) is one popular case of taxi ridesharing, where passenger trips with nearby origins and destinations and similar departure time are grouped into a single ride. The study investigates theoretical and practical aspects of TGR implementation in real world. In particular, two essential problems on operation strategy and policy making of TGR are examined. First, we investigate the optimal assignment of a set of passengers for the sake of maximizing total saved travel miles. Second, we analyze different behaviors of passengers and drivers in participating taxi group rides, and explore the best incentives for TGR in order to maximize efficiency under optimal assignment. The optimal assignment is formulated as an integer linear programming problem and is further converted into an equivalent graph problem. While the problem is NP-hard, efficient algorithms are needed for real-world on-line implementations. We develop an exact algorithm and a heuristic algorithm to solve the TGR problem, and compare the results with a bounded-error greedy algorithm. The numerical experiments suggest that the heuristic algorithm is capable of solving real-world TGR instances efficiently with good solution quality. To explore the best incentives for grouped taxi rides, comprehensive numerical experiments are conducted using taxi trip data from New York City (US), Wuhan (China), and Shenzhen (China). Our numerical results show that over 47% of the total taxi trip mileage may be saved if proper level of incentives are provided and if passengers are matched optimally.

Keywords: Taxi group ride; Optimal assignment; Passenger discount; Driver subsidy; Heuristic algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261516306166
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:103:y:2017:i:c:p:208-226

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2017.03.001

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().