event

ISyE Guest Speaker

Primary tabs

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.

 

 

Status

  • Workflow Status:Published
  • Created By:Anita Race
  • Created:01/08/2013
  • Modified By:Fletcher Moore
  • Modified:10/07/2016

Keywords

  • No keywords were submitted.