On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment

By Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, Daniela Rus. 2017

1,231 citations recorded by the source corpus.

Significance 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.

Subfields: Automotive Engineering, Building and Construction, Marketing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Building and Construction

In Marketing

Citations in the corpus

Swarm of micro flying robots in the wild (2022, background): “Such a scheme can seamlessly connect to high-level decision-making and task assignment modules with outputs that are always preferred goals for each robot (54, 55).”
Does ride-hailing increase or decrease vehicle kilometers traveled (VKT)? A simulation approach for Santiago de Chile (2020, background): “Alonso-Mora et al. (2017) only study the substitution between current taxi trips and on-demand shared services to conclude that such a move would provide large savings in fleet size and congestion.”
Creative destruction of the sharing economy in action: The case of Uber (2018, background): “A recent MIT study (Alonso-Mora et al., 2017) examined how ride-sharing could impact the transportation system in New York City, and found that such a technology-enabled ride-sharing business model with optimized algorithms could radically reduce traffic congestion up to 75%.”
Dynamic pricing and matching in ride‐hailing platforms (2019, neutral): “We refer readers to Alonso-Mora et al. (2017) and Bertsimas et al. (2018) for some modeling”
Short-Term Forecasting of Passenger Demand under On-Demand Ride Services: A Spatio-Temporal Deep Learning Approach (2017, background): “Recently, the on-demand ride-sharing market and the optimal assignment strategies have also attracted researchers’ attentions(Alonso-Mora et al., 2017).”
Planning and Decision-Making for Autonomous Vehicles (2018, background): “(143), who introduced an anytime-optimal method for request matching and dynamic vehicle routing in low- and high-capacity vehicles.”
The science of science: from the perspective of complex systems (2017, background): “, spatial epidemic control [26], energy consumption and supply [27] and ride-sharing services [28].”
Addressing the minimum fleet problem in on-demand urban mobility (2018, background): “The type of shareability network introduced here is profoundly different from the type studied previously: it models the sharing of vehicles, whereas previous networks 7–9 modelled the sharing of rides.”
Can sharing a ride make for less traffic? Evidence from Uber and Lyft and implications for cities (2021, background): “Even with the high trip densities of New York City, waiting times would average 2.8 min with a mean trip delay of 3.5 min in one study (Alonso-Mora et al., 2017).”