TSPLIB数据集简介与MATLAB读取

mutougeda

数据格式：
2 S! g+ a0 s) I+ D8 I7 J9 A
+ i/ p4 X1 F5 s5 N* h1 d# n8 k/ a% c% XNAME : eil51

COMMENT : 51-city problem (Christofides/Eilon)

TYPE : TSP

DIMENSION : 51

9 p. V3 {& e7 S6 [5 D8 b  S. T$ FEDGE_WEIGHT_TYPE : EUC_2D
1 Z) ^' d- D, n6 l. S% Y
, R( e: I1 U4 l9 ZNODE_COORD_SECTION
; N: Y. v( M; S% i9 j
1 37 52
; g2 v- C* n1 f
# h; n& d- E' z. \; L1 c% g* e! ?2 49 49
& I8 T! r1 W  s  N( x9 l
3 52 64

4 20 26
% Y% q' }9 [  H% c
5 40 30
) M; O' T2 y! l8 n( ]  M# M: E
& J6 B! e0 D; R; I/ u0 J# x…

, E4 ~1 o+ T) _+ \+ j  j; @/ K& W50 56 37

* F, c! y& g* h) e51 30 40

1 _6 e- c5 p; e8 X( W+ HEOF
2 Z/ C! ]0 T6 j2 J


2 m" h7 l* Y7 [- U3 UNAME就是该文件的名字。

. T' p5 a" X7 l- p2 ]COMMENT是对这个问题的附加说明。

TYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。
. n5 G' {' S1 U/ W+ j* H& a
( C; o( o6 G1 R& \DIMENSION描述了城市的数量。

' J7 _) y% P8 J7 t# uEDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。

NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。
* n" B$ }! z4 H( Y9 a& T: a
$ D: T" ?) b) C+ d# D但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。

$ N8 a; R" ?0 r) x* z. {MATLAB读取代码：

5 w6 o# B9 Y- O

• 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
  1 {# S, s0 R  g3 y. Z

6 t; Q2 e, Z2 x9 }- g
: e. ~; K- [  T% R9 u

ExxNEN

TSPLIB数据集简介与MATLAB读取