In major metropolitan areas such as Los Angeles County, ride-sharing systems can help reduce traffic congestion and increase the efficiency of the transportation system. This research project proposes three different solution approaches for solving the ride share routing problem with flexible pickup and drop-off points. The first is a dynamic programming-based route enumeration procedure that can be used to solve small-sized problems; the other two are branch and price-based heuristics for solving large problems. The researchers first provide a mixed integer nonlinear model for routing and pickup and drop-off points selection which they later decompose into a master and subproblem for solving. To validate the performance of their approaches and gather valuable insights about the ridesharing system, the researchers perform numerical experiments on a San Francisco Taxicab dataset. Results show that the approaches are efficient, solving instances with up to 300 nodes within 130 CPU seconds. For these datasets, incorporating flexible meeting points (i.e., pickup and drop-off points) can reduce the total travel time of the rideshare system by 18%. Sensitivity analysis shows that it can also decrease the time passengers wait time for rides by 43%. The methodologies in this study can help transportation planners design more efficient rideshare systems with less waiting, better passenger service, and less travel time.
