Models, Algorithms, and Implementations for Operational Optimization of Ridepool Services

Abstract

Ridepooling/microtransit are special types of ridehailing that benefit from reduced pollution and lower costs to users by placing multiple unrelated customers that share similar itineraries in the same vehicle. This dissertation studies problems related to ridepooling from several angles, from algorithmic, numerical, theoretical, to real-world practical studies. The bulk of the work relates to Request-Trip-Vehicle decompositions for ridepool assignments problems, a recent technique that has gained popularity because it preserves optimal solutions, provides large flexibility to adapt to a variety of constraints, and because of good practical performance. In this dissertation, we start by presenting an algorithm for the operation of high-capacity electric vehicle fleets in ridepool systems where the vehicles need to recharge during the day. We show that our algorithm outperforms a naive approach with respect to the service rate metric and discuss how the results reinforce the importance of having demand forecasts in ridepool settings. Next, we present some novel formulations of the ridepool assignment problem based on inexact models. These formulations, as well as some from the literature, are benchmarked on New York City taxi data according to the service rate metric. After observing that the service rate is very similar for all of the algorithms we then demonstrate evidence that there may be a service rate barrier that many algorithms are hitting. We hypothesize that in order to break this barrier algorithms must be adapted to take into account demand forecasts. On the front of microtransit, we first study a method for developing approximation algorithms for tail-risk minimization problems motivated by routing shared vehicles to maximize the probability of successful transfers to other transit. Then more concretely, we discuss work done in collaboration with transit agencies in Seattle and Minneapolis-St. Paul, using tools and algorithms we developed to perform a data-driven design of microtransit feeder services, with the first pilots slated for deployment in fall 2021. Finally, as a timely contribution we present a model and efficient implementation for studying infectious diseases on university campuses.