Reseach on Algorithms for Traveling Salesman Problem

本文在对TSP求解方法进行深入分析的基础上，提出了几种改进算法和新算法，并定义了两种现实TSP模型。首先，对TSP的典型算法，主要包括松弛问题的求解、启发式算法和精确算法，进行了分析、比较和评价，指出各方法存在的问题及研究倾向。其次，对求解TSP的近似算法进行了研究，包括启发式算法评价标准的探讨、两种改进的启发式算法的提出以及对TSP线性松弛问题求解方法的比较。评价启发式算法性能的标准主要是计算复杂性和计算精度。指引最近邻算法和选择“龙骨”的指数级邻域搜索算法是本文提出了的两种改进的启发式算法。数值实验表现出这两种改进算法的有效性及优点。将两种内点算法：原-对偶内点算法和等高面法，用于求解TSP的线性松弛问题。数值实验显示出这两种内点算法的计算性能都好于单纯形法。同时，等高面法的计算复杂性略低于原-对偶内点算法。再次，提出了一种新的整数规划算法－等量面法，并用其对TSP进行了精确求解。理论上证明了该算法是一种良性隐式枚举，数值实验表明该算法具有很好的性能。应用等量面法迭代求解了TSP的最优解。最后，本文给出了图形旅行商问题的数学模型，同时定义了两种新的现实旅行商问题－实用旅行商问题和动态旅行商问题