0. Data files

This section provides links to tarballs containing the data files used for this work.

File Description

instances.tar.gz Raw instance files for randomly generated TSP instances. Dimension (i.e., number of objectives) is ranging from 2 to 4 objectives, with instance sizes of 100, 200 and 400 cities. For each dimension-size combination, 5 instances with different seeds have been used.

instances_pf.tar.gz Reference Pareto fronts for the instances contained in instances tarball.

File	Description
instances.tar.gz	Raw instance files for randomly generated TSP instances. Dimension (i.e., number of objectives) is ranging from 2 to 4 objectives, with instance sizes of 100, 200 and 400 cities. For each dimension-size combination, 5 instances with different seeds have been used.
instances_pf.tar.gz	Reference Pareto fronts for the instances contained in instances tarball.

Notes

The file names of the individual instances are built on the following structure: [type].cXXX.oYY.sZZZZ.mtsp, where [type] represents the instance type (in this work, we only consider Euclidean, symmetric, and isometric instances, hence the constant file prefix "eucl.sym.iso"), XXX represents the instance size (i.e., the number of cities), Y the number of objectives, and ZZZZ the seed used for the random number generator.
The reference Pareto front result files for each instance have been generated with an extension of Thomas Stützle's ACOTSP implementation of Ant Colony Optimization algorithm applied to the Traveling Salesman Problem. The extension of the result files is "smacotsp.res" because the results have been generated by applying an extension of the ACOTSP to multi-objective problems through multiple scalarizations of the distance matrices.

1. Comparing NSGA-II versus NSGA-II + PLS

As described in the paper, we have chosen to use a hybrid NSGA-II + PLS algorithm, because it enhances the overall performance of the algorithm in comparison with NSGA-II alone. The following plots (generated with eaftools) show the evolution of both algorithms with "EAF-snapshots" at several moments of the run.

EAF difference plot after 100 seconds execution time. Although NSGA-II begins being as good as the hybrid algorithm in the central area of the Pareto front (represented by the grey points on the plot), the latter is still better.

EAF difference plot after 200 seconds execution time. The hybrid algorithm is still outperforming NSGA-II.

EAF difference plot after 800 seconds execution time. The spreading along the Pareto optimal frontier (PF) of the hybrid algorithm has still improved, now almost covering the whole PF. This spreading happens at the cost of a relatively worse convergence towards the PF, when compared to NSGA-II. Thus, in the central area, NSGA-II now out-performs the hybrid algorithm. This difference is conjectured to be due to the use of the candidate list in the PLS sub-algorithm. It, indeed, prevents the algorithm from exploring the complete 2-exchange neighbourhood, rather limiting the possible cities considered for a 2-exchange move to a limited set of potentially most improving cities.

2. Comparing a posteriori versus a priori approaches

2.1. Solutions for different seeds

The results presented in the paper are based on instances generated with one particular seed (seed = 1235). This section presents the summarized results obtained with different instance seeds. The same preference model parameters have been used as in the paper. As can be seen, the results are very similar to those from the paper and therewith confirm the presented conclusions.