Supporting material for the article:

Estimation-based Ant Colony Optimization
and Local Search for the
Probabilistic Traveling Salesman Problem


September 2008

Table of Contents
  1. Abstract
  2. Algorithms
  3. Instances used for tuning
  4. Instances used for testing
  5. Effectiveness of 2.5-opt-EEais in pACS
  6. Numerical values and statistical bounds

1. Abstract:

The application of ant colony optimization for solving stochastic optimization problems is one of hot topics in recent years. In this paper, we customize the ant colony optimization algorithms to tackle a stochastic optimization problem, the Probabilistic Traveling Salesman Problem. The proposed customization consists of using an empirical estimation approach to evaluate the cost of the solutions constructed by the ants and integrating the newly proposed estimation-based iterative improvement algorithm as local search. Experimental results on a large number of problem instances show that the customized ant colony optimization algorithms completely outperforms the current best ant colony optimization algorithm tailored to solve the given problem. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithms for the Probabilistic Traveling Salesman Problem.

Keywords: Probabilistic Traveling Salesman Problem, Ant Colony Optimization, Iterative Improvement Algorithm, Empirical Estimation




2. Algorithms:




3. Instances used for tuning :

Experimental set File
Tuning Clustered homogeneous instances
(1.6 MB)

4. Instances used for testing :

Experimental set File
Effectiveness of 2.5-opt-EEais in pACS PTSPLIB proposed by Bianchi
(1.5 MB)
Estimation-based ant colony system Clustered homogeneous instances of size 1000 from DIMACS instance generator
(1.6 MB)
Comparison among estimation-based ACO variants Clustered homogeneous instances of size 1000 from DIMACS instance generator
(1.6 MB)

5. Effectiveness of 2.5-opt-EEais in pACS

The plots represent the cost of the solutions obtained by pACS+2.5-opt-EEais normalized by the one obtained by pACS+1-shift. The normalization is done on run by run basis for 30 runs; the normalized solution cost is then aggregated.


6. Numerical values and statistical results:

The absolute values for all the results in the form of tables. In these tables, we present the final solution quality and the corresponding computational time for each probabiltiy range. Moreover, in order to test that the observed difference between the cost of the solutions reached by the considered algorithms are significant in a statistical sense, we use a t test and we present the 95% confidence interval obtained from the t-test. The results are composed in a single pdf file:

Format  
PDF (click the above icon to see/download the results)