# TSP

**Repository Path**: ltstriker/TSP

## Basic Information

- **Project Name**: TSP
- **Description**: 旅行售货员问题The traveling salesman problem
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2018-11-04
- **Last Updated**: 2020-12-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# TSP

#### 项目介绍
旅行售货员问题The traveling salesman problem

#### 项目要求  
在TSPLIB（http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/，多个地址有备份；其他网站还可以找到有趣的art TSP和national TSP）中选一个大于100个城市数的TSP问题，
1.	采用多种邻域操作的局部搜索local search策略求解；
2.	在局部搜索策略的基础上，加入模拟退火simulated annealing策略，并比较两者的效果；
3. 要求求得的解不要超过最优值的10％，并能够提供可视化，观察路径的变化和交叉程度。



#### 数据
数据格式：
TYPE : TSP
DIMENSION : 131
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION

表示图是完全无向图。
共DIMENSION个节点
节点间距离是欧几里得距离
NODE_COORD_SECTION 是一种格式：
节点序号 坐标轴1  坐标轴2

* 为了方便c读操作。。直接读数据了。格式提前判断之~
[数据来源](http://www.math.uwaterloo.ca/tsp/vlsi/index.html)  
测例一：(minimal 564 me:595+-5  5%)  T=1000 L=0.5 C=3 R=1
VLSI data  
data1.txt  
参考结果：xqf131.tout.gif

头
```
NAME : xqf131
COMMENT : Bonn VLSI data set with 131 points
COMMENT : Uni Bonn, Research Institute for Discrete Math
COMMENT : Contributed by Andre Rohe
TYPE : TSP
DIMENSION : 131
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
```
[其他来源](https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/)