UC Berkeley

In the recent decades, new modes of transportation have been developed due to urbanization, highly dense population, and technological advancement. As a result, design and operation of urban transportation have become increasingly important to better utilize the resources and efficiently meet demand. This dissertation was motivated by two problems on optimizing design and control of urban transportation. In the first one, we consider a problem of dynamically matching heterogeneous market parcitipants so as to maximize the total number of matching, which was motivated by practices of ride-sharing platforms. In the other problem, we study efficient design of elevator zoning system in high-rises with uncertainty in customer batching.

In Chapter 1, we consider a multiperiod stochastic optimization of a market that matches heterogeneous and impatient agents. The model was mainly motivated from carpooling products run by ride-sharing platforms such as Uber and Lyft, and kidney exchange market, where market participants are heterogeneous in terms of how likely they can be matched with others. In the case of a ride-sharing platform, one of the key operational decisions for carpooling is to efficiently match riders and clear the market in a timely manner. In doing so, the platform needs to take into account the heterogeneity of riders in terms of their trip types(e.g origin-destination pair) and different matching compatibility. For example, some customers may request rides within San Francisco, while others may request rides from San Francisco to outside the city. Since picking up and dropping off a customer within the city can be done within relatively short amount of time, those who want to travel within the city can be matched with any other riders for carpooling. However, the destinations of those who want to travel to outside the city may be very different, and in order to maintain customers' additional transit time due to carpooling, it is likely that they can be only matched with those who want to travel within the city. In the case of kidney exchange where market participants arrive in the form of patient-donor pair, pairs with donor who can donate her kidney to most of patients (for example, blood type O) and patient who can get kidney from most of donors (for example, blood type AB) can be easily matched to other pairs. The opposite case would be hard-to-match pair that is incompatible for matching with most of other pairs. Our model is an abstraction of these two motivating examples, and considers two types of agents: easy-to-match agents that can be matched with either type of agents, and hard-to-match agents that can be only matched with easy-to-match ones. We first formulate a dynamic program to solve for optimal matching decisions over infinite time horizon in a discrete time setting, and characterize structure of optimal stationary policies. Inspired by practices in kidney exchange where the market is cleared for every fixed time interval, we connect the discrete time model to a continuous time setting by investigating the effect of the length of matching intervals on the matching performance. Results from numerical experiments indicate certain patterns in the relationship between the length of matching intervals and the maximum number of matching achieved, and provides valuable insights for future direction of research.

In Chapter 2, we consider a zoning problem for elevator dispatching systems in high-rises. In practice, zoning is frequently used to improve efficiency of elevator systems. The idea of zoning is to prevent different elevators from stopping at common floors, which may result in long service times of elevators and thus long waiting times of customers. Our goal is to provide a mathematical framework that can help a system planner decide optimal zoning design with some performance guarantee. To this end, we focus on uppeak traffic situation during morning rush hour, which is in general the heaviest traffic during the day. The performance in the uppeak traffic situation can be considered as the system's capacity, because if the system can handle uppeak traffic well, it can also serve other types of traffic with good performance. Thus, the performance measure in the uppeak traffic situation can be used as a metric to choose the optimal zoning configuration. One of the components that complicate the problem is customer batching, on which the system may not have a control. In view of this, we formulate an adversarial optimization problem that can measure the system performance of different zoning decisions. By considering the heaviest traffic situation of the day and using the adversarial framework, we provide a model that can be used for capacity planning of elevator systems. We formulate mixed-integer linear program(MILP)s to find the optimal zoning configuration. To solve the MILPs, we show that we can use simple greedy algorithms and solve smaller linear programs. We also provide a few illustrative examples as well as numerical experiments to verify the theoretical results and obtain insights for further analysis.