TSPLIB数据集简介与MATLAB读取

mutougeda

数据格式：

* x% W- F  ~1 U3 ^  Z! c# n# l3 dNAME : eil51

COMMENT : 51-city problem (Christofides/Eilon)
2 e( A9 P3 I- g# {* f: X1 J
TYPE : TSP

DIMENSION : 51

EDGE_WEIGHT_TYPE : EUC_2D

6 m; w$ S# Q! g9 q! A+ uNODE_COORD_SECTION

1 37 52
4 c7 u  e" p! q! g3 g
2 49 49

' L: n7 q5 ?( D$ S6 V" g6 A2 f& t3 52 64

' N. e7 D$ Z0 D1 v8 B1 P1 F4 20 26
% Y5 s: c9 ]" s) r9 q5 f1 z% Y
5 40 30
7 o1 V& V  A/ e2 H( c, Q
…

50 56 37
/ R7 d+ J2 o' _; k# i% `
51 30 40
+ j5 r2 r) W! n. O' ?$ n& T
. G* k: Y; r, ]# @1 `/ R! QEOF



NAME就是该文件的名字。

- ]% I2 u# ~( T; P2 Z4 ^5 wCOMMENT是对这个问题的附加说明。

2 m& J. Y4 V% K" aTYPE描述了问题的类型，因为TSPLIB中还包含了一些其他类型的问题，但是这里我们只关注TSP类型。

. q6 _5 o8 k% g9 L/ {& B! c4 J. DDIMENSION描述了城市的数量。
2 u$ ~6 J) B, \5 D
3 F' Y1 A8 k$ Z- B- EEDGE_WEIGHT_TYPE 描述了两个城市间cost的类型，这里是我们最为熟悉的2D欧几里得距离。

; ~% m* q* A1 y" c: p9 pNODE_COORD_SECTION描述了各个城市的2D欧几里得坐标。每一行按照城市编号，X坐标，Y坐标的顺序。

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

8 y) t' [6 e' E9 C" FMATLAB读取代码：
5 J- B2 r" p) N# |9 S& @2 T

• 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读取