Optimization Online


A Dynamic Traveling Salesman Problem with Stochastic Arc Costs

Alejandro Toriello (toriello***at***usc.edu)
William B. Haskell (wbhaskel***at***usc.edu)
Michael Poremba (poremba***at***usc.edu)

Abstract: We propose a dynamic traveling salesman problem (TSP) with stochastic arc costs motivated by applications, such as dynamic vehicle routing, in which a decision's cost is known only probabilistically beforehand but is revealed dynamically before the decision is executed. We formulate the problem as a dynamic program (DP) and compare it to static counterparts to demonstrate the dynamic paradigm's advantage over an a priori approach. We then apply approximate linear programming (ALP) to overcome the DP's curse of dimensionality and obtain a semi-infinite linear programming lower bound. The bound requires only expected arc costs and knowledge of the uncertainty support set, and is valid for any distribution with these parameters. Though NP-hard for arbitrary compact uncertainty sets, we show that it can be solved in polynomial time for two important classes, polytopes with polynomially many extreme points and hyper-rectangles. We also analyze the price-directed policy implied by our ALP and derive worst-case guarantees for its performance. Our computational experiments demonstrate the advantage of both the ALP bound and a related heuristic policy.

Keywords: traveling salesman problem, stochastic vehicle routing, approximate dynamic program, semi-infinite linear program

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Other Topics (Dynamic Programming )

Category 3: Infinite Dimensional Optimization (Semi-infinite Programming )

Citation: Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California. June, 2013.

Download: [PDF]

Entry Submitted: 08/31/2012
Entry Accepted: 09/01/2012
Entry Last Modified: 06/07/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society