TSPLIB数据集简介与MATLAB读取

mutougeda

数据格式：

NAME : eil51
; K8 W4 V0 \( p' D: L
COMMENT : 51-city problem (Christofides/Eilon)

+ Q; G' t( C3 z- UTYPE : TSP
) V7 b, U& Z: }- O% x
( g: D, ^$ M% W+ l4 T) JDIMENSION : 51
; X0 X7 r) k* Y+ y/ n. k. R
EDGE_WEIGHT_TYPE : EUC_2D
9 W. X( v5 x8 h" Z
NODE_COORD_SECTION
. f4 A, m1 u; @2 ~6 |$ O
1 37 52
1 V: ~- H$ h  p
5 Z  ]7 x1 w7 i* [" M0 g8 F2 49 49
( E; @- w/ P+ b3 H
8 e5 [) ]4 S, E( w! P3 X3 52 64

! S1 o; t- m) @# P4 j8 S6 Z4 20 26
0 G4 L3 G8 w  z/ }& L6 D8 [, D
5 40 30

…

50 56 37

0 @/ b! s! m* z8 D, `/ |51 30 40

EOF
) Q/ r: h- t- S' _* @

; v: D) z* G0 W* q) C  p& r# u
. r  R% y9 K. y* N) c- Z% |* i; n- HNAME就是该文件的名字。

$ s1 e& F, N7 |/ ~COMMENT是对这个问题的附加说明。

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

& O* X4 B4 |/ r" MDIMENSION描述了城市的数量。
5 \1 b- I1 X# v" t
EDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。
, m8 j% I) o0 J# }
NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。
6 o1 f4 S! N3 S
但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。

MATLAB读取代码：
9 t; p' T9 W4 x6 s( c- |
. j$ U+ p8 p* ~6 C' T4 }

• 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
  7 p; @* L' v+ U

' n& o4 Y2 l: T: p6 K# P
+ f% }6 x& }4 ~

ExxNEN

TSPLIB数据集简介与MATLAB读取