Estimation-based local search for stochastic combinatorial optimization using delta evaluations: A case study on the probabilistic traveling salesman problem

Mauro Birattari, Prasanna Balaprakash, Thomas Stutzle, Marco Dorigo

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

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 this approach and we assess its performance on the probabilistic traveling salesman problem. Experimental results on a large set of instances show that the proposed approach can lead to a very fast and highly effective local search algorithm.

Original languageEnglish
Pages (from-to)644-658
Number of pages15
JournalINFORMS Journal on Computing
Volume20
Issue number4
DOIs
StatePublished - 2008
Externally publishedYes

Keywords

  • Iterative improvement
  • Simulation
  • Stochastic combinatorial optimization
  • Suboptimal algorithms

Fingerprint

Dive into the research topics of 'Estimation-based local search for stochastic combinatorial optimization using delta evaluations: A case study on the probabilistic traveling salesman problem'. Together they form a unique fingerprint.

Cite this