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
M. Birattari, P. Balaprakash, T. Stützle, and M. Dorigo. Estimation-based Local Search for Stochastic Combinatorial Optimization. Technical Report TR/IRIDIA/2007-003, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium, February 2007.

Abstract

In recent years, much attention has been devoted to the development of metaheuristics and local search algorithms for tackling stochastic combinatorial optimization problems. This paper focuses on local search algorithms; their effectiveness is greatly determined by the evaluation procedure that is used to select the best of several solutions in the presence of uncertainty. In this paper, we propose an effective evaluation procedure that makes use of empirical estimation techniques. We illustrate our approach and assess its performance on the probabilistic traveling salesman problem. Experimental results on a large set of instances show that our approach can lead to a very fast and highly effective local search algorithms.


Updated: 2017-03-27