A Dynamic Traveling Salesman Problem with Stochastic Arc Costs

Alejandro Toriello (), William B. Haskell () and Michael Poremba ()
Additional contact information
Alejandro Toriello: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
William B. Haskell: Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089
Michael Poremba: Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089

Operations Research, 2014, vol. 62, issue 5, 1107-1125

Abstract: We propose a dynamic traveling salesman problem (TSP) with stochastic arc costs motivated by applications, such as dynamic vehicle routing, in which the cost of a decision is known only probabilistically beforehand but is revealed dynamically before the decision is executed. We formulate this as a dynamic program (DP) and compare it to static counterparts to demonstrate the advantage of the dynamic paradigm over an a priori approach. We then apply approximate linear programming (ALP) to overcome the DP's curse of dimensionality, obtain a semi-infinite linear programming lower bound, and discuss its tractability. We also analyze a rollout version of the price-directed policy implied by our ALP and derive worst-case guarantees for its performance. Our computational study demonstrates the quality of a heuristically modified rollout policy using a computationally effective a posteriori bound.

Keywords: traveling salesman problem; stochastic vehicle routing; approximate dynamic program; semi-infinite linear program (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2014.1301 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:5:p:1107-1125

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().