Thesis Defense: The Edge of Large-Scale Optimization in Transportation

Tuesday, May 7, 2019 - 12:30pm to 1:30pm

Event Calendar Category

LIDS Thesis Defense

Speaker Name

Sebastien Martin

Affiliation

LIDS

Building and Room number

E51-376

Abstract

THESIS COMMITTEE:
Prof. Dimitris Bertsimas (Thesis co-supervisor)
Prof. Vivek Farias
Prof. Patrick Jaillet (Thesis co-supervisor)
Prof. Asu Ozdaglar
 
The emergence of analytics has created significant opportunities for research in optimization, in particular in the rising field of transportation. The availability of massive data sets makes it possible to define new real-world applications that are larger than what state-of-the-art optimization algorithms and solvers can handle. Therefore, problems that matter the most are sometimes solved using simplistic optimization methods that are faster but potentially result in sub-optimal solutions. This thesis explores this computational tradeoff, focusing on impactful applications of optimization in transportation. Using both theory and computational experiments, we introduce novel optimization algorithms to overcome the tractability issues that arise in large scale optimization problems. This thesis also focuses on the implementation of these algorithms, through the creation of software and collaboration with Boston Public Schools that generated millions of dollars in savings. Confronting the challenges of implementation lead us to introduce a framework for model interpretability, an essential building block of successful analytics applications.
 
The two main applications of this thesis are ride-sharing and school transportation. We introduce an online vehicle routing algorithm for ride-sharing able to handle hundreds of thousands of customers every day in New York City. We also worked with Boston Public Schools on school bus routing, implementing an algorithm that saves 5 million dollars every year in Boston, money that is being reinvested in the children's education. This work was also the first to answer the complex policy question ``when should schools start?'', and this answer created a national public debate as well as an update of Boston's start time policy.
 
Building on these applications, this thesis presents methodological contributions in large-scale optimization. Our work on ride-sharing and school buses both introduce state-of-the-art algorithms for school bus routing and scheduling problems with time-windows. These contributions both rely on our work on large-scale travel-time estimation. We introduce an algorithm that solves a sequence of second order cone problems to approximate solutions of the inverse shortest path length problem on networks with tens of thousands of arcs and is able to accurately estimate travel times in cities as large as NYC and Boston. We also present a theoretical and empirical study of the stochastic proximal point algorithm, an alternative to stochastic gradient methods (the de-facto algorithm for large scale machine learning).
 
This study is representative of the tradeoffs of large scale optimization as we show that the optimization gains of the computationally expensive proximal operator allow it to remain computationally competitive and a good alternative to stochastic gradients.
 
Finally, this thesis also focuses on the challenges of the implementation of these optimization algorithms. The first step towards implementation is to create robust software, and this thesis shares many software contributions, including a complete real-time simulation engine for online vehicle routing. Moreover, our impact in Boston Public School was also made possible by frequent exchanges with policy-makers and journalists. These interactions showed how important it was for a successful implementation to be able to describe and explain our models and algorithms to stakeholders. We, therefore, use the last part of this thesis to formalize what it means for a model to be interpretable. Using an incremental framework that generalizes various traits associated with interpretability for a large class of models, we are able to provide a way to quantify and optimize a formal measure of interpretability.