GTSP instances

Here you can download instances of the Generalised Travelling Salesman Problem that were generated from TSPLIB by applying the clustering procedure of Fischetti, Salazar and Toth (see M. Fischetti, J.J. Salazar González, P. Toth "A Branch-and-Cut Algorithm for the Symmetric Generalized Travelling Salesman Problem" Operations Research 45, 55-67, 1997).

Download

• All instances (both symmetric and asymmetric) can be downloaded as a single file here
• All symmetric instances can be downloaded here
• All asymmetric instances can be downloaded here
• Individual symmetric instances can be downloaded here
• Individual asymmetric instances can be downloaded here

All files are in .tar.gz format

File format

File format is an extension of the TSPLIB format. It differs from the original format in the following respects:

1. The TYPE entry is set to "GTSP" or "AGTSP" for symmetric and asymmetric instances of GTSP respectively (similar to "TSP"/"ATSP" in the original TSPLIB format).
2. New entry GTSP_SETS: M (where M is a positive integer) defines the number of clusters in this instance. This is used in conjunction with GTSP_SET_SECTION defined below.
3. New section GTSP_SET_SECTION defines which nodes belong to which clusters. This section contains exactly M entries, where M is the number of clusters (see GTSP_SETS above). Each entry has the following format:
   m v₁ v₂ ... v_k(m) -1, where m is the cluster number (clusters are numbered from 1 to M), and v₁ v₂ ... v_k(m) are vertices comprising cluster m (vertices are numbered from 1 to N).

Example (4br17.gtsp):

NAME:  4br17
TYPE: AGTSP
COMMENT: 17 city problem (Repetto)
DIMENSION:  17
GTSP_SETS: 4
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX 
EDGE_WEIGHT_SECTION
 9999    3    5   48   48    8    8    5    5    3    3    0    3    5    8    8    5
    3 9999    3   48   48    8    8    5    5    0    0    3    0    3    8    8    5
    5    3 9999   72   72   48   48   24   24    3    3    5    3    0   48   48   24
   48   48   74 9999    0    6    6   12   12   48   48   48   48   74    6    6   12
   48   48   74    0 9999    6    6   12   12   48   48   48   48   74    6    6   12
    8    8   50    6    6 9999    0    8    8    8    8    8    8   50    0    0    8
    8    8   50    6    6    0 9999    8    8    8    8    8    8   50    0    0    8
    5    5   26   12   12    8    8 9999    0    5    5    5    5   26    8    8    0
    5    5   26   12   12    8    8    0 9999    5    5    5    5   26    8    8    0
    3    0    3   48   48    8    8    5    5 9999    0    3    0    3    8    8    5
    3    0    3   48   48    8    8    5    5    0 9999    3    0    3    8    8    5
    0    3    5   48   48    8    8    5    5    3    3 9999    3    5    8    8    5
    3    0    3   48   48    8    8    5    5    0    0    3 9999    3    8    8    5
    5    3    0   72   72   48   48   24   24    3    3    5    3 9999   48   48   24
    8    8   50    6    6    0    0    8    8    8    8    8    8   50 9999    0    8
    8    8   50    6    6    0    0    8    8    8    8    8    8   50    0 9999    8
    5    5   26   12   12    8    8    0    0    5    5    5    5   26    8    8 9999
GTSP_SET_SECTION:
1 4 5 -1
2 1 2 3 10 11 12 13 14 -1
3 8 9 17 -1
4 6 7 15 16 -1
EOF