CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year Technical Reports
By Class By Topic By Year Technical Reports
login
P. Balaprakash, M. Birattari, T. Stützle, and M. Dorigo. Estimation-based Metaheuristics for the Probabilistic Traveling Salesman Problem. Technical Report TR/IRIDIA/2009-017, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium, June 2009.

Abstract

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.


Updated: 2017-03-27