A Dynamic Traveling Salesman Problem with Stochastic Arc Costs

• 成果类型: Article
• 署名作者: Toriello, Alejandro; Haskell, William B.; Poremba, Michael
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Southern California
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2014.1301
• 发表日期: 2014
• 页码: 1107-1125
• 关键词: vehicle-routing problem; linear-programming approach; price-directed control; shortest-path problems; fleet management; algorithm; policies; demand

摘要

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.