ρmTSP: multiobjective Travel Salesman Problem with tunable objective correlation

| Description | Properties | Format | Generator | Instances |

Description

The three main parameters of the family of ρmTSP benchmarks are:

  • ρ: the objective correlation coefficient
  • M: the number of objective functions
  • N: the number of cities
  • TYPE: the type of instance


The ρmTSP is described in:

  • B. Derbel, A. Liefooghe, S. Verel, On the Design and Analysis of Multiobjective TSP Instances with Correlated Objectives (in preparation)
  • B. Derbel, A. Liefooghe, Q. Zhang, H. E. Aguirre, K. Tanaka, Multi-objective Local Search Based on Decomposition. 14th International Conference on Parallel Problem Solving from Nature (PPSN XIV), LNCS, pages 431-441, Edinburgh, UK, September 17-21, 2016.


Properties

  • The following figure illustrates the measured correlation between edge costs (average Pearson coefficient between pairwise objectives) for N=100
  • The following figure illustrates the measured correlation between objective values (average Pearson coefficient between pairwise objectives) for N=100


Format

The file format of a ρmTSP instance contains two sections, inspired by the DIMACS single objective instances format, and existing uncorrelated instances mTSP. The file format is described in details in the following.

a) Heading section

  1. The section has exactly 10 lines being the heading of the instance file
  2. The section provides information concerning the instance, i.e.,
    1. NAME : the file name
    2. TYPE : the type of instance (RUE or RDM or REBDM)
    3. N : the number of cities
    4. M : the number of objectives
    5. ρ: correlation parameter used to generate the instance
    6. cor : measured correlation between the edge-costs (average pair-wise Pearson correlation coefficient)
    7. seed : the seed value used to generate the instance
    8. EDGE_WEIGHT_TYPE : EXPLICIT (edge costs are explicitly given)
    9. EDGE_WEIGHT_FORMAT : UPPER_DIAG_ROW
    10. EDGE_WEIGHT_SECTION

b) Problem section

  1. The section provides the distance matrix between pair-wise cities (only symmetric TSP are considered)
  2. The section is made of exactly N*(N-1)/2 + N lines
  3. The line format is the following:
     i j c_{1,i,j} ... c_{M,i,j} 

where i and j are the indices of two cities and c_{m,i,j} is the (positive integer) cost between city i and city j with respect to objective m. These fields are separated by a blank or by TAB characters

Example

Below we provide one example for an instance with a negative correlation ρ=-0.4, N=7 cities, and M=2 objectives.

Following the heading section, one can see the cost matrices (integer values) just after the EDGE_WEIGHT_SECTION line.

NAME : RDM_-0.4_2_7_0.dat
TYPE : RDM
N : 7
M : 2
rho : -0.4
cor : -0.5833485
seed : 0
EDGE_WEIGHT_TYPE : EXPLICIT
EDGE_WEIGHT_FORMAT : UPPER_DIAG_ROW
EDGE_WEIGHT_SECTION
1 1 0 0
1 2 459 3600
1 3 2595 1630
1 4 269 3369
1 5 668 3868
1 6 1196 2373
1 7 3403 134
2 2 0 0
2 3 3918 1528
2 4 3699 3007
2 5 2200 2183
2 6 130 4403
2 7 1626 3692
3 3 0 0
3 4 3657 1479
3 5 4053 1205
3 6 1971 1173
3 7 1590 854
4 4 0 0
4 5 1900 844
4 6 2272 3004
4 7 2381 348
5 5 0 0
5 6 1855 3120
5 7 2399 104
6 6 0 0
6 7 2033 1393
7 7 0 0

Source code of generator

The source code of a instance generator (in R) are available on the svn of the project:

svn checkout http://svn.code.sf.net/p/mocobench/code/trunk/rmtsp/generator mocobench

For more details on project svn, see the sourceforge repository.

You can download the generator which is written in R: rmtsp_gen.R
If you need to install R, please visit the official page of R project


Data files of instances

All instance files are available on the svn of the project. See svn to access directly with svn.

If you want to access only to some instances, you can browse the repository: browse instances repository.

File names are normalized: TYPE_<rho>_<M>_<N>_<seed>.dat
where <rho>, <M>, and <N> are the main parameters of the instance, and <seed> is the random seed used to produce the instance with rmtsp_gen.R.

You can easily produce other instances with the available scripts written in bash using the generator in R.