Applications of estimation-based SLS algorithms to stochastic routing problems P. Balaprakash, Mauro Birattari, Thomas Stuetzle, and Marco Dorigo IRIDIA-CoDE, Universit´e Libre de Bruxelles (ULB), Brussels, Belgium {pbalapra,mbiro,stuetzle,mdorigo}@ulb.ac.be In a number of combinatorial optimization problems, some of the information for when generating solutions is only available in a stochastic form. Two examples of such problems are the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic customers and demands (VRPSCD). For example, in the PTSP each node requires a visit only with a certain probability. The PTSP is commonly tackled using the a priori optimization approach: find a solution that visits all nodes before actually knowing which nodes are to be visited. From this a priori solution the associated a posteriori solution is computed after knowing which nodes need to be visited. It is obtained by skipping the nodes that do not require a visit and visiting the others in the order in which they appear in the a priori solution. The goal in the PTSP is to find an a priori solution that minimizes the expected cost of the a posteriori solution. In our research on stochastic routing problems, we have developed new iterative improvement algorithms that use estimation-based techniques in the delta evaluation for the PTSP [1]. Additional developments include the adoption of the adaptive determination of the appropriate sample size and the usage of importance sampling to improve the iterative improvement algorithms for cases [2], where the probability that a node requires visit is very low. In this presentation, we will give an overview of the estimation-based iterative improvement algorithms we implemented for the PTSP. Next, we present computational results for stochastic local search methods that make use of these iterative improvement algorithms and we show that our best performing algorithms are new state-of-the-art methods for the PTSP. Finally, we also consider the extension of the estimation-based delta evaluation to the VRPSCD and compare the initial computational results for our methods to the previously best algorithms.