TSPLIB数据集简介与MATLAB读取

mutougeda

数据格式：
- h8 V- U5 o! Y# |/ f  {( Y% u
- f/ ?+ A' R1 O5 ^, O, QNAME : eil51
$ K4 e% _- \2 s. N6 Z/ v
COMMENT : 51-city problem (Christofides/Eilon)
# a# h' ~+ k9 y1 O
TYPE : TSP
% l4 K. S2 g8 [$ \% _6 b7 [
DIMENSION : 51
+ n+ f, J& b: A6 o* `) T
EDGE_WEIGHT_TYPE : EUC_2D
2 E. n/ w8 O7 ^$ p9 z
NODE_COORD_SECTION
1 q5 S4 j, B! |+ r9 j
1 37 52

2 49 49
$ H+ z; k* y! v9 _
3 52 64
8 ?* d* P- [! v" \. N
; Y+ Q8 V5 J7 w. i0 i% ]( ?  X4 20 26
2 _9 d; O4 \6 J3 x
. X) Q, K" [+ x5 40 30
$ P) O" X: Q4 v; M( j3 V; V
% }: ^7 V3 k9 \8 o2 u, i% @2 z5 @5 O…

50 56 37

51 30 40

EOF
, ]8 h% V; B# w( Z! n
0 k8 j) R7 b% @6 O: ^' z
6 }% G; i: {9 f$ d9 v
  |: m' `& |: B9 C) kNAME就是该文件的名字。

/ s& N0 O, J( k" cCOMMENT是对这个问题的附加说明。

$ H# }/ S: i2 n. e3 o! V: H% mTYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。
- k2 o9 {* k- _2 @$ H
9 C8 d' b" E# g. h% F1 h  D# gDIMENSION描述了城市的数量。

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

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

2 j/ U$ Z" A: x4 Y8 Q8 K8 _' s2 Y) p但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。
& n) T9 d) ]% i. u3 W/ e
% Y1 V( _0 l5 F# G& KMATLAB读取代码：
; q" c/ V5 R( q& v
" @: D8 y8 }1 J

• 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
  - m' J# c  Z& ^- G

) P' u/ W1 r  H3 f6 R1 m7 Y

ExxNEN

TSPLIB数据集简介与MATLAB读取