## 启发式算法解决广义旅行商问题
#### 简介
使用 <u>模拟退火</u>、<u>禁忌搜索</u>、<u>遗传算法</u>和<u>蚁群算法</u>共四种启发式算法来解决**广义旅行商问题**
#### 问题实例
[问题实例链接](./GTSP_instance.md)
- GTSP(9,5) GTSP(17,11) GTSP(24,15) GTSP(31,16) GTSP(39,25)
#### 算法流程
#### 结果分析
##### 复杂度
> 针对五种GTSP实例，分别迭代100000次，计算其运行时间
| 时间\s | 遗传算法 | 蚁群算法 | 模拟退火 | 禁忌搜索 |
| ---- | -------- | -------- | -------- | -------- |
|**GTSP(9,5)**| 215.1 | 1135.8 | 23.75 | 41.35 |
|**GTSP(17,11)**| 291.5 | 4629.4 | 25.61 | 336.3 |
|**GTSP(24,15)**| 416.3 | 8874.4 | 37.50 | 510.8 |
|**GTSP(31,16)**| 522.7 | 11344.5 | 40.08 | 730.5 |
|**GTSP(39,25)**| 617.2 | 15768.9 | 57.90 | 1624.0 |
|平均 | 412.56 | 8,350.6 | 36.97 | 648.58 |
##### 收敛性
> 针对五种GTSP实例，分别迭代100000次，查看其每次迭代解的路径总距离
###### GTSP(9,5)
###### GTSP(17,11)
###### GTSP(24,15)
###### GTSP(31,16)
###### GTSP(39,25)
##### 解比较
> 针对五种GTSP实例，分别迭代100000次，查看最后解的效果
###### GTSP(9,5)
###### GTSP(17,11)
###### GTSP(24,15)
###### GTSP(31,16)
###### GTSP(39,25)
基于Python实现的多种启发式算法解决广义旅行商问题.zip
需积分: 1 159 浏览量
2024-05-11
09:36:36
上传
评论
收藏 2.71MB ZIP 举报
基于Python实现的多种启发式算法解决广义旅行商问题.zip （67个子文件） 
基于Python实现的多种启发式算法解决广义旅行商问题 algorithms 
AntColonyAlgorithm.py 6KB Heuristic.py 381B TabuSearch.py 4KB GeneticAlgorithm.py 6KB SimulatedAnnealing.py 3KB main.py 11KB GTSP_instance.md 5KB images 
iteration_39_25_SA.png 22KB solution_17_11_AC.png 29KB AC.png 58KB TS.drawio 7KB SA.drawio 9KB
solution_9_5.jpg 168KB solution_9_5_SA.png 23KB solution_39_25.jpg 233KB solution_17_11_TS.png 29KB iteration_24_15_GA.png 29KB solution_31_16.jpg 204KB solution_39_25_AS.png 37KB iteration_9_5_AC.png 14KB iteration_17_11_SA.png 28KB iteration_24_15_SA.png 30KB solution_17_11.jpg 193KB iteration_31_16_SA.png 23KB solution_17_11_GA.png 29KB iteration_31_16.jpg 219KB solution_31_16_TS.png 31KB iteration_9_5_GA.png 18KB AC.drawio 9KB iteration_17_11_AC.png 15KB iteration_9_5.jpg 250KB solution_39_25_TS.png 39KB solution_9_5_GA.png 23KB solution_39_25_GA.png 42KB solution_24_15_AC.png 32KB iteration_31_16_AC.png 15KB solution_9_5_AC.png 23KB iteration_17_11_GA.png 29KB solution_39_25_AC.png 45KB iteration_24_15.jpg 249KB TS.png 47KB solution_17_11_SA.png 29KB solution_24_15_TS.png 30KB iteration_39_25_TS.png 16KB iteration_9_5_TS.png 17KB solution_31_16_GA.png 29KB GA.png 57KB solution_31_16_SA.png 31KB iteration_39_25_AC.png 14KB iteration_31_16_TS.png 16KB GA.drawio 7KB solution_31_16_AC.png 32KB solution_24_15.jpg 200KB iteration_39_25.jpg 234KB iteration_31_16_GA.png 29KB solution_9_5_TS.png 23KB iteration_39_25_GA.png 34KB iteration_17_11_TS.png 14KB iteration_24_15_AC.png 16KB iteration_9_5_SA.png 24KB iteration_17_11.jpg 233KB iteration_24_15_TS.png 15KB solution_24_15_GA.png 30KB solution_24_15_SA.png 31KB process_total.jpg 145KB SA.png 50KB README.md 2KB资源评论
