Research

My current research interests are Large-Scale Optimization, Machine Learning, Transportation, Data Analytics and applications to Public Policy.

Published Work

D. Bertsimas, A. Delarue, S. Martin. Optimizing schools' start time and bus routes (2019) Proceedings of the National Academy of Sciences (PNAS) March 26, 2019 116 (13) 5943-5948
(formerly From School Buses to Start Times: Driving Policy With Optimization)
bookmark Franz Edelman Award 2019 Finalist
bookmark MIT ORC 2018 Best Student Paper
bookmark 2nd place of Doing Good with Good OR Competition, INFORMS 2018
Travel time estimation in NYC

Abstract: Maintaining a fleet of buses to transport students to school is a major expense for U.S. school districts. In order to reduce transportation costs by allowing buses to be reused between schools, many districts spread start times across the morning. However, assigning each school a time involves both estimating the impact on transportation costs and reconciling additional competing objectives. Facing this intricate optimization problem, school districts must resort to ad hoc approaches, which are often expensive, inequitable, and even detrimental to student health. For example, medical evidence overwhelmingly indicates that early high school starts are severely impacting the development of an entire generation of students and constitute a major public health crisis. We present the first algorithm to jointly optimize school bus routing and bell time assignment. Our method leverages a natural decomposition of the routing problem and uses mixed-integer optimization to compute and combine subproblem solutions. Our algorithm significantly outperforms state-of-the-art school bus routing methods. The routing engine can be used to formulate a tractable proxy to transportation costs, which allows the formulation of the bell time assignment problem as a multi-objective Generalized Quadratic Assignment Problem. Local search methods provide high-quality solutions, allowing school districts to explore the tradeoffs between competing priorities and choose the solution that best suits the needs of the community. Our application in Boston led to $5 million in yearly savings (maintaining service quality despite a 50-bus fleet reduction) and to the unanimous approval of the first school start time reform in thirty years.

Travel time estimation in NYC

Abstract: Twenty-first century urban planners have identified the understanding of complex city traffic patterns as a major priority, leading to a sharp increase in the amount and the diversity of traffic data being collected. For instance, taxi companies in an increasing number of major cities have started recording metadata for every individual car ride. In this paper, we show that we can leverage network optimization insights to extract accurate travel time estimations from such origin-destination data, using information from a large number of taxi trips to reconstruct the traffic patterns in an entire city on a variety of timescales. We develop a method that tractably exploits origin-destination data, and draws from its optimization framework the flexibility needed to take advantage of other sources of traffic information. Using synthetic data, we establish the robustness of our algorithm to uncertainty, and display its ability to significantly reduce input variance. We show empirically that our algorithm can leverage any available amount of data, even in a high-variance environment, to provide insights about urban traffic patterns on different scales, leading to accurate travel time estimations throughout the network.

Taxi routing in NYC

Abstract: With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand datasets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In this paper, we develop an optimization framework, coupled with a novel and generalizable backbone algorithm, that allows us to dispatch in real time thousands of taxis serving more than 25,000 customers per hour. We provide evidence from historical simulations using New York City routing network and yellow cabs data to show that our algorithms improve upon the performance of existing heuristics in such real-world settings.

Cal logo reproduced with congestion patterns

Abstract: This article presents a study on freeway networks instrumented with coordinated ramp metering and the ability of such control systems to produce arbitrarily complex congestion patterns within the dynamical limits of the traffic system. The developed method is used to evaluate the potential for an adversary with access to control infrastructure to enact high-level attacks on the underlying freeway system. The attacks are executed using a predictive, coordinated ramp metering controller based on finite-horizon optimal control and multi-objective optimization techniques. The efficacy of the control schemes in carrying out the prescribed attacks is determined via simulations of traffic network models based on the cell transmission model with onramps modeled as queue buffers. Freeway attacks with high-level objectives are presented on two illustrative examples: congestion-on-demand, which aims to create precise, user-specified pockets of congestion, and catch-me-if-you-can, which attempts to aid a fleeing vehicle from pursuant vehicles.

Current Research

New large scale transportation infrastructure are revolutionizing our daily commute. Even more that traditional Uber/Lyft, ride sharing, electric scooters and self driving technologies create the opportunity of exciting and impactful new optimization problems. My current work, in the line of my already published transportation research, explores these applications and try to scale traditional optimization algorithms and formulations to tackle these new challenges.
Stochastic proximal algorithms are a way to explore the intersection of optimization and large scale machine learning. The aim of this work is to show that these algorithms can be competitive with projected first order algorithms (such as stochastic gradient descent) in practice.
Model interpretability is an important topic for today's Operations Research and Machine Learning. This loosely defined property is generally associated with sparsity, decision trees, clustering or some times even neural networks. In this work, we define and study a novel general class of interpretable models.