Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

Prasanna Balaprakash, Mauro Birattari, Thomas Stützle, Zhi Yuan, Marco Dorigo

Research output: Contribution to journalArticlepeer-review

47 Scopus citations

Abstract

The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.

Original languageEnglish
Pages (from-to)223-242
Number of pages20
JournalSwarm Intelligence
Volume3
Issue number3
DOIs
StatePublished - 2009
Externally publishedYes

Funding

Acknowledgements The authors thank Leonora Bianchi for providing the source code of pACS+1-shift. This research has been supported by COMP2SYS, an Early Stage Training project funded by the European Commission within the Marie Curie Actions program (MEST-CT-2004-505079), and by ANTS and META-X, which are ARC projects funded by the French Community of Belgium. The authors acknowledge support from the fund for scientific research F.R.S.-FNRS of the French Community of Belgium, of which PB and ZY are research fellows, MB and TS are research associates, and MD is a research director.

Keywords

  • Ant colony optimization
  • Empirical estimation
  • Estimation-based local search
  • Probabilistic traveling salesman problem

Fingerprint

Dive into the research topics of 'Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem'. Together they form a unique fingerprint.

Cite this