TSPLIB 是一个包含了 TSP 及其相关问题的问题库。其中的文件都具有.tsp 或.atsp 后缀,tsp
表示对称 TSP 问题,atsp 表示非对称 TSP 问题 用记事本 sublimetext 等都可以打开
NAME 就是该文件的名字。
COMMENT 是对这个问题的附加说明。
TYPE 描述了问题的类型,因为 TSPLIB 中还包含了一些其他类型的问题,但是这里我们只关
注 TSP 类型。
DIMENSION 描述了城市的数量。
EDGE_WEIGHT_TYPE 描述了两个城市间 cost 的类型,这里是我们最为熟悉的 2D 欧几里得距
离。
NODE_COORD_SECTION 描述了各个城市的 2D 欧几里得坐标。每一行按照城市编号,X 坐标,
Y 坐标的顺序。
但是需要注意的是,EDGE_WEIGHT_TYPE 并不是只有 EUC_2D 一种,而是有 13 种之多。各
种类型有对应的距离计算方法,如曼哈顿距离,地理距离等,单独提一下出现最多的一种类
型 EXPLICIT,这种类型和其他的区别较大,城市间的距离是显式给出的,无需再计算。以
gr17.tsp 为例:
NAME: gr17
TYPE: TSP
COMMENT: 17-city problem (Groetschel)
DIMENSION: 17
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
EDGE_WEIGHT_SECTION
0633 0 257 390 0 91 661 228 0 412 227
169383 0 150 488 112 120 267 0 80 572 196
77351 63 0 134 530 154 105 309 34 29 0
259555 372 175 338 264 232 249 0 505 289 262
476196 360 444 402 495 0 353 282 110 324 61
208292 250 352 154 0 324 638 437 240 421 329
297314 95 578 435 0 70 567 191 27 346 83