Estimation-based metaheuristics for the probabilistic traveling salesman problem

Prasanna Balaprakash; Mauro Birattari; Thomas Stützle; Marco Dorigo

doi:10.1016/j.cor.2009.12.005

Estimation-based metaheuristics for the probabilistic traveling salesman problem

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

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

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.

Original language	English
Pages (from-to)	1939-1951
Number of pages	13
Journal	Computers and Operations Research
Volume	37
Issue number	11
DOIs	https://doi.org/10.1016/j.cor.2009.12.005
State	Published - Nov 2010
Externally published	Yes

Funding

The authors thank Dr. Leonora Bianchi and Prof. Ann Melissa Campbell for providing the source code of pACS+1-shift and the aggregation approach, respectively. This research has been supported by , 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.

Funders	Funder number
Australian Nurse Teachers' Society
European Commission	MEST-CT-2004-505079
Fédération Wallonie-Bruxelles

Keywords

Empirical estimation
Metaheuristics
Probabilistic traveling salesman problem

Access to Document

10.1016/j.cor.2009.12.005

Cite this

@article{f7cbfb763dd04b31847b52033f23aa22,

title = "Estimation-based metaheuristics for the probabilistic traveling salesman problem",

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.",

keywords = "Empirical estimation, Metaheuristics, Probabilistic traveling salesman problem",

author = "Prasanna Balaprakash and Mauro Birattari and Thomas St{\"u}tzle and Marco Dorigo",

year = "2010",

month = nov,

doi = "10.1016/j.cor.2009.12.005",

language = "English",

volume = "37",

pages = "1939--1951",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - Estimation-based metaheuristics for the probabilistic traveling salesman problem

AU - Balaprakash, Prasanna

AU - Birattari, Mauro

AU - Stützle, Thomas

AU - Dorigo, Marco

PY - 2010/11

Y1 - 2010/11

N2 - 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.

AB - 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.

KW - Empirical estimation

KW - Metaheuristics

KW - Probabilistic traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=77951263646&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2009.12.005

DO - 10.1016/j.cor.2009.12.005

M3 - Article

AN - SCOPUS:77951263646

SN - 0305-0548

VL - 37

SP - 1939

EP - 1951

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 11

ER -

Estimation-based metaheuristics for the probabilistic traveling salesman problem

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this