TSPLIB数据集简介与MATLAB读取

mutougeda

数据格式：

NAME : eil51

COMMENT : 51-city problem (Christofides/Eilon)

1 r0 d6 B- a/ v4 TTYPE : TSP
4 A: e$ w6 m8 j) y9 T: ^
DIMENSION : 51
# ?% m  |! o  e
EDGE_WEIGHT_TYPE : EUC_2D

NODE_COORD_SECTION
: c1 g+ f$ _4 F4 d2 G" J
/ B6 ^& l% a; a4 A5 d$ V1 O1 37 52
& P) t/ Y- a+ P7 J/ z6 ^9 h. {& {( m/ m2 x
2 49 49
$ r! w5 N6 i# `, b
3 52 64
% C& ]5 f* q. e/ J: O: @" ?
4 20 26

5 40 30

…
7 `3 Q! o6 [3 F! S5 y
- K9 [( r3 A9 H50 56 37
( _; B% M, `& Y9 h/ Q
" k. H" o6 u* O- i51 30 40

EOF



: P& t- M8 j2 l. N4 yNAME就是该文件的名字。
( z5 |" \  ^+ v" H, E
COMMENT是对这个问题的附加说明。
8 ~. @5 ?4 I. r: t' z
" |, ~+ I& o' W- O; GTYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。

DIMENSION描述了城市的数量。

EDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。

( D3 j; f' Y, m& \  K$ @, |$ |NODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。
: f% o3 E; ]) S) G$ J5 @) x9 {+ r# G' ?$ Q
+ a5 Z& Z- o0 Z+ R但是需要注意的是，EDGE_WEIGHT_TYPE并不是只有EUC_2D一种，而是有13种之多。各种类型有对应的距离计算方法，如曼哈顿距离，地理距离等，这里我就不一一列举了，论文中有详细的叙述。这里我只单独提一下出现最多的一种类型EXPLICIT，这种类型和其他的区别较大，城市间的距离是显式给出的，无需再计算。
4 e( o; ]+ g1 `7 H6 w8 t
7 ]+ f8 [4 q  |' N8 D( [0 r$ {% RMATLAB读取代码：
8 B# E& ]/ l* a$ Q* Q5 j

• 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
  6 p0 T9 R4 e! I+ s4 X

& l- Y9 d% D8 c& ~
- r9 ?7 {) B3 t* u# C" p; e

ExxNEN

TSPLIB数据集简介与MATLAB读取