Carpooling options from companies like Uber and Lyft could reduce the number of vehicles on the road 75 percent without significantly impacting travel time.
The new algorithm shows that 3,000 four-passenger cars could serve 98 percent of NYC taxi demand. This suggests that ride-sharing options from Uber and Lyft could play a big role in reducing congestion, and even helping with pollution and energy usage.
Using data from 3 million taxi rides, the new algorithm works in real-time to reroute cars based on incoming requests, and can also proactively send idle cars to areas with high demand - a step that speeds up service 20 percent, according to Rus.
A key challenge was to develop a real-time solution that considers the thousands of vehicles and requests at once,” says Professor Daniela Rus who led the research. “We can do this in our method because that first step enables us to understand and abstract the road network at a fine level of detail.”
To be sure, companies like Uber and Lyft are designing similar algorithms (though they’re probably considered trade secrets), but seeing it in action gives us an idea of how much cities could change once we have fleets of self-driving cars at our disposal. “The system is particularly suited to autonomous cars,” said Rus, “since it can continuously reroute vehicles based on real-time requests.”
A few hundred to a few thousand robotic cars would be able to service much of the transportation in most cities
PNAS - On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment
Ride-sharing services can provide not only a very personalized mobility experience but also ensure efficiency and sustainability via large-scale ride pooling. Large-scale ride-sharing requires mathematical models and algorithms that can match large groups of riders to a fleet of shared vehicles in real time, a task not fully addressed by current solutions. We present a highly scalable anytime optimal algorithm and experimentally validate its performance using New York City taxi data and a shared vehicle fleet with passenger capacities of up to ten. Our results show that 2,000 vehicles (15% of the taxi fleet) of capacity 10 or 3,000 of capacity 4 can serve 98% of the demand within a mean waiting time of 2.8 min and mean trip delay of 3.5 min.
Ride-sharing services are transforming urban mobility by providing timely and convenient transportation to anybody, anywhere, and anytime. These services present enormous potential for positive societal impacts with respect to pollution, energy consumption, congestion, etc. Current mathematical models, however, do not fully address the potential of ride-sharing. Recently, a large-scale study highlighted some of the benefits of car pooling but was limited to static routes with two riders per vehicle (optimally) or three (with heuristics). We present a more general mathematical model for real-time high-capacity ride-sharing that
(i) scales to large numbers of passengers and trips and
(ii) dynamically generates optimal routes with respect to online demand and vehicle locations.
The algorithm starts from a greedy assignment and improves it through a constrained optimization, quickly returning solutions of good quality and converging to the optimal assignment over time. We quantify experimentally the tradeoff between fleet size, capacity, waiting time, travel delay, and operational costs for low- to medium-capacity vehicles, such as taxis and van shuttles. The algorithm is validated with ∼3 million rides extracted from the New York City taxicab public dataset. Our experimental study considers ride-sharing with rider capacity of up to 10 simultaneous passengers per vehicle. The algorithm applies to fleets of autonomous vehicles and also incorporates rebalancing of idling vehicles to areas of high demand. This framework is general and can be used for many real-time multivehicle, multitask assignment problems.