大规模TSP问题的层次求解法

摘要

旅行商问题(Traveling Salesman Problem，TSP)是在数学和计算机科学当中最有研究价值的组合优化NP难问题之一.自从1932年提出该问题以来，诸多研究者表现出极大的兴趣，并且很快就有研究者投入大量时间去研究它.当TSP问题有比较小的规模时候，会有很多算法可以高效的求解它的精确解，但随着TSP问题的规模不断的增加，问题的求解难度也会不断增加，所以求解时间较长或是在短时间里无法得到所期望的结果.TSP问题尤其是大规模的TSP问题的求解，不但有着很重要的学术价值、理论价值，更会帮助解决现实社会中一些实际问题，它的实用性非常高.因此，这一NP难问题一直受到中外研究者的广泛关注.为了在求解TSP问题上有新的突破，人们开始研究一些新的算法——仿生算法.随着人们提出群智能的思想，一系列智能算法相继提出，比如禁忌搜索、神经网络、模拟退火、遗传算法、蚁群算法、DNA计算等优化算法.这些算法都可以用来求解TSP问题，但是这些算法有它们的一定优势，也存在它们各自的缺陷.其中蚁群优化算法是以解决TSP问题而提出的，该算法比起其他的优化算法表现更好.虽然蚁群算法能很好的解决小规模的TSP问题，但是人们的目的不止要解决小规模的TSP问题.随着TSP问题规模的增长，蚁群算法以及其它算法的缺点就逐一表现出来了.针对于这些不足，本文提出了两种新的混合算法.本文的主要内容如下:
　　1、本文首先探讨了选题的现实意义，研究背景以及国内外的研究趋势.简单总结了求解TSP问题的算法，主要分两大类，精确算法和启发式算法.
　　2、针对小规模TSP问题，本文结合Delaunay三角剖分与蚁群算法求解小规模的TSP问题，然后在已知的可行解上进行分段优化.
　　3、本文提出了一种大规模TSP问题的层次求解算法，该算法首先采用聚类算法把大规模TSP问题转化成若干个小规模的城市集合，然后把这个问题看作是广义旅行商问题(Generalized Traveling Salesman Problem，GTSP)，即把求解大规模TSP问题转换成求解GTSP问题和几个小规模TSP问题.然后用传统蚁群算法求解每一个城市集合的最短路径，以及用改进的蚁群算法求解GTSP问题的所有城市族的连接顺序.最后将每一个城市集合的最优路径按GTSP问题的连接顺序合并成原TSP问题的一个解.实验部分我们分别用本文算法和传统的蚁群算法求解大规模TSP问题，实验表明本文算法对城市规模较大的TSP问题有较好的效果，与传统的蚁群算法比较，本文算法的求解效率有了显著的提高.

目录

摘要

1 引言

1．1 研究背景及意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．3 本文主要研究工作

1．4 本文结构安排

2 本文相关算法的介绍

2．1 K-means算法

2．2 吸引子传播算法的描述

2．3 蚁群算法的描述

3 基于候选集的蚁群算法求解TSP问题

3．1 候选集的建立

3．2 分段优化

3．3 仿真实验

4 大规模TSP问题的层次求解法

4．1 聚类算法的选择

4．2 寻找类与类之间的连接顺序

4．3 确定边界城市

4．4 求解类内的最优路径

4．5 路径的合成

4．6 仿真实验

5 总结与展望

参考文献

致谢

作者简介

声明