David Shmoys - Algorithms for the Operation and Design of Bike-sharing Systems

14:30
Mardi
19
Fév
2019
  • Keynote Speech
Lieu : 
Organisé par : 
Nicolas Peltier
Intervenant : 
David Shmoys (Cornell University)
Équipes : 

 

David Shmoys obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the Cornell faculty. He is Co-Chair of the Academic Planning Committee for Cornell Tech and Associate Director of the Institute of Computational Sustainability at Cornell University.

He is a Fellow of the ACM, INFORMS, and of SIAM, was an NSF Presidential Young Investigator, and has served on numerous editorial boards, including Mathematics of Operations Research (for which he is currently an Associate Editor), Operations Research, ORSA Journal on Computing, Mathematical Programming, and the SIAM Journals of both Computing and Discrete Mathematics, where for the latter he also served as Editor-in-Chief. He has been the advisor for 21 graduated Ph.D. students, and his former students are currently on the faculties of many leading universities and research labs, including MIT, Waterloo, Brown, Maryland, Georgetown, and D-Wave.

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, The Design of Approximation Algorithms, was awarded the 2013 Lanchester Prize by INFORMS.

His paper, "Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility", joint with Daniel Freund, Shane Henderson, and Eoin O'Mahony, was awarded the 2018 INFORMS Daniel H. Wagner Prize.

Réalisation technique : Antoine Orlandi | Tous droits réservés

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, and by 2017 there were roughly 17 million individual trips taken. We have worked with Citibike and their parent company Motivate, 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 algorithmic tools 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 stocking levels for the bikes, as well as methods employed for optimizing (and re-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. 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.

This is joint work with Daniel Freund, Shane Henderson, and Eoin O’Mahony, as well as Hangil Chung, Aaron Ferber, Nanjing Jian, Ashkan Nourozi-Fard, Alice Paul, and David Williamson.