*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Dynamic Programming Approximations for Deterministic and Stochastic Routing Problems
SPEAKER: Dr. Alejandro Toriello
ABSTRACT:
We discuss the application of approximate dynamic programming techniques to several versions of the traveling salesman problem (TSP), with the goal of obtaining tractable lower bounds and high-quality solutions. The first half of the talk focuses on deterministic problems, including a new family of polyhedral lower bounds for the TSP and heuristic techniques that combine ideas from integer and dynamic programming. The second half extends our approach to stochastic models in which information is revealed dynamically; the motivating application is real-time vehicle routing. For a dynamic TSP with stochastic arc costs, we discuss how our bounding techniques extend, when they are efficiently solvable, and how to derive policies from them with performance guarantees and good empirical results.
