TSP问题（traveling salesman problem，旅行商问题）属于经典的计算机理论科学问题，在交通调度、机器人控制、矿物结晶学、超大规模集成电路等各个方面具有广泛的应用。该问题描述如下:要求商人从一个城市出发，不重复地访问所有城市，并回到出发点，问什么样的环路最短？由于TSP问题易于描述，同时又属于经典的NP-hard组合优化问题，因此它作为算法实验平台而被广泛研究。目前人们对TSP问题的研究主要集中在启发式算法设计方面。TSP问题的启发式算法分为环路构造算法和环路改进算法两大类:前者包括最近邻、贪心算法、Clarke-Wright、Christofides等;后者包括局部搜索（2-opt、3-opt及其变体）、禁忌搜索、模拟退火、遗传算法等。　　本文首先对TSP问题的研究进展进行了总结，在此基础上，分别从理论和实验的角度，深入地研究了TSP问题状态空间与算法设计的关系。本文的主要工作与创新在于提出了状态空间切换的方法及其在TSP问题上的应用，可归纳为“一种方法”，“一个模型”和“四种应用”:　　“一种方法”——状态空间切换(status space switch):对于TSP这类组合优化问题，最简单通用的启发式算法是局部搜索，它将可行解视为高维状态空间上的点，在点的邻域搜索更好的解。局部搜索的优点是搜索效率高，解的质量好:其缺点是可能过早落入局部最优解陷阱（trap）而不能得到全局最优解。通过研究局部搜索与状态空间的关系，本文在归纳总结了一般宏启发算法跳出局部最优解陷阱的方法的基础上，提出了一种新的跳出局部最优解陷阱的方法—状态空间切换。该方法的基本原理是:不同状态空间的拓扑性质存在差别，当局部搜索在一个状态空间落入局部最优解陷阱时，在其他状态空间中，当前解可能并非局部最优解，此时若算法转到新状态空间中进行局部搜索，则可以得到新的更好解。这样通过不同状态空间的交替使用，可以有效地避免落入局部最优解陷阱，进而提高局部搜索的性能。本文指出了状态空间的实例、启发集和局部搜索算子三个要素。通过改变状态空间的各种要素，可以得到不同的状态空间切换算法。　　状态空间切换为组合优化问题的算法设计提供了一种新思路，现有的启发式算法均可与之相结合以获得新的更好算法。对于一个启发式算法，可以通过改变实例或启发集要素来获得它的状态空间切换算法;对于多个启发式算法，可以将它们视为局部搜索算子，通过对这些局部搜索算子的各种排列组合，可以得到多种状态空间切换算法。　　“一个模型”——解的概率统计模型(statistic model of solution):为了将状态空间切换方法应用于TSP问题，需要对TSP问题的状态空间进行建模。由于状态空间一般都过于复杂，所以难以对局部搜索算法和问题本身进行分析，目前常用的较好的方法是适应度地貌分析。这种方法的一个缺点是将解作为基本单元，不考虑解的内部结构，从而不能分析解的内部更精细的性质。本文突破传统适应度地貌分析的局限，将解看成一些更基本单元的集合，并以此为基础分析了局部最优解与全局最优解之间的关系，提出了解的概率统计模型，揭示了TSP问题状态空间的内部更加精细特性。TSP问题解的概率统计模型指出全局最优解的边在局部最优解中出现的概率符合[0，1]上的β-分布，而对于非全局最优解的边，我们对其进行了划分:在局部最优解中频繁出现的边，记其集合为U1;很少在局部最优解中出现的边，记其集合为U2。U1中的边在局部最优解中出现的概率期望值满足[0，1]上的β-分布。U2的边在局部最优解中出现的概率期望值的具体分布对结果的影响较小。　　TSP问题解的概率统计模型为精细地刻划状态空间的性质提供了一种新的思路，利用它可以更加量化地描述状态空间，为研究TSP问题的算法设计提供了一种非常有效的手段。　　“四种应用”——多重规约算法、自适应可变启发集搜索、并集搜索和并集稀疏图搜索:我们利用前面的概率统计模型来分析TSP问题的状态空间，发现了局部最优解交集中的绝大部分边属于全局最优解以及局部最优解并集包含了绝大部分全局最优解边。利用这种特征，我们设计了以下状态空间切换算法:①在算法运行中，将局部最优解的交集固定，由此得到规模更小的新TSP问题，在求解这个新的规模更小的TSP问题后，我们将它的解与原局部最优解的交集拼接起来，这样就得到了原TSP问题的解，这就是改变实例要素的状态空间切换算法——多重规约算法;②在算法运行中，利用局部最优解的交集对启发集进行收缩，由此得到改变启发集要素的状态空间切换算法—自适应可变启发集搜索算法。③利用局部最优解的并集作为启发集，由此得到改变启发集要素的状态空间切换算法——并集搜索;④利用局部最优解的并集将原TSP问题转换成一个稀疏图上的TSP问题，由此得到改变实例要素的状态空间切换算法——并集稀疏图搜索。　　四种状态空间切换算法佐证了状态空间切换方法的有效性。同时，这些算法的思想可以应用到其他组合优化问题上。比如:可利用多重归约算法的思想求解图的划分和二次分配问题以及利用并集搜索来求解任务调度和中国邮递员问题等。