A Dynamic Traveling Salesman Problem with Stochastic Arc Costs
Alejandro Toriello (toriellousc.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.
Entry Submitted: 08/31/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|