Supporting material for the article:

Estimation-based Metaheuristics for the
Probabilistic Traveling Salesman Problem

First generated: November 2008. Last update:May 2009

Table of Contents

Abstract
Algorithms
Tuning
Instances used for testing
Comparison between estimation-based algorithms under 100 CPU seconds
Comparison between estimation-based algorithms under 1000 CPU seconds
Comparison with pACS+1-shift
Numerical values and statistical bounds

1. Abstract:

The Probabilistic Traveling Salesman Problem (PTSP) that we tackle in this paper is a central problem in stochastic vehicle routing. Recently, it has been shown that empirical estimation is a promising approach to tackle the PTSP. Based on this approach, a high performing local search algorithm has been developed. In this paper, we customize several metaheuristics to solve the PTSP. This customization consists in using the estimation approach to evaluate the solutions and the recently developed estimation-based local search to improve them. We experimentally evaluate the performances of the customized estimation-based metaheuristics. The experimental results show that a customized memetic algorithm is highly effective and it outperforms the current state-of-the-art algorithms on a number of instances.

Keywords: Probabilistic Traveling Salesman Problem, Metaheuristics, Iterative Improvement Algorithm, Empirical Estimation

2. Algorithms:

2.5-opt-EEais: The state-of-the-art estimation-based local search for the PTSP.
pACS+1-shift: The state-of-the-art ant colony optimization algorith for the PTSP; It is an ant colony system that uses the closed-form expression with 1-shift local search.
HybMSPSO: Hybrid multiple particle swarm optimization algorithm. It uses the closed-form expression to compute the cost of a solution.
RRLS-EE: Estimation-based random restart local search with 2.5-opt-EEais local search.
ILS-EE: Estimation-based iterated local search with 2.5-opt-EEais local search.
MAGX-EE: Estimation-based Memetic algorithm with 2.5-opt-EEais local search.
ACS-EE: Estimation-based ant colony system with 2.5-opt-EEais local search.

3. Tuning :

Experimental set	File
`Tuning instances`	Clustered instances of size 1000 (3.3 MB)
`Parameter configutations`	A set of 10 parameter configurations for each algorithm on 100 and 1000 CPU seconds (4.4 KB)

4. Instances used for testing :

Experimental set	File
`Comparison between estimation-based algorithms`	Clustered instances of size 1000 from DIMACS instance generator (17.8 MB)
`Comparison with analytical computation algorithms and concorde`	Instances generated according to the scheme proposed by Bianchi (2006) (2.4 MB)

5. Comparison between estimation-based algorithms under 100 CPU seconds

Experimental results on clustered PTSP instances of size 1000 under 100 CPU seconds. The plots represent the cost of the solutions obtained by ILS-EE, MAGX-EE, and ACS-EE normalized by the one obtained by RRLS-EE. The normalization is done on a instance-by-instance basis for 50 instances; the normalized solution cost is then aggregated.

6. Comparison between estimation-based algorithms under 1000 CPU seconds

Experimental results on clustered PTSP instances of size 1000 under 1000 CPU seconds. The plots represent the cost of the solutions obtained by ILS-EE, MAGX-EE, and ACS-EE normalized by the one obtained by RRLS-EE. The normalization is done on a instance-by-instance basis for 50 instances; the normalized solution cost is then aggregated.

7. Comparison with pACS+1-shift

The plots represent the cost of the solutions obtained by MAGX-EE normalized by the one obtained by pACS+1-shift. The normalization is done on a run-by-run basis for 10 runs; the normalized solution cost is then aggregated.

8. 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)