Future transport systems: On-Demand Ridepooling
About the Project
On-demand mobility systems are expanding worldwide. Ride pooling services are transforming urban mobility as they allow several passengers to share a vehicle when traveling along similar routes. While most ride-pooling services currently focus on drivers to operate these vehicles, there is a push in the industry towards self-driving vehicles which can provide safe, reliable and affordable transporation. In this project, the algorithmic and operational challenges of such a technology is explored with a goal to help improve public transport.
One contribution of this project was a study into understanding user benefit by adopting ride pooling services. This is done by building a mathematical function where the added travel time and discomfort have to be compensated by a price discount. This approach is then used in a series of experiments which highlighted that distance savings of the magnitude previously shown in research can only be obtained based on the user willingness to share and the discounts offered to them. If a user is unwilling to share their ride, a higher discount rate might be needed which is higher than the rate currently offered by such services. This highlights the need for future research to look into exploration of advanced discount mechanisms and demand distributions.
This project also introduced a highly scalable anytime optimal algorithm for ride-sharing which looks at using a fleet of vehicles with varying passenger capacities to assign them to matched passengers and rebalancing this fleet to service demand. In contrast to previous research which is limited to small problem instances, the proposed method is suited for much larger cases such as the entirety of New York City with thousands of vehicles, requests and road segments. Experimental results are conducted using a public dataset from New York with around 3 million rides. The results show that a fleet of just 2000 vehicles was sufficient to meet 98% of the demand with low waiting time and delays.
Project Demonstrations
Funding & Partners
This project was funded in part by Didi Udian Technologies Shenzhen.
Related Publications
What do walking and e-hailing bring to scale economies in on-demand mobility?
Kenan Zhang, Javier Alonso-Mora, Andres Fielbaum.
In Transportation Research Part B: Methodological, 2025.
This study investigates the impact of walking and e-hailing on the scale economies of on-demand mobility services. An analytical framework is developed to i) explicitly characterize the physical interactions between passengers and vehicles in the matching and pickup processes, and ii) derive the closed-form degree of scale economies (DSE) to quantify scale economies. The general model is then specified for conventional street-hailing and e-hailing, with and without walking before pickup and after dropoff. We show that, under a system-optimum fleet size, the market always exhibits economies of scale regardless of the matching mechanism and the walking behaviors, though the scale effect diminishes as passenger demand increases. Yet, street-hailing and e-hailing show different scale economies in their matching process. While street-hailing matching shows a constant DSE of two, e-hailing matching is more sensitive to demand and its DSE diminishes to one when passenger competition emerges. Walking, on the other hand, has mixed effects on the scale economies: while the reduced pickup and in-vehicle times bring a positive scale effect, the extra walking time and possible concentration of vacant vehicles and waiting passengers on streets negatively affect scale economies. All these analytical results are validated through agent-based simulations on Manhattan with real-life demand patterns.
Improving public transportation via line-based integration of on-demand ridepooling
Andres Fielbaum, Alejandro Tirachini, Javier Alonso-Mora.
In Transportation Research Part A: Policy and Practice, 2024.
Local motion planning is a heavily researched topic in the field of robotics with many promising algorithms being published every year. However, it is difficult and time- consuming to compare different methods in the field. In this paper, we present localPlannerBench, a new benchmarking suite that allows quick and seamless comparison between local motion planning algorithms. The key focus of the project lies in the extensibility of the environment and the simulation cases. Out-of-the-box, localPlannerBench already supports many simulation cases ranging from a simple 2D point mass to full-fledged 3D 7DoF manipulators, and it's straightforward to add your own custom robot using a URDF file. A post-processor is built-in that can be extended with custom metrics and plots. To integrate your own motion planner, simply create a wrapper that derives from the provided base class. Ultimately we aim to improve the reproducibility of local motion planning algorithms and encourage standardized open-source comparison.
Beyond the last mile: different spatial strategies to integrate on-demand services into public transport in a simplified city
Andres Fielbaum, Sergio Jara-Díaz, Javier Alonso-Mora.
In Public Transport, 2024.
Integrating on-demand services into public transport networks might be the best way to face the current situation in which these new technologies have increased congestion in most cities. When cooperating with on-demand services rather than competing with them, public transport would not risk losing users, and could attract some passengers from private modes thanks to an increased quality of service. This fact has engendered a growing literature discussing how to design such an integrated system. However, all of that research has imposed that on-demand mobility is to solve the so-called “last-mile problem”, serving only as a feeder that connects the exact origins/destinations with the traditional public transit network. As it induces a large number of transfers and it precludes some scale-effects to be triggered, in this paper we challenge that imposition and investigate if this is the best spatial integration strategy. To do so, we study a simplified linear city in a morning peak situation, where we propose seven different line structures, all of them combining a traditional fixed line with on-demand ride-pooling (ODRP): three direct structures, where ODRP can serve full trips, three semi-direct, where a single ODRP vehicle can serve the largest part of a trip, and a base case in which ODRP is restricted to the first and final legs only. Our results show that the base case is optimal only under very specific demand patterns, or when transfer penalties are disregarded. Our analytical approach reveals relevant operational aspects of such integrated systems: namely, that the base case can help increase directness (diminishing detours), and that ODRP can help shorten the routes of the fixed services to decrease operator costs.
Design of mixed fixed-flexible bus public transport networks by tracking the paths of on-demand vehicles
Andres Fielbaum, Javier Alonso-Mora.
In Transportation Research Part C: Emerging Technologies, 2024.
On-demand ridepooling (ODRP) vehicles follow routes that are fully flexible. However, when the system does not provide door-to-door service and users can be asked to walk, their paths tend to concentrate, particularly along main streets that connect highly demanded areas of the city. These frequently travelled segments are hence useful to multiple passengers, which can be used as an indicator that it would be efficient to allocate a fixed public transport line there. In this paper, we formalise this idea and propose a novel method to design a public transport network, where bus fixed lines are combined with ODRP. Given a network and a transport demand, we first simulate how to serve it using only ODRP with walking. For this, we employ a state-of-the-art assignment algorithm, and take as output the resulting users' paths. These paths are then processed by a tailored algorithm to create fixed lines where the paths accumulate the most. Users who do not have an available fixed line (i.e., those whose paths were barely shared) are served by ODRP in the mixed system. Simulations using real-life data from Utrecht, The Netherlands, and the Sunshine Coast, Australia, reveal the merits of our method compared to several benchmarks. Crucially, our method builds a small number of fixed lines while still serving the majority of the demand through them. This study contributes not only to the design of public transport networks, but also to the understanding of the patterns that naturally appear in intrinsically flexible mobility systems.
Economies and diseconomies of scale in on-demand ridepooling systems
A. Fielbaum, A. Tirachini, J. Alonso-Mora.
In Economics of Transportation, 2023.
We analyse the sources of economies and diseconomies of scale in On-Demand Ridepooling (ODRP), disen- tangling three effects: when demand grows, average costs are reduced due to i) a larger fleet that diminishes waiting and walking times (Mohring Effect), and ii) matching users with more similar routes (Better-matching Effect). A counter-balance force (Extra-detour Effect), occurs when iii) the number of passengers per vehicle in- creases and users face longer detours. At low demand levels, there is little sharing and the Mohring effect pre- vails; as demand grows, more passengers per vehicle push for the Extra-detour Effect to dominate; eventually, vehicles run at capacity, and the Better-matching Effect prevails. The last two effects are specific to ODRP as the routes are not fixed but adapted online. Our simulations show that considering both users’ and operators’ costs, scale economies prevail, and that ODRP with human-driven vehicles and walks allowed has total costs similar to door-to-door systems with driverless vehicles.
Ride-pooling adoption, efficiency and level of service under alternative demand, behavioural and pricing settings
A. de Ruijter, O. Cats, J. Alonso-Mora, S. Hoogendoorn.
In Transportation Planning and Technology, 2023.
Previous studies into the potential benefits of ride pooling failed to account for the trade-off that users likely make when considering a shared ride. We address this shortcoming by formulating user net benefit stemming from pooling as a compensatory function where the additional travel time and on-board discomfort need to be compensated by the price discount for a traveller to choose a pooled ride over a private ride. The proposed formulation is embedded in a method for matching travel requests and vehicles. We conduct a series of experiments investigating how the potential of ride-pooling services depends on demand characteristics, user preferences and the pricing policy adopted by the service provider. Our results suggest that the total vehicle mileage savings found by previous studies is only attainable when users are very willing to share their ride (i.e. attach low premium to private rides) and are offered a 50% discount for doing so.
Large-scale online ridesharing: the effect of assignment optimality on system performance
David Fiedler, Michal Čertický, Javier Alonso-Mora, Michal Pěchouček, Michal Cap.
In Journal of Intelligent Transportation Systems, 2022.
Mobility-on-demand (MoD) systems consist of a fleet of shared vehicles that can be hailed for one-way point-to-point trips. The total distance driven by the vehicles and the fleet size can be reduced by employing ridesharing, i.e., by assigning multiple passengers to one vehicle. However, finding the optimal passenger-vehicle assignment in an MoD system is a hard combinatorial problem. In this work, we demonstrate how the VGA method, a recently proposed systematic method for ridesharing, can be used to compute the optimal passenger-vehicle assignments and corresponding vehicle routes in a massive-scale MoD system. In contrast to existing works, we solve all passenger-vehicle assignment problems to optimality, regularly dealing with instances containing thousands of vehicles and passengers. Moreover, to examine the impact of using optimal ridesharing assignments, we compare the performance of an MoD system that uses optimal assignments against an MoD system that uses assignments computed using insertion heuristic and against an MoD system that uses no ridesharing. We found that the system that uses optimal ridesharing assignments subject to the maximum travel delay of 4 minutes reduces the vehicle distance driven by 57% compared to an MoD system without ridesharing. Furthermore, we found that the optimal assignments result in a 20% reduction in vehicle distance driven and 5% lower average passenger travel delay compared to a system that uses insertion heuristic.
A business class for autonomous mobility-on-demand: Modeling service quality contracts in dynamic ridesharing systems
B. A. Beirigo, R. R. Negenborn, J. Alonso-Mora, F. Schulte.
In Transportation Research Part C: Emerging Technologies, 2022.
With the popularization of transportation network companies (TNCs) (e.g., Uber, Lyft) and the rise of autonomous vehicles (AVs), even major car manufacturers are increasingly considering themselves as autonomous mobility-on-demand (AMoD) providers rather than individual vehicle sellers. However, matching the convenience of owning a vehicle requires providing consistent service quality, taking into account individual expectations. Typically, different classes of users have different service quality (SQ) expectations in terms of responsiveness, reliability, and privacy. Nonetheless, AMoD systems presented in the literature do not enable active control of service quality in the short term, especially in light of unusual demand patterns, sometimes allowing extensive delays and user rejections. This study proposes a method to control the daily operations of an AMoD system that uses the SQ expectations of heterogeneous user classes to dynamically distribute service quality among riders. Additionally, we consider an elastic vehicle supply, that is, privately-owned freelance AVs (FAVs) can be hired on short notice to help providers meeting user service-level expectations. We formalize the problem as the dial-a-ride problem with service quality contracts (DARP-SQC) and propose a multi-objective matheuristic to address real-world requests from Manhattan, New York City. Applying the proposed service-level constraints, we improve user satisfaction (in terms of reached service-level expectations) by 53% on average compared to conventional ridesharing systems, even without hiring additional vehicles. By deploying service-quality-oriented on-demand hiring, our hierarchical optimization approach allows providers to adequately cater to each segment of the customer base without necessarily owning large fleets.
How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium
A. Fielbaum, R. Kucharski, O. Cats, J. Alonso-Mora.
In European Journal of Operational Research, 2021.
Emerging on-demand sharing alternatives, in which one resource is utilised simultaneously by a circumstantial group of users, entail several challenges regarding how to coordinate such users. A very relevant case refers to how to form groups in a mobility system that offers shared rides, and how to split the costs within the travellers of a group. These are non-trivial tasks, as two objectives conflict: 1) minimising the total costs of the system, and 2) finding an equilibrium where each user is content with her assignment. Aligning both objectives is challenging, as users are not aware of the externalities induced to the rest. In this paper, we propose protocols to share the costs within a ride so that optimal solutions can also constitute equilibria. To do this, we model the situation as a non-cooperative game, which can be seen as a game-version of the well-known set cover problem. We show that the traditional notions of equilibrium in game theory (Nash and Strong) are not useful here, and prove that determining whether a Strong Equilibrium exists is an NP-Complete problem, by reducing it to the k-Exact-Cover problem. Hence, we propose three alternative equilibrium notions (stronger than Nash and weaker than Strong), depending on how users can coordinate. For each of these equilibrium notions, we propose a (possibly overcharging) cost-sharing protocol that yields the optimal solutions equilibria. Simulations for Amsterdam reveal that our protocols can achieve stable solutions that are close to the optimum, and that having a central coordinator can have a large impact.
Anticipatory routing methods for an on-demand ridepooling mobility system
A. Fielbaum, M. Kronmueller, J. Alonso-Mora.
In Transportation, 2021.
On-demand mobility systems in which passengers use the same vehicle simultaneously are a promising transport mode, yet difficult to control. One of the most relevant challenges relates to the spatial imbalances of the demand, which induce a mismatch between the position of the vehicles and the origins of the emerging requests. Most ridepooling models face this problem through rebalancing methods only, i.e., moving idle vehicles towards areas with high rejections rate, which is done independently from routing and vehicle-to-orders assignments, so that vehicles serving passengers (a large portion of the total fleet) remain unaffected. This paper introduces two types of techniques for anticipatory routing that affect how vehicles are assigned to users and how to route vehicles to serve such users, so that the whole operation of the system is modified to reach more efficient states for future requests. Both techniques do not require any assumption or exogenous knowledge about the future demand, as they depend only on current and recent requests. Firstly, we introduce rewards that reduce the cost of an assignment between a vehicle and a group of passengers if the vehicle gets routed towards a high-demand zone. Secondly, we include a small set of artificial requests, whose request times are in the near future and whose origins are sampled from a probability distribution that mimics observed generation rates. These artificial requests are to be assigned together with the real requests. We propose, formally discuss and experimentally evaluate several formulations for both approaches. We test these techniques in combination with a state-of-the-art trip-vehicle assignment method, using a set of real rides from Manhattan. Introducing rewards can diminish the rejection rate to about nine-tenths of its original value. On the other hand, including future requests can reduce users’ traveling times by about one-fifth, but increasing rejections. Both methods increase the vehicles-hour-traveled by about 10%. Spatial analysis reveals that vehicles are indeed moved towards the most demanded areas, such that the reduction in rejections rate is achieved mostly there.
Towards a geographically even level of service in on-demand ridepooling
P. Schuller, A. Fielbaum, J. Alonso-Mora.
In Proc. 2021 IEEE - Int. Conf. on Intelligent Transportation (ITSC), 2021.
On-demand ridepooling systems usually need to decide which requests to serve, when the number of vehicles is not enough to transport them all with waiting times that are acceptable by the users. When doing so, they tend to provide uneven service rates, concentrating rejections in some zones within the operation area. In this paper, we propose two techniques that modify the objective function governing the assignment of users to vehicles, to prioritize requests originated at zones that present a relatively large rejection rate. The goal is to diminish the Gini Index of the rejections' rate, which is a well established way to measure inequality in economics. We test these techniques over an artificial small network and a real-life case in Manhattan, and we show that they are able to reduce the Gini Index of the rejection rates. Moreover, the overall rejection rate can be simultaneously reduced, thanks to utilizing the vehicles more efficiently.
On-demand ridesharing with optimized pick-up and drop-off walking locations
A. Fielbaum, X. Bai, J. Alonso-Mora.
In Transportation Research Part C: Emerging Technologies, 2021.
On-demand systems in which passengers with similar routes can share a vehicle are expected to become a relevant part of future mobility, thanks to their flexibility and their potential impact on reducing congestion. Nevertheless, due to the long detours required by a door-to-door scheme, they induce extra costs to the users in terms of delay. In this paper, we face the design of such a system in which users might be requested online to walk towards/from nearby pick-up/drop-off points if this improves overall efficiency. We show theoretically that the general problem becomes more complex (as it contains two sub-problems that extend set-cover), analyze the trade-offs that emerge, and provide a general formulation and specific heuristics that are able to solve it over large instances. We test this formulation over a real dataset of Manhattan taxi trips (9970 requests during one hour), finding that (a) average walks of about one minute can reduce the number of rejections in more than 80% and Vehicles-Hour-Traveled in more than 10%, (b) users who depart or arrive at the most demanded areas are more likely to be required to walk, and (c) the performance improvement of the service is larger when the system receives more trip requests.
Unreliability in ridesharing systems: Measuring changes in users' times due to new requests
A. Fielbaum, J. Alonso-Mora.
In Transportation Research Part C: Emerging Technologies, 2020.
On-demand systems in which several users can ride simultaneously the same vehicle have great potential to improve mobility while reducing congestion. Nevertheless, they have a significant drawback: the actual realization of a trip depends on the other users with whom it is shared, as they might impose extra detours that increase the waiting time and the total delay; even the chance of being rejected by the system depends on which travelers are using the system at the same time. In this paper we propose a general description of the sources of unreliability that emerge in ridesharing systems and we introduce several measures. The proposed measures are related to two sources of unreliability induced by how requests and vehicles are being assigned, namely how users’ times change within a single trip and between different realizations of the same trip. We then analyze both sources using a state-of-the-art routing and assignment method, and a New York City test case. Regarding same trip unreliability, in our experiments for different fixed fleet compositions and when reassignment is not restricted, we find that more than one third of the requests that are not immediately rejected face some change, and the magnitude of these changes is relevant: when a user faces an increase in her waiting time, this extra time is comparable to the average waiting time of the whole system, and the same happens with total delay. Algorithmic changes to reduce this uncertainty induce a trade-off with respect to the overall quality of service. For instance, not allowing for reassignments may increase the number of rejected requests. Concerning the unreliability between different trips, we find that the same origin-destination request can be rejected or served depending on the state of the fleet. And when it is served the waiting times and total delay are rarely equal, which remains true for different fleet sizes. Furthermore, the largest variations are faced by trips beginning at high-demand areas.
If you are late, everyone is late: late passenger arrival and ride-pooling systems' performance
R. Kucharski, A. Fielbaum, J. Alonso-Mora, O. Cats.
In Transportmetrica A: Transport Science, 2020.
Sharing rides in on-demand systems allow passengers to reduce their fares and service providers to increase revenue, though at the cost of adding uncertainty to the system. Notably, the uncertainty of ride-pooling systems stems not only from travel times but also from unique features of sharing, such as the dependency on other passengers' arrival time at their pick up points. In this work, we theoretically and experimentally analyse how late arrivals at pick up locations impact shared rides' performance. We find that the total delay is equally distributed among sharing passengers. However, delay composition gradually shifts from on-board delay only for the first passenger to waiting delay at the origin for the last passenger. Sadly, trips with more passengers are more adversely impacted. Strategic behaviour analysis reveals Nash equilibria that might emerge. We analyse the system-wide effects and find that when lateness increases passengers refrain from sharing and eventually opt-out.
Ride-Sharing Efficiency and Level of Service under Alternative Demand, Behavioral and Pricing Settings
A. de Ruijter, O. Cats, J. Alonso-Mora, S. Hoogendoorn.
In Transportation Research Board Annual Meeting, 2020.
Previous studies examining ride-sharing potential assumed that rides can be shared as long as the incurred delay does not exceed a certain threshold. Conversely, we formulate willingness to share as a compensatory cost function at the individual passenger level. The latter considers trade-offs between delays caused by detours, travel discomfort related to sharing a vehicle and a fare discount associated with a shared ride. Next to finding how these behavioral preferences and the offered discount structure affect the efficiency and level of service of ride-sharing services, the effect of directionality in demand is considered. A graph-based approach is applied to perform an efficient assignment of vehicles to requests. We test the model on an experiment representing an urban context. Our findings suggest that service performance is strongly dependent on users' willingness to share and somewhat less strongly on users' tolerance to delays. Implementation of a ride-sharing service is most successful when directionality in demand is low, while ride-specific discounts can be effective in maximizing societal benefits.
Optimizing Multi-class Fleet Compositions for Shared Mobility-as-a-Service
A. Wallar, W. Schwarting, J. Alonso-Mora, D. Rus.
In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2019.
Mobility-as-a-Service (MaaS) systems are transforming the way society moves. The introduction and adoption of pooled ride-sharing has revolutionized urban transit with the potential of reducing vehicle congestion, improving accessibility and flexibility of a city's transportation infrastructure. Recently developed algorithms can compute routes for vehicles in realtime for a city-scale volume of requests, as well as optimize fleet sizes for MaaS systems that allow requests to share vehicles. Nonetheless, they are not capable of reasoning about the composition of a fleet and their varying capacity classes. In this paper, we present a method to not only optimize fleet sizes, but also their multi-class composition for MaaS systems that allow requests to share vehicles. We present an algorithm to determine how many vehicles of each class and capacity are needed, where they should be initialized, and how they should be routed to service all the travel demand for a given period of time. The algorithm maximizes utilization while reducing the total number of vehicles and incorporates constraints on wait- times and travel-delays. Finally, we evaluate the effectiveness of the algorithm for multi-class fleets with pooled ride-sharing using 426,908 historical taxi requests from Manhattan and 187,243 downtown Singapore. We show fleets comprised of vehicles with smaller capacities can reduce the total travel delay by 10% in Manhattan whereas larger capacity fleets in downtown Singapore contribute to a 9% reduction in the total waiting time.
Optimizing Vehicle Distributions and Fleet Sizes for Mobility-on-Demand
A. Wallar, J. Alonso-Mora, D. Rus.
In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2019.
Mobility-on-demand (MoD) systems are revolutionizing urban transit with the introduction of ride-sharing. Such systems have the potential to reduce vehicle congestion and improve accessibility of a city's transportation infrastructure. Recently developed algorithms can compute routes for vehicles in real-time for a city-scale volume of requests while allowing vehicles to carry multiple passengers at the same time. However, these algorithms focus on optimizing the performance for a given fleet of vehicles and do not tell us how many vehicles are needed to service all the requests. In this paper, we present an offline method to optimize the vehicle distributions and fleet sizes on historical demand data for MoD systems that allow passengers to share vehicles. We present an algorithm to determine how many vehicles are needed, where they should be initialized, and how they should be routed to service all the travel demand for a given period of time. Evaluation using 23,529,740 historical taxi requests from one month in Manhattan shows that on average 2864 four passenger vehicles are needed to service all of the taxi demand in a day with an average added travel delay of 2.8 mins.
The Impact of Ridesharing in Mobility-on-Demand Systems: Simulation Case Study in Prague
D. Fiedler, M. Certicky, J. Alonso-Mora, M. Cap.
In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2018.
In densely populated-cities, the use of private cars for personal transportation is unsustainable, due to high parking and road capacity requirements. The mobility-on-demand systems have been proposed as an alternative to a private car. Such systems consist of a fleet of vehicles that the user of the system can hail for one-way point-to-point trips. These systems employ large-scale vehicle sharing, i.e., one vehicle can be used by several people during one day and consequently, the fleet size and the parking space requirements can be reduced, but, at the cost of a non-negligible increase in vehicles miles driven in the system. The miles driven in the system can be reduced by ridesharing, where several people traveling in a similar direction are matched and travel in one vehicle. We quantify the potential of ridesharing in a hypothetical mobility-on-demand system designed to serve all trips that are currently realized by private car in the city of Prague. Our results show that by employing a ridesharing strategy that guarantees travel time prolongation of no more than 10 minutes, the average occupancy of a vehicle will increase to 2.7 passengers. Consequently, the number of vehicle miles traveled will decrease to 35% of the amount in the MoD system without ridesharing and to 60% of the amount in the present state.
Vehicle Rebalancing for Mobility-on-Demand Systems with Ride-Sharing
A. Wallar, M. van der Zee, J. Alonso-Mora, D. Rus.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2018.
Recent developments in Mobility-on-Demand (MoD) systems have demonstrated the potential of road vehicles as an efficient mode of urban transportation Newly developed algorithms can compute vehicle routes in real-time for batches of requests and allow for multiple requests to share vehicles. These algorithms have primarily focused on optimally producing vehicle schedules to pick up and drop off requests. The redistribution of idle vehicles to areas of high demand, known as rebalancing, on the contrary has received little attention in the context of ride-sharing. In this paper, we present a method to rebalance idle vehicles in a ride-sharing enabled MoD fleet. This method consists of an algorithm to optimally partition the fleet operating area into rebalancing regions, an algorithm to determine a real-time demand estimate for every region using incoming requests, and an algorithm to optimize the assignment of idle vehicles to these rebalancing regions using an integer linear program. Evaluation with historical taxi data from Manhattan shows that we can service 99.8% of taxi requests in Manhattan using 3000 vehicles with an average waiting time of 57.4 seconds and an average in-car delay of 13.7 seconds. Moreover, we can achieve a higher service rate using 2000 vehicles than prior work achieved with 3000. Furthermore, with a fleet of 3000 vehicles, we reduce the average travel delay by 86%, the average waiting time by 37%, and the amount of ignored requests by 95% compared to earlier work at the expense of an increased distance travelled by the fleet.
Multi-Objective Analysis of Ridesharing in Automated Mobility-on-Demand
M. Cap, J. Alonso-Mora.
In Proc. Robotics: Science and Systems (RSS), 2018.
Self-driving technology is expected to enable the realization of large-scale mobility-on-demand systems that employ massive ridesharing. The technology is being celebrated as a potential cure for urban congestion and others negative externalities of individual automobile transportation. In this paper, we quantify the potential of ridesharing with a fleet of autonomous vehicles by considering all possible trade-offs between the quality of service and operation cost of the system that can be achieved by sharing rides. We formulate a multi-objective fleet routing problem and present a solution technique that can compute Pareto-optimal fleet operation plans that achieve different trade- offs between the two objectives. Given a set of requests and a set of vehicles, our method can recover a trade-off curve that quantifies the potential of ridesharing with given fleet. We provide a formal optimality proof and demonstrate that the proposed method is scalable and able to compute such trade-off curves for instances with hundreds of vehicles and requests optimally. Such an analytical tool helps with systematic design of shared mobility system, in particular, it can be used to make principled decisions about the required fleet size.
Predictive Routing for Autonomous Mobility-on-Demand Systems with Ride-Sharing
J. Alonso-Mora, A. Wallar, D. Rus.
In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2017.
Ride-sharing, or carpooling, systems with autonomous vehicles will provide efficient and reliable urban mobility on demand. In this work we present a method for dynamic vehicle routing that leverages historical data to improve the performance of a network of self-driving taxis. In particular, we describe a constrained optimization method capable of assigning requests to autonomous vehicles in an informed way, to minimize the expected cost of serving both current and future travel requests. We allow several passengers with independent trips to share a vehicle and allow vehicles to pick additional passengers as they progress through their route. Based on historical data, we compute a probability distribution over future demand. Then, samples from the learned probability distribution are incorporated into a decoupled vehicle routing and passenger assignment method to take into account the predicted future demand. This method consists of three steps, namely pruning of feasible trips, assignment of trips to vehicles and rebalancing of idle vehicles. We show the benefits and trade-offs of this predictive approach in an experimental evaluation with over three million rides extracted from a dataset of taxi trips in New York City. Our method produces routes and assignments that, in expectation, reduce the travel and waiting times for passengers, with respect to a purely reactive approach. Besides the mobility on demand application, the method we present is general and could also be applied to other multi-task multi-vehicle assignment and routing problems.
On-demand High-capacity Ride-sharing via Dynamic Trip-Vehicle Assignment
J. Alonso-Mora, S. Samaranayake, A. Wallar, E. Frazzoli, D. Rus.
In Proceedings of the National Academy of Sciences of the USA (PNAS), vol. 114, no. 3, pp. 462-467, 2017.
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.