PhD Candidate, Cornell University
I mathematically model and optimize problems arising in modern transportation systems.
The recent (r)evolution of “transportation-as-a-service” has affected commuting patterns in major American cities. Yet the rise of ride-sharing apps, like Uber or Lyft, and bike-sharing systems, like CitiBike or Hubway, not only provided new opportunities for commuters, but also new challenges for operators. Common to all of these challenges are the intricate underlying network effects each ride has on supply in the system. For example, every rental of a bike at a bike-sharing station not only decreases the supply of bikes at that station but simultaneously increases the supply of docks available (for bike returns). The same phenomenon is present in ride-sharing systems. The resulting externalities, both positive and negative, make such systems academically interesting markets in dire need of optimization. In my research, I aim to combine rigorous mathematical analysis with real data to alleviate these operational challenges. More specifically, I try to model the operational challenges mathematically and design algorithms that find optimal solutions. Often, the underlying mathematical structure of my models suggests that it may be impossible to design an algorithm that is guaranteed to be both fast and correct. In such cases, I aim to design heuristics with provable guarantees. For example, in my work with Banerjee and Lykouris, we studied the question of how to optimally price in ride-sharing systems. While our results showed that the underlying optimization problem is non-convex in general (computationally difficult to optimize), we proved that we can solve a related problem, use the resulting solution, and parametrically bound the error compared to the optimal solution. For the parameters of realistic regimes, the error turned out to be very close to 0. As an intern at Lyft, I then got to further investigate and optimize the impact pricing can have as a control. In related work with Shmoys and Henderson on capacity allocation in bike-sharing systems, we applied an inventory model frequently used in routing problems. In our work, we adapted it to the more strategic question of allocating dock-capacity in such systems and found structural properties that allowed us to design a provably fast and correct algorithm. Applying our algorithm to data-sets from NYC, Chicago, and Boston, we were able to inform the operators’ system design, thus reducing the number of out-of-stock events that customers experience.
Abstract: The growing popularity of bike-sharing systems around the world has motivated recent attention to models and algorithms for the effective operation of these systems. Most of this literature focuses on their daily operation for managing asymmetric demand. In this work, we consider the more strategic question of how to allocate dock-capacity in such systems. Our main result is a practically fast polynomial-time allocation algorithm to compute optimal solutions for this problem, that can also handle a number of practically motivated constraints, such as a limit on the number of docks moved from a given allocation. Our work further develops connections between bike-sharing models and the literature on discrete convex analysis and optimization.
Pub.: 28 Nov '16, Pinned: 01 Jul '17
Abstract: We propose a framework for data-driven pricing in shared vehicle systems (such as bikesharing and carsharing) in which customers can pick up and drop off vehicles in different locations. This framework provides efficient algorithms with rigorous approximation guarantees for a wide class of objective functions (including welfare and revenue), and under a variety of constraints on the prices. An interesting class of constraints accommodated by this framework includes multi-objective settings in which the goal is to maximize some objective function subject to some lower bound on another objective function. An important representative of this class is the Ramsey pricing problem, i.e. maximize revenue subject to some lower bound on welfare. Compared to traditional item-pricing problems, pricing in shared vehicle systems is more challenging due to network externalities, wherein setting prices at one demand node may affect the supply at each other node in the network. To capture the system dynamics, we use a closed queueing model in which exogenous demand (obtained from data) can be modulated through pricing. We achieve our approximation guarantees by first projecting the problem to an infinite-supply setting, deriving optimal prices in this limit, and then bounding the performance of these prices in the finite-vehicle system. Our infinite-to-finite supply reduction is of independent interest since it holds for a broader class of objective functions, and applies even more generally than the pricing problems that we consider.
Pub.: 24 Aug '16, Pinned: 01 Jul '17
Join Sparrho today to stay on top of science
Discover, organise and share research that matters to you