Benchmark results for the Biobjective Traveling Salesman Problem

This webpage supports the article "Design and analysis of stochastic local search for the multiobjective traveling salesman problem" by L. Paquete and T. Stützle.

Short-cut:

Experimental Analysis of Components
Comparison with MOGLS

Three types of biobjective TSP instances were considered:

Euclidean instances, where each distance value for each objective corresponds to the Euclidean distance between a pair of cities; the coordinates of each city is an integer drawn from a uniform distribution within the range [0; 3163];
Random Distance Matrix (RDM) instances, where each distance value at each objective is an integer drawn from a uniform distribution within the range [0; 4473];
Mixed instances, where one objective is Euclidean, while the other is RDM.

The instances are available here

Five types of SLS components were tested:

Search strategy
Neighbourhood structure
Component-wise step (only for instances of size 100)
Search length
Number of scalarizations

The experimental methodology followed three steps:

Evaluate better relations between pairs of SLS components;
Apply statistical hypothesis over the empirical attainment functions (EAF) between pairs of SLS components (not shown since the null hypothesis was always rejected);
Generate plots of positive and negative differences between EAFs for each pair of SLS components;

Notes (see publication for more details):

In the mixed instances, the second phase of 2phaseE starts from the Euclidean objective, whereas 2phaseR starts from the RDM objective.
The table for better relations is understood as follows: Level A in the row is in x% of the cases better than level B in the column;
The values presented for the better relations are averaged over all the instances of the same type and same size;
Each EAF plot shown in this webpage corresponds to a single instance;
The lower bound in the EAF plots is given by optimal solutions for several weighted sum formulations of a 2-matching problem;
Only absolute differences larger or equal than 20% are shown in the EAF plots;
The EAF plots between n and 10n scalarizations and between 0 and 100 perturbations are not shown.

Euclidean instances

Size (n)

100

300

500

Search Strategy:

Better Relations:

	Restart	2phase
Restart	-	0.0%
2phase	0.0%	-

EAF plots: Restart vs. 2phase

Better Relations:

	Restart	2phase
Restart	-	0.0%
2phase	4.1%	-

EAF plots: Restart vs. 2phase

Better Relations:

	Restart	2phase
Restart	-	0.0%
2phase	10.1%	-

EAF plots: Restart vs. 2phase

Neighborhood Structure

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	1.2%	-

EAF plots: 2-opt vs. 3-opt

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	43.0%	-

EAF plots: 2-opt vs. 3-opt

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	53.1%	-

EAF plots: 2-opt vs. 3-opt

Component-wise Step

Better Relations:

	False	True
False	-	0.0%
True	0.0%	-

EAF plots: False vs. True

Not tested; always shown to have a positive effect in preliminary experiments.

Not tested; always shown to have a positive effect in preliminary experiments.

Search Length

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	15.1%	-	0.0%
100	20.4%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	65.3%	-	0.0%
100	80.0%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	71.8%	-	0.0%
100	79.9%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Number of Scalarizations

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	0.0%	-	0.0%
10n	0.0%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	0.0%	-	0.0%
10n	0.0%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	0.0%	-	0.0%
10n	0.0%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Random Instances

Size (n)

100

300

500

Search Strategy:

Better Relations:

	Restart	2phase
Restart	-	0.0%
2phase	6.4%	-

EAF plots: Restart vs. 2phase

Better Relations:

	Restart	2phase
Restart	-	0.0%
2phase	31.6%	-

EAF plots: Restart vs. 2phase

Better Relations:

	Restart	2phase
Restart	-	0.0%
2phase	31.7%	-

EAF plots: Restart vs. 2phase

Neighborhood Structure

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	50.3%	-

EAF plots: 2-opt vs. 3-opt

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	67.4%	-

EAF plots: 2-opt vs. 3-opt

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	75.0%	-

EAF plots: 2-opt vs. 3-opt

Component-wise Step

Better Relations:

	False	True
False	-	0.0%
True	0.0%	-

EAF plots: False vs. True

Not tested; always shown to have a positive effect in preliminary experiments.

Search Length

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	42.6%	-	0.0%
100	54.9%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	67.0%	-	0.0%
100	77.7%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	69.0%	-	0.0%
100	74.1%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Number of Scalarizations

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	0.0%	-	0.0%
10n	0.0%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	8.3%	-	0.0%
10n	11.9%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	7.0%	-	0.0%
10n	10.5%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Mixed Instances

Size (n)

100

300

500

Search Strategy:

Better Relations:

	Restart	2phaseE	2phaseN
Restart	-	0.0%	0.0%
2phaseE	0.0%	-	0.0%
2phaseN	0.0%	0.0%	-

EAF plots: Restart vs. 2phaseE, Restart vs. 2phaseR, 2phaseE vs. 2phaseR

Better Relations:

	Restart	2phaseE	2phaseN
Restart	-	0.0%	0.0%
2phaseE	5.2%	-	0.0%
2phaseN	2.1%	0.0%	-

EAF plots: Restart vs. 2phaseE, Restart vs. 2phaseR, 2phaseE vs. 2phaseR

Better Relations:

	Restart	2phaseE	2phaseN
Restart	-	0.0%	0.0%
2phaseE	15.8%	-	0.0%
2phaseN	6.9%	0.0%	-

EAF plots: Restart vs. 2phaseE, Restart vs. 2phaseR, 2phaseE vs. 2phaseR

Neighborhood Structure

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	6.5%	-

EAF plots: 2-opt vs. 3-opt

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	22.3%	-

EAF plots: 2-opt vs. 3-opt

Better Relations:

	2-opt	3-opt
2-opt	-	0.0%
3-opt	26.2%	-

EAF plots: 2-opt vs. 3-opt

Component-wise Step

Better Relations:

	False	True
False	-	0.0%
True	0.0%	-

EAF plots: False vs. True

Not tested; always shown to have a positive effect in preliminary experiments.

Search Length

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	22.8%	-	0.0%
100	26.6%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	34.6%	-	0.0%
100	52.8%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Better Relations:

	0	50	100
0	-	0.0%	0.0%
50	40.0%	-	0.0%
100	49.7%	0.0%	-

EAF plots: 0 vs. 50, 50 vs. 100

Number of Scalarizations

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	0.0%	-	0.0%
10n	0.0%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	0.9%	-	0.0%
10n	7.3%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Better Relations:

	n	5n	10n
n	-	0.0%	0.0%
5n	1.1%	-	0.0%
10n	7.6%	0.0%	-

EAF plots: n vs. 5n, 5n vs. 10n

Comparison with MOGLS

Only the EAF plots are shown.

For the 3 objective instances, we show the EAF plots with parallel coordinates for a given range of differences.

Euclidean instances

Comparison with MOGLS

Size

100

300

2 Objectives

Euclidean

Ours vs. MOGLS

Ours vs. MOGLS

RDM

Ours vs. MOGLS

Ours vs. MOGLS

3 Objectives

Euclidean

(80%,100%]: Ours vs. MOGLS

(60%,80%]: Ours vs. MOGLS

(80%, 100%]: Ours vs. MOGLS

(60%,80%]: Ours vs. MOGLS

RDM

(80%, 100%]: Ours vs. MOGLS

(60%,80%]: Ours vs. MOGLS

(40%,60%]: Ours vs. MOGLS

(80%, 100%]: Ours vs. MOGLS

(60%, 80%]: Ours vs. MOGLS