Applied Math Colloquium
Monday, December 10, 2018 at 4:15pm
David Shmoys (Cornell University)
Title: Models and Algorithms for the Operation and Design of Bike-sharing Systems
Abstract: Bike-sharing systems are changing the urban transportation landscape; for example, New York launched the largest bike-sharing system in North America in May 2013, which served roughly 17 million rides in 2017. We have worked with Citibike and its parent company Motivate, developing optimization models and algorithms to change how they manage their systems. In particular, continuous-time Markov chain models, combined with simple mathematical programming tools, can be used to answer the question – what is the optimal deployment of the bike fleet across the system at the start of the day? In addition, we shall consider the more strategic question of how to (re-)allocate dock-capacity in such systems. We develop new algorithms for the resulting mathematical programming problems, with algorithmic implications in the theory of discrete convexity. More concretely, we design a practically fast polynomial-time allocation algorithm to compute optimal solutions for the dock allocation problem, which can also handle practically motivated constraints, such as a limit on the number of docks moved in the system. More recently, we have guided the development of Bike Angels, a program to incentivize users to crowdsource “rebalancing rides”, and we will describe its underlying analytics, where the pricing mechanism is once again grounded in the same underlying algorithmic tools.