TSPLIB数据集简介与MATLAB读取

TSPLIB是一个包含了TSP及其相关问题的问题库。其中的文件都具有.tsp后缀。关于这些文件的使用，有一篇专门的解说论文(https://docs.google.com/file/d/0B4zUGKjaO9uERU1RZDNuRkg3TW8/edit)

数据格式：

NAME : eil51

COMMENT : 51-city problem (Christofides/Eilon)

TYPE : TSP

DIMENSION : 51

EDGE_WEIGHT_TYPE : EUC_2D

NODE_COORD_SECTION

1 37 52

2 49 49

3 52 64

4 20 26

5 40 30

…

50 56 37

51 30 40

EOF

NAME就是该文件的名字。

COMMENT是对这个问题的附加说明。

TYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。

DIMENSION描述了城市的数量。

EDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。

NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。

但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。

MATLAB读取代码：

MATLAB

function [n_citys,city_position] = Read(filename)
fid = fopen(filename,'rt');
location=[];
A = [1 2];
tline = fgetl(fid);
while ischar(tline)
    if(strcmp(tline,'NODE_COORD_SECTION'))
        while ~isempty(A)
            A=fscanf(fid,'%f',[3,1]);
            if isempty(A)
                break;
            end
            location=[location;A(2:3)'];
        end
    end
    tline = fgetl(fid); 
    if strcmp(tline,'EOF')
        break;
    end
end
[m,n]=size(location);
n_citys = m;
city_position=location;
fclose(fid);
end

相关文章：

蚁群算法（ACO）旅行商问题（TSP）路径规划MATLAB实现

Github数据集仓库地址：https://github.com/xyjigsaw/Dataset（在TSPLIB目录下）

tsplib官网：https://wwwproxy.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

参考资料：https://blog.csdn.net/natsu1211/article/details/39216117

​