Online optimization in routing and scheduling
<-- Return to the list
Date: 12-09-2008
Start Time:
1:00pm
End Time: 2:00pm
Speaker: Patrick Jaillet, Massachusetts Institute of Technology
Location: 303 Mudd
ABSTRACT
An online problem is one that must be “solved” without knowing the future or without having complete information. One common approach to evaluating strategies for such problems is to assume a specific stochastic model of the unknown and use various probabilistic tools. Another approach, sometimes called competitive analysis, and related to min-max strategies in game theory, evaluates strategies under worst-case scenarios.
We first present results we have obtained on online routing and scheduling. In particular, we consider first online routing optimization problems such as the Online TSP and its variants, where the objective is to minimize the time needed to visit a set of locations under various constraints; the problems are online because the set of locations are revealed incrementally over time. We will look at optimal online algorithms; at improved competitive ratios under resource augmentation; and at behavior under general stochastic structures for the problem data, unknown and unused by the online player.
We then consider results we have recently obtained on similar problems but with a twist - when one can reject requests along the way.
We conclude with open research questions.
BIO
Dr. Patrick Jaillet is the Edmund K. Turner Professor and Head of Civil and Environmental Engineering at MIT. From 1991 to 2002 he was a professor at the University of Texas in Austin, the last five years as the chair of the Department of Management Science and Information Systems with a joint appointment in the Department of Civil Engineering. He co-founded and was director of UT's Center for Computational Finance. Before his appointment at UT Austin, he was a faculty in the applied mathematics department at the Ecole Nationale de Ponts et Chaussée in Paris. He received the Diplôme d'Ingénieur from the Ecole Nationale des Travaux Publics de l'Etat in France, then moved on to MIT where he received the SM in Transportation (1982) followed by a PhD in Operations Research (1985).
Dr. Jaillet's research interests include on-line problems; real-time and dynamic optimization; network design and optimization; probabilistic combinatorial optimization; and financial engineering. His research has been funded by NSF, ONR, USDOT, and from private funds (e.g., UPS, Indosuez Bank). Professor Jaillet has taught courses in combinatorial optimization; network optimization; probabilistic methods in operations research; stochastic analysis; risk management; and mathematics in finance. Dr. Jaillet's consulting works include supply chain strategy, logistics and distribution optimization, electronic marketplace design, and development of optimization solutions in various industries, including automotive, financial and manufacturing.
Dr. Jaillet is a member of the Institute for Operations Research and Management Science Society (INFORMS), the Mathematical Programming Society (MPS), the Society of Industrial and Applied Mathematics (SIAM), and the Bachelier Society. He is currently an Associate Editor for Networks, Transportation Science, and Naval Research Logistics, and has been an Associate Editor for Operations Research from 1994 until 2005.