Mathematical model of San Francisco Taxi Data Showed Dynamic Rideshare Routing Could Reduce the Total Travel Time of the Rideshare System by 18 Percent.

Assessment of the Effect on Flexible Pick up and Drop off Points on Rideshare System Yield Mobility Benefits.

Date Posted

The Ridesharing Routing Problem with Flexible Pickup and Drop-off Points

Summary Information

Ride-sharing systems have the potential to help reduce traffic congestion and increase the efficiency of the transportation system, especially in metropolitan areas. This study proposed three different approaches to solve the ride share routing problem using flexible pickup and drop-off points with consideration of High Occupancy Lanes (HOV) and the time limits of passengers and drivers. These approaches employed dynamic programming-based route enumeration procedure and optimization-based heuristics. To evaluate the effectiveness of these approaches, the researchers employed a San Francisco Taxicab dataset, comprising the origin and destination of approximately 650,000 taxicab rides collected from 5/17/2008 - 6/10/2008. 


The researchers created a Mixed Integer Nonlinear Program (MINLP) for this study, which was divided into two smaller problems: selecting a route and choosing pickup and drop-off points. To solve this model, three different approaches were used. The first approach used an exhaustive route enumeration algorithm (REA), which generated all feasible routes and corresponding pickup and drop-off points. The second approach was a branch and price-based optimization algorithm (a method of combinatorial optimization for solving integer linear programming) that simultaneously selected routes and pickup/drop-off points. The third approach used the same algorithm but with a sequential process for choosing routes and pickup/drop-off points.



  • The study found that the inclusion of flexible pickup and drop-off points in a rideshare system could result in a 18 percent reduction in total travel time.
  • Sensitivity analysis showed that the implementation of such a system could also decrease waiting times for rides by 43 percent. 
Goal Areas
Results Type
Deployment Locations