TSPLIB数据集简介与MATLAB读取

mutougeda

1 e! y, T* Y( I: a数据格式：

NAME : eil51

COMMENT : 51-city problem (Christofides/Eilon)

  t2 X9 `( }1 n  ~! }* }; \TYPE : TSP

DIMENSION : 51

8 J5 R- s0 f# \) @- U2 Y- X9 EEDGE_WEIGHT_TYPE : EUC_2D

  e$ V0 `/ G! f& C" H: vNODE_COORD_SECTION

1 37 52
! U, x& K; Z+ I
2 49 49

3 52 64
4 E0 e: w9 `# O" F) a0 q: I7 ~, W
4 20 26

& _' ?8 r: }2 i0 j- j5 40 30
' u- u. I- s( j4 z  G! t+ ]* V
+ h+ [: X& U" v, o5 F…

* P4 {  u+ ?1 o$ l$ g3 A50 56 37

& l/ K! m8 R# ]7 y1 z3 ]) M: b51 30 40

EOF


3 j- N' c( C* r+ F
NAME就是该文件的名字。

  a2 Z0 v- P0 \5 J- zCOMMENT是对这个问题的附加说明。

TYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。
/ C8 P* V8 R5 ]0 m1 d' R- u
DIMENSION描述了城市的数量。

/ l! Q0 ^1 N4 U! a; [+ |$ nEDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。
3 a% u$ u2 Y0 K
NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。
( h! F$ R3 \  P% k% R
, f& `5 C# b& O8 X- O但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。

) q% f+ v" _+ n8 T% ]0 {/ x0 `4 `8 v/ S  P7 RMATLAB读取代码：

8 z) X  Y( @& F, k; T) C$ v8 I

• 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
  6 H; |; d" k" [. X

- n7 R3 ~3 a+ ]- i
5 _2 q* }8 Y1 U! e9 I

ExxNEN

TSPLIB数据集简介与MATLAB读取