Application of robust and inverse optimization in transportation

We study the use of inverse and robust optimization to address two problems in transportation: finding the travel times and designing a transportation network. We assume that users choose the route selfishly and the flow will eventually reach an equilibrium state (User Equilibrium). The first part of the thesis demonstrates how inverse and robust optimization can be used to find the actual travel times given a stable flow on the network and some noisy information on travel times from different users. We model the users' perception of travel times using three different sets and solve the robust inverse problem for all of them. We also extend the idea to find parametric functional forms for travel times given historical data. Our numerical results illustrate the significant improvement obtained by our models over a simple fitting model. The second part of the thesis considers the network design problem under demand uncertainty. We show that for affine travel time functions, the deterministic problem can be formulated as a mixed integer programming problem with quadratic objective and linear constraints. For the robust network design problem, we propose a decomposition scheme: breaking a tri-level programming problem into two smaller problems and re-iterating until a good solution is obtained. To deal with the expensive computation required by large networks, we also propose a heuristic robust simulated annealing approach. The heuristic algorithm is computationally tractable and provides some encouragingly results in our simulations.

Department dc:contributor.department

Massachusetts Institute of Technology. Computation for Design and Optimization Program.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2010

Author dc:creator

• Nguyen, Thai Dung

Advisor dc:contributor.advisor

• Dimitris J. Bertsimas and Georgia Perakis.

• Computation for Design and Optimization Program.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/62482

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/62482