Algorithms for Scalable Dynamic Ride-Pooling

To reach sustainability goals, urban transportation systems need to shift from polluting, inefficient cars to high-capacity shared public transit. However, transit cannot effectively cover all travel demand, so a transition from cars to transit risks reducing the quality of transportation in some areas. Ride-pooling is a flexible alternative to traditional fixed transit that could ease these concerns. In dynamic ride-pooling, travelers make a request for immediate travel to a central dispatcher, stating their origin and destination locations. The dispatcher assigns a taxi-like road vehicle to each request that picks the traveler up at their origin and brings them to their destination. In contrast to traditional taxis, the dispatcher may “pool” independent travelers in the same vehicle if they have matching itineraries. Ride-pooling is both shared and on-demand, which promises better efficiency than cars while maintaining greater flexibility than fixed public transit. As such, it could become a staple of future transportation systems, especially due to the advent of shared autonomous vehicles.
Operating a ride-pooling vehicle fleet requires the dispatcher to effectively assign vehicles to travelers with the goal of optimizing trip quality for riders and minimizing the amount of resources used by the vehicles, e.g. ... mehrfuel, emissions, or driver costs. In a real-world ride-pooling system, an assignment needs to be computed quickly to allow for interactive routing applications. Recent approaches for the dynamic ride-pooling problem focus on the quality of assignments, but do not scale to the expected future demand for ride-pooling in metropolitan areas. Thus, there is a need for faster, more scalable routing solutions.
In this dissertation, we make several key contributions to advancing routing for dynamic ride-pooling. We base our approach on previous work that showed that efficient shortest-path algorithms for road networks should be at the core of dynamic ride-pooling. We engineer these shortest-path algorithms for different variants of the problem.
Our dispatcher KaRRi is designed for fast dispatching in dynamic ride-pooling with meeting points, where riders walk to a pickup location to reduce the vehicle detour required for the pickup. As the dispatcher can choose the meeting point, this routing problem requires us to solve many-to-many shortest-path problems between all possible meeting points and all existing vehicle stops. KaRRi solves these problems by exploiting the locality of meeting points in the road network for cache-efficient bundled shortest-path queries with instruction- level parallelism and improved pruning. KaRRi is the first dispatcher for ride-pooling with meeting points that has a running time in the order of milliseconds per request, which makes it as fast as previous solutions without meeting points. At the same time, meeting points improve the total vehicle operation time and average rider trip time by about 10% compared to a solution without meeting points. In effect, KaRRi leverages its efficient routing to obtain improved solution quality at the same computational cost.
Furthermore, we propose Mt-KaRRi, a multi-threaded version of KaRRi, with the goal of analyzing ride-pooling on the largest available input data for urban transportation systems. We show that a simple synchronization scheme based on iterative re-assignments allows us to concurrently process requests that come in at a similar time. Experimental results show that this approach loses only about 1% solution quality compared to the sequential solution, but leads to good speedups of up to 53 for 96 threads. With this, we can find ride-pooling assignments for all 25 million trips in a Los Angeles rush hour in real time. This level of throughput exceeds previous approaches by two orders of magnitude.
We use KaRRi to conduct a study of ride-pooling as an integrated part of metropolitan scale transportation systems. Using a model for traveler mode choice, we evaluate ride-pooling in competition with walking, cars, and public transit. As an improvement over previous studies, the scalability of KaRRi allows us to analyze the effect of huge vehicle fleets and an adoption of ride-pooling by the whole population.
We also explore complex extended scenarios that could profit from the efficiency of KaRRi. As a first step, we consider journeys that allow a single transfer between ride-pooling vehicles. As the main source of added complexity, we now need to find the best transfer locations for pairs of vehicles. We first propose an exact variant of our algorithm KaRRiT that exhaustively searches for the best transfer location by combining engineered one-to-all shortest-path queries and pruning based on problem constraints. As the exact variant is too slow for real-world systems, we also propose a heuristic variant of KaRRiT. This heuristic variant is about two orders of magnitude slower than the no-transfer approach, but its transfer journeys generate tangible benefits for the effectiveness of ride-pooling.
Finally, we consider the integration of ride-pooling and public transit, which is required to make optimal use of the flexibility of ride-pooling and the efficiency of public transit. For this, we combine KaRRi with a framework for public transit journey planning to find multimodal journeys that use both ride-pooling and transit. We identify key differences to traditional multimodal journeys with walking and transit, and show that our solution needs to optimize journeys in a multi-criteria sense by considering ride-pooling cost and rider trip time. We adapt KaRRi to efficiently solve one-to-many ride-pooling queries between a traveler’s origin and all public transit stations. A multi-criteria public transit query then uses these ride- pooling access trips to find complete multimodal journeys. Our solution PaRRot computes multimodal journeys with an overhead of less than 2.5ms over a ride-pooling-only query. We show that combined journeys reduce system-wide rider trip times, and that they can improve the total time driven by ride-pooling vehicles. Combined journeys prove particularly important for travelers that previously had no alternative to using a ride-pooling-only trip.