The probabilistic traveling salesman problem (PTSP) is a central problem in stochastic routing. Recently, we have shown that empirical estimation is a promising approach to devise highly effective local search algorithms for the PTSP. In this paper, we customize two metaheuristics, an iterated local search algorithm and a memetic algorithm, to solve the PTSP. This customization consists in adopting the estimation approach to evaluate the solution cost, exploiting a recently developed estimation‐based local search algorithm, and tuning the metaheuristics parameters. We present an experimental study of the estimation‐based metaheuristic algorithms on a number of instance classes. The results show that the proposed algorithms are highly effective and that they define a new state‐of‐the‐art for the PTSP.
