TSPLIB数据集简介与MATLAB读取

mutougeda

1 C5 \$ Q9 k  j6 A& ?数据格式：
' j3 z( ]4 A( T; J5 B; ~
$ f% F  K; V- Q1 ONAME : eil51
1 r/ N- M' k; f1 u1 ]
COMMENT : 51-city problem (Christofides/Eilon)
) E3 d0 @% q/ @/ O
TYPE : TSP
6 r7 p2 E8 ]4 ~# y- ^' N
DIMENSION : 51
# @9 O2 I6 x* l2 y& _
EDGE_WEIGHT_TYPE : EUC_2D

* e+ S2 P1 s% H: J6 J2 g& P- ?5 @NODE_COORD_SECTION
( S5 `5 S' D8 V* i
/ y0 {; w" u1 o$ e1 37 52

2 49 49
; ^# _: P. [8 d: n
4 ~- M0 g, Y  {5 d0 p0 J, n3 52 64
. F) z/ Y, m  D; E" O
4 20 26
' H8 {: j, F6 l- }0 H( ?
5 40 30

…

50 56 37

5 n3 X6 }0 z& N- G2 r' }51 30 40

( Q8 @' M5 B  ~" X  lEOF



NAME就是该文件的名字。

3 B& P: H, O+ m! [8 ?3 NCOMMENT是对这个问题的附加说明。
3 d7 y4 t" b" j4 S6 ~4 e' r
, G% u9 n! b( b) x5 G& @$ \0 X: ATYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。

: c: ]' t  J! Z" W" ^DIMENSION描述了城市的数量。

9 F7 l+ |: W% ?' F5 n+ |, xEDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。

# e  l- I$ `1 q2 DNODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。
/ b# \/ f/ r& l
但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。
6 P- {. g. D# c+ `
MATLAB读取代码：
) C% G4 Q, T! `( I- P1 }) 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
  

ExxNEN

TSPLIB数据集简介与MATLAB读取