TSPLIB数据集简介与MATLAB读取

mutougeda

数据格式：

7 U' x  i: j0 v& x9 D+ R* aNAME : eil51

: N  v9 E' i# c: j: ?1 u% u. _COMMENT : 51-city problem (Christofides/Eilon)
- G$ A; C0 m8 L
TYPE : TSP

5 T, ^8 y6 H# V) M0 }DIMENSION : 51
  x- O# T9 |) }* _
2 q  {) B, ^. x# Y0 Y4 AEDGE_WEIGHT_TYPE : EUC_2D
9 D0 w( w2 X4 v4 O5 Z* F7 k* x/ l
  n: S: C! P# H! A6 Y  d& qNODE_COORD_SECTION

1 37 52
: f8 ?/ V/ {1 R% @6 K4 r
6 i4 w4 \+ o  ^' s  o$ S2 49 49

3 52 64
+ ^# I/ l# n; e9 m  |
4 20 26

5 40 30

. S3 F7 `$ D, Z0 n. T; ~* n& G…

' i0 F# I* o2 h1 W6 ~50 56 37
# l9 N6 r, U8 g3 J
7 e$ u! A$ J2 k6 g/ t51 30 40
: b9 X4 @* K+ q+ \) @
/ B; Y' x" j9 u& c# IEOF
$ X+ G; l* W, E- F# @3 W

. n/ T1 [0 g, [0 ~* ~1 f8 V" d
NAME就是该文件的名字。

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

TYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。
# S; t0 _* v9 B  c1 t( q. y: G
9 p! `7 G" R7 dDIMENSION描述了城市的数量。
0 k7 V5 J6 r( g0 f/ J' h
+ A" M3 @/ j: V' A! iEDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。

. y6 Y4 Q) T: W& G2 INODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。

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

  Y" o: q! R" e, x+ mMATLAB读取代码：

• 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
  ' @* X7 a: x0 Z, g: q/ G

4 {, J4 O/ Q0 Y4 S' T

ExxNEN

TSPLIB数据集简介与MATLAB读取