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读取代码:

相关文章:

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

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

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

读者评分
[评分人数: 2 平均分: 5]

评论

OmegaXYZ