In the next few decades, it is estimated that a quarter of all trips worldwide will be served by shared mobility supported in part by lower carbon footprint compared to private mobility. In particular, on-demand ridesharing is appealing due to its convenience, matching passengers needing rides to vehicles in real time while optimizing the matching. While this matching problem is computationally challenging, the state-of-art greedy search algorithm assigns passengers one at a time to the locally best vehicle and has been shown to perform well in practice. However, in order to scale the algorithm, how to parallelize searches for multiple requests remains challenging due to contention for vehicle tours. Moreover, the request latency may still be too high for on-demand requests. In this paper, we give several techniques to speed up and scale out ridesharing search. To deal with data contention while scaling out greedy search, we introduce a “map-release” and ticketing system that sacrifices read-write consistency to achieve high concurrency, even under high contention, and while avoiding expensive aborts incurred by optimistic approaches. To address high request latency, we give a caching technique to speed up the tour expansion subroutine of greedy search, and we also give a pruning technique to reduce the tour candidates even further compared to existing techniques. Together, these techniques deliver around 7x the throughput and order of magnitude lower latency on a real instance compared to the “embarassingly parallel” parallelized map approach and with better scalability.

Ridesharing algorithms operate in environments that are dynamic and uncertain due to traffic effects. Evaluating an algorithm by deploying it in a real environment is costly and often inaccessible, yet the traditional approach of using static inputs and applying an objective function on the outputs may give unrealistic results. Jargo is a novel real-time simulator that provides more realistic evaluation. It lets users implement their own algorithms, speed field functions, and evaluators, and then it reports on multiple quality metrics that are useful to service providers. To support any new and existing algorithm, simulate traffic, and compute the metrics, it is supported by a new relational model of ridesharing. Relations naturally express empirical concepts such as customer pick-up time, and their flexibility can allow any feasible routing strategy. Relational algebra is also convenient for defining operations on the system as well as formalizing service-related metrics. We will show how a service provider considering whether or not to deploy the well-known greedy insertion algorithm could use Jargo to uncover its limits and guide the development of new techniques.

Ridesharing is becoming a popular mode of transportation with profound effects on the industry. Recent algorithms for vehicle-to-customer matching have been developed; yet cross-study evaluations of their performance and applicability to real-world ridesharing are lacking. Evaluation is complicated by the online and real-time nature of the ridesharing problem. In this paper, we develop a simulator for evaluating ridesharing algorithms, and we provide a set of benchmarks to test a wide range of scenarios encountered in the real world. These scenarios include different road networks, different numbers of vehicles, larger scales of customer requests, and others. We apply the benchmarks to several state-of-the-art search and join based ridesharing algorithms to demonstrate the usefulness of the simulator and the benchmarks. We find quickly-computable heuristics outperforming other more complex methods, primarily due to faster computation speed. Our work points the direction for designing and evaluating future ridesharing algorithms.