Stochastic Ridesharing System with Flexible Pickup and Drop-off

Ridesharing can help reduce traffic congestion, greenhouse gas emissions and increase accessibility to transportation in major metropolitan areas across the United States. A robust rideshare system needs to take uncertainties such as traffic congestion and passenger cancellations into account. In this report, the authors propose a data-driven stochastic rideshare system that integrates those sources of uncertainties. Instead of assuming a probability distribution, the approach learns the underlying distribution in travel times and passenger cancellations from historical data. The authors first provide a mathematical model of the problem. Later they propose a stochastic average approximation approach for solving the routing and flexible pickup and drop-off selection problem. They also propose a Branch-and-Price heuristic and Adaptive Large Neighborhood Search-basedmetaheuristic to solve the underlying rideshare routing problem. To validate the approach, the authors construct test cases based on the New York City taxicab dataset. Numerical results show that the proposed branch and price-based solution approach can efficiently solve small instances while being close to the true optimum. On the other hand, the ALNS-based approach can solve medium to large instances with a small computational time budget while being robust to uncertainties. The proposed approach can help transportation officials and rideshare planners design more robust rideshare systems to alleviate traffic congestion in California. View the NCST Project Webpage