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.
Citation
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California. June, 2013.