A Dynamic Traveling Salesman Problem with Stochastic Arc Costs

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.