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.