Optimal assignment and incentive design in the taxi group ride problem

•Develops the modeling framework to devise operational strategy and design incentives for the TGR problem.•Introduces the graph conversion approach to solve the optimal passenger assignment problem as an equivalent graph problem•Develops the heuristic algorithm that solves real-world TGR problem efficiently and effectively, by taking advantage of the structure of IGRG.•Conducts numerical experiments using real-world taxi trip data from three different cities for understanding the effectiveness of TGR, the impact of passenger discount, and the importance of driver subsidy.

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.