旅行商问题(TSP)是来源于实际应用的一个非常重要的组合优化问题。该问题的研究对于实际运用和科学研究都有着重大的意义。本文主要通过研究局部搜索算法和演化计算方法来更高效地解决旅行商问题。在本文中,我们着重研究了Lin-Kernighan局部搜索算法和杂交算法。我们对文中主要的算法都进行了大规模的实验。与其他许多研究通常只关注实验的最终结果不同,本文中对于算法性能的实验分析都是基于算法的运行时行为和多种时间度量。这使得我们的实验分析更均衡,更详尽,更公平以及史合理。本文中的工作主要来自以下五个方面：第一,我们研究了局部搜索算法中优秀的Lin-Kernighan算法,并且在原始的Lin-Kernighan算法上进行了一些改进,比如为原始Lin-Kemighan算法设计了一个新的高效的数据结构,对候选集的大小进行试验探索,同时还对原始Lin-Kemighan算法的一些搜索策略进行了调整,给出了一个比原始Lin-Kemighan算法更好的改进的Lin-Kernighan算法,提高了该算法的性能。第二,对Lin-Kernighan算法进行了规模较大的实验,不同于其他研究只关注最终结果,我们通过基于运行时行为的算法性能分析,将Lin-Kernighan算法和其他一些局部搜索算法进行比较,给出了关于Lin-Kernighan算法性能更加平衡全面详尽的分析报告。第三,基于不同局部搜索算法的比较,我们发现了不同局部搜索算法存在不同的优点和缺点,基于这些优缺点,我们对不同的局部搜索算法进行了组合,得到的组合局部搜索算法(LS-LS杂交算法)比单一的局部搜索算法性能更加优秀。第四,我们将纯的局部搜索算法和组合局部搜索算法与演化算法和基于种群的蚁群优化相杂交,通过一些参数调整,得到了性能优秀的杂交算法。即使在求解规模较大的旅行商问题时,我们的新杂交算法也能快速地找到很好的解。实验结果表明我们的新杂交算法相当具有竞争性。最后,我们扩展了杂交算法的思想,为进化算法设计了针对旅行商问题并且基于Lin-Kernighan算法的交叉算子。实验结果表明我们设计的交叉算子的性能比作为旅行商问题研究领域中最好的交叉算子之一的Edge cossover交叉算子更好。这说明我们关于基于局部搜索算法设计交叉算子的想法非常具有前景。