Efficient operational strategies for ridesharing systems
This dissertation aims at developing computationally tractable models and algorithms to increase the operational efficiency of the Mobility-on-Demand (MoD) ridesharing systems via three means: i) fast ride-vehicle matching; ii) proactive rebalancing; iii) request-level pricing strategies, and iv) framework to incorporate mode choice models. Mobility-on-Demand (MoD) services such as Uber and Lyft are disrupting urban mobility. Over the last few years, this disruption has led to much interest in studying the design, management and impacts of these systems. However, due to the large scale of the demand and fleet size, how to optimally assign the vehicles to trip requests and how to optimize the prices charged on riders in real time still remain as open problems. Studies usually solve the request-vehicle assignment task in two ways: i) greedy matching, in which a new coming request is matched to a request immediately; ii) batching matching, in which the requests are collected for a short time window (e.g. 30 seconds), and at the end of the time window the optimization problem is considered for the whole batch of requests. Batching matching can usually increase the matching efficiency since it can use the fleet better compared to the greedy matching. However, riders' waiting time can be prolonged due to the batching window, and damage the riders' experience. There is not a consensus on which method is better, and this dissertation discusses both frameworks and one can implement the methods and compare the performance via simulation. In addition, the research proposes speed-up techniques for the batching matching, which can reduce the computation time and increase the matching efficiency given a limited time window. MoD systems are generally designed and analyzed for a fixed and exogenous demand, but such frameworks fail to answer questions about the impact of these services on the urban transportation system, such as the effect of induced demand and the implications for transit ridership. In this dissertation, we propose a unified framework to design, optimize and analyze MoD operations within a multimodal transportation system where the demand for a travel mode is a function of its level of service. An application of Bayesian optimization (BO) to derive the optimal supply-side MoD parameters (e.g., fleet size) is also illustrated. The profit of the MoD companies and the balance between the supply and demand highly depend on the pricing strategies applied. Since the supply and demand volumes at different locations change continuously, dynamic pricing has been proven to be more robust and be helpful to relieve the Wild Goose Chase (WGC) phenomenon. However, the current dynamic pricing method is usually state-dependent. Specifically, given a location zone and its supply level at the moment, the system determines the price multiplier for this zone for the next time window. Although such methods are easy to implement, they ignore the network effects among different location zones, and also they cannot differ the price (multiplier) for requests in the same zone. In practice, travelers make mode choice decisions by comparing the characteristics of each service in the market, and the characteristics of the alternatives (e.g. public transit service) are usually different for each traveler due to their different destination and sociodemographic characteristics. To overcome the above difficulty, the pricing method presented in this dissertation determines the price for each trip request individually. Although MoD services have become one of the major transportation modes, public transit service is still an affordable and clean transportation mode choice. This dissertation also develops fast computation techniques to solve the reliable routing problem known as the stochastic on-time arrival (SOTA) problem in transit networks, which provides a routing strategy that maximizes the probability of arriving at the destination within a given time budget.