The Information Science Colloquium speaker for Wednesday, September 27, will be David Shmoys from Cornell's School of Operations Research and Information Engineering (ORIE) and the Department of Computer Science. Shmoys serves as Laibe/Acheson Professor of Business Management and Leadership Studies, director of ORIE and associate director of the Institute for Computational Sustainability. Shmoys' research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, and most recently, comptuational sustainability. His work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP-hard problems. His recent book, co-authored with David Williamson, is called The Design of Approximation Algorithms and was awarded the 2013 Lanchester Prize by INFORMS.
Title: Models and Algorithms for the Design and Operation 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, with individual trips expected to exceed 15 million rides for 2017. We have worked with Citibike, using analytics and optimization to change how they manage the system. Huge rush-hour usage imbalances the system - we answer the following two questions: where should bikes be at the start of a day and how can we mitigate the imbalances that develop?
We will survey the analytics we have employed for the former question, where we developed an approach based on continuous-time Markov chains combined with integer programming models to compute daily stocking levels for the bikes, as well as methods employed for optimizing the capacity of the stations. For the question of mitigating the imbalances that result, we will describe both heuristic methods and approximation algorithms that guide both mid-rush hour and overnight rebalancing, as well as for the positioning of corrals, which have been one of the most effective means of creating adaptive capacity in the system.
This is joint work with Daniel Freund, Shane Henderson, Nanjing Jian, Ashkan Nourozi-Fard, Eoin O’Mahony, and Alice Paul.