View article

Abstract⎯ In the Dynamic and Stochastic Traveling Salesman Problem (DSTSP) a vehicle has to service a number of requests which are disclosed in a dynamic fashion over a planning horizon. When the vehicle is temporarily idle, one option is to reposition it in anticipation of future demand. The aim of this paper is to study waiting strategies for the DSTSP under a probabilistic characterization of customer requests. We determine an optimal policy through a Markov decision process and we develop both lower and upper bounds (analytically and heuristically, respectively) on the optimal policy cost. The behavior of these procedures is illustrated on a numerical example and tested on a set of random instances.