Large-Scale Real-time Ride Sharing Systems


Ride-hailing systems have increased congestion in many cities. For instance, a recent study has shown that, between 2010 and 2016, weekday vehicle hours of delay increased by 62% compared to 22% in a counterfactual 2016 scenario without ride hailing. Large-scale ride-sharing can change the equation. recently, researchers at MIT have shown that 98% of the riders using NYC taxi and limousine services in NY city can be served with 3,000 vehicles and an average wait of 3.8 minutes (NYC has currently about 12,000 taxis). This project aims at designing large-scale ride-sharing systems that serves all the rides with short waiting times and small deviation compared to the shortest paths of the riders. The underlying technology combines optimization, machine learning, and model-predictive control.

"Ride Sharing Optimization for New York City"
Play Video
Start Video Playback



Recent results using a dedicated optimization algorithm has shown that all riders can be served with 2,000 vehicles, an average wait time of 2.2 minutes, and an average deviation of 0.62 minute compared to a direct trip. The figures above  depict some of these results and report the average waiting times and average vehicle occupancy for varying numbers of customers and fleet sizes during peak hours. Interestingly, the average occupancy is around 1.3 as soon as there are more than 2,000 vehicles in the fleet. This indicates that ride-sharing does not typically lead to overcrowded vehicles.





Real-Time Dispatching of Large-Scale Ride-Sharing Systems: Integrating Optimization, Machine Learning, and Model Predictive Control. Connor Riley, Pascal Van Hentenryck, and Enpeng Yuan. In the Proceedings of 29th International Joint Conference on Artificial Intelligence (IJCAI-20), Tokyo, Japan 2020.


On-Demand Mobility Systems, Pascal Van Hentenryck, ISE Magazine, Fall 2019.

A Column Generation for Online Ride-Sharing Services. Connor Riley, Antoine Legrain, and Pascal Van Hentenryck. In the Proceedings of 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2019), Thessaloniki, Greece, June 4–7, 2019.