Enhancing Ride-Pooling Operations: Algorithms, Heuristics and Simulation-Based Approaches

Abstract

The massive growth of ride-hailing and mobility-on-demand (MoD) platforms like Uber, Lyft, and DiDi, as well as advances in connected and automated vehicle (CAV) technology over the past decade have brought promising alternatives to car ownership within reach for many city residents. However, these services come with potentially severe negative effects on cities, such as increasing congestion and emissions due to empty miles. A useful tool to reduce these drawbacks is the introduction and promotion of ride-pooling, which accommodates multiple passenger requests in a single trip. Adopting ride-pooling on a city-wide scale though has significant challenges including customer preferences, computational complexity, and demand uncertainty, all of which affect the benefits of the service. This dissertation aims to examine and address these issues in the context of ride-pooling operations.

The success of ride-pooling platforms hinges on whether customer demand will accept it over other alternatives; without enough demand, the system loses the efficiency of multiple customers per vehicle. To this end, we propose a community-based ride-sharing scheme where a system operator recommends travelers with similar travel patterns in order to address concerns about delay and safety while promoting a shared-vehicle environment. By leveraging trajectory data from routing apps, smartphones and CAVs, we can gather information about consumer preferences and construct a mobility profile for them. We modify a traditional Dynamic Time Warping (DTW) algorithm to compare trajectories in users’ profiles and use the resulting measures as a basis for offline recommendation matching. We demonstrate this framework on data from the Microsoft Geolife Dataset.

Most ride-pooling platforms operate in a real-time environment, rather than offline, so it is important to consider operational challenges as well. Most notably, solving a matching problem to not only pair riders but also assign groups of requests to vehicles is incredibly complex and time-consuming at scale. First, we develop and examine a family of scalable heuristic methods for ride-to-ride and ride-to-vehicle assignment that improves the customers’ ride-pooling experience. In order to evaluate how changes in these methods and platform decisions affect all aspects of the system including customer waiting time and delay, we propose a family of metrics for evaluating ride-pooling performance. We show that the proposed heuristics for the ride-pooling assignment are scalable and easily implementable methods and can be substitutes for centralized optimization in many scenarios, with only minor sacrifices in platform performance.

Second, while heuristics can achieve good performance in many scenarios, they provide no guarantees on performance in the worst cases. To address this, we formulate a joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program and expand it to the dual- or multi-source scenario in which the service provider can use different fleets of vehicles. Two approximation algorithms are proposed that provide competitive bounds on worst case performance. We then evaluate these approximation algorithms on real-world data using a simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%)

The algorithms, frameworks, and takeaways presented in this dissertation were derived and evaluated for ride-pooling specifically, but many are generalizable to other shared mobility and multi-modal use cases.