TSPLIB数据集简介与MATLAB读取

mutougeda

数据格式：

NAME : eil51

  c# S; G  s0 K6 h! e% dCOMMENT : 51-city problem (Christofides/Eilon)
6 J1 @: X$ k% _$ U, _- O0 \
TYPE : TSP
$ U1 g0 ~$ ]) e8 m$ T$ P
DIMENSION : 51
0 Y. [8 O8 g+ j. }  a! N0 J6 z$ V
EDGE_WEIGHT_TYPE : EUC_2D
% T: J- [* ?! {+ @3 `
NODE_COORD_SECTION

9 J+ v* l- b( U5 G  A0 m5 z2 |+ K* u1 37 52
8 \: g$ Z9 i# B7 @
2 49 49
9 Z; r9 }6 L2 h$ k$ W6 |
5 Q* q1 U* K1 i) m7 c3 52 64

4 20 26

5 40 30
2 H- V! V% W% t& m* i
/ j0 f; Y2 O/ H7 f: |4 p7 y…

* B& k2 u+ s" ~4 I/ Q8 `50 56 37
  n( a+ J) Z' z6 c& u
51 30 40
3 L1 s/ c; E5 b+ r3 W/ T
EOF
- N* F( q" K8 ]
; o: _: B) S2 W, l  |4 F# ^* q

" K1 G: B1 C8 t% WNAME就是该文件的名字。
3 C4 C1 H- I; X( J
3 V0 B( R' Y: kCOMMENT是对这个问题的附加说明。

TYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。
% a; |" L$ ]6 A- @: U4 q2 q
2 [( b% l: i6 d6 n( w  f& D. }" QDIMENSION描述了城市的数量。
" w: a# i# `: P2 j2 W. R/ ^
EDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。

6 I* m  Q% L* [6 v4 ]NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。
& E( k9 A: |* G% y8 C4 q
但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。
9 E. a, J$ V  |4 A$ q! f9 H
MATLAB读取代码：
0 z6 e6 K0 a) `2 _( K. d

• 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
    U# F( O- Y0 O! q

- W$ }( B: N$ J6 r

ExxNEN

TSPLIB数据集简介与MATLAB读取