基于剪枝算法解决非对称TSP问题的算法研究*

李博 颜靖艺

1 桂林航天工业学院 计算机科学与工程学院，桂林 广西 541004;2 桂林电子科技大学信息科技学院 管理系, 桂林 广西 541004

如果一个人要依次前往多个城市旅游，他就需要进行相应的路程规划。当仅仅以各个城市之间距离作为衡量标准，不考虑其他因素时，这就转换为寻找最短路径的问题——旅行商问题。旅行商问题，即TSP问题(Traveling Salesman Problem，TSP)，指的是：有个旅行商人需要独自依次前往数个城市经商环游，在整个旅程中他对于每个城市去且仅能去一次，不能多次经过同一座城市，并且在整个旅行的最后他需要回到起点，基于这些条件他需要计划出一条最短的路径。

TSP问题在我们生活中有很广泛的应用，比如路径规划等[1-3]。同时，TSP问题是NP-Complete问题，因此在求解过程中不能选用一些传统的优化算法。基于TSP问题的普遍性和趣味性，国内外科学工作者对这个数学问题进行了各种角度的研究，很多知名的算法被选用处理该问题，比如：贪心算法(Greedy algorithm)、蚁群算法(Ant colony algorithm)、模拟退火算法(Simulated annealing algorithm)、遗传算法(Genetic algorithm)等[4]。对于TSP问题，研究人员设计解决该问题的算法都希望尽可能快的求出路径规划方案，并且其路径规划长度更短，即又好又快。但是由于TSP问题的复杂性，这些算法目前都有些不足：贪心算法在计算离散的优化问题时，由于其运算规则的设计，在求解过程中会出现局部最优问题[5]；遗传算法是一种比较常见和通用的算法，在很多问题上都有很好的表现。但是遗传算法作为一种通用算法，在处理TSP问题时也有些局限性，比如当城市的数量增加时，其计算精度会下降，而运行时间会增加；蚁群算法是目前公认的解决TSP问题的最佳算法，有些科学工作人员认为蚁群算法就是为解决TSP问题而生的算法。本文认为：如果研究TSP问题都采用蚁群算法，可能会导致思维固化；部分研究人员只专注于研究蚁群算法，忽略了其他的一些思路；而改进的蚁群算法过度追求优秀的计算结果，忽视算法运行时间，使得城市数量较多的数据集在实验中运行周期较长[6-8]。同时，目前该领域的研究大部分集中在对称TSP问题(两个城市往返距离相等)上，关于非对称TSP问题(两个城市往返距离不同)研究成果较少。因此，本文没有选择当前关于TSP问题的热门研究方向，而是从一个新的角度思考，即采用本文作者提出的方法：笨人算法(Fool algorithm)，通过不断排除最不符合预期的解，直到剩下唯一解，也就是此次运算的解，然后迭代完成整个路径规划。同时，这种方法由于其自身算法的设计，即使无法完成最优解，也可以得出对于此次路径规划可能的最大复杂度的估计[9]。

1 算法设计思想

在求解TSP问题时，首先会对问题进行数学的抽象，如转换为有向图、矩阵、坐标系中的坐标点等形式。本文也将其转化为矩阵的形式，并对其进行分析：本文以矩阵的横纵坐标表示城市的编号，矩阵内的数字代表的两个城市之间的距离(从横坐标编号城市到纵坐标编号城市)。这样构造的矩阵，有如下特点：1)当前城市到当前成城市的距离为0，也就是这个矩阵的对角线上的元素均为0；2)针对TSP问题中的两个城市之间的往返距离是否相等，TSP问题可以分为对称TSP问题和非对称TSP问题，对于对称TSP问题，这样的构造就会形成对称矩阵。

目前大部分经典的TSP问题研究成果都是关于对称TSP问题，以至于研究TSP问题最权威的数据库TSPLIB中基本都是对称TSP问题的数据集。但是从实际应用中，非对称TSP问题有更为广泛的应用场景：1)目前两个城市、两个地点之间往返路线通常是不相同的；2)即使往返路线完全相同，也要考虑道路拥挤情况、车辆情况、机票火车票价格等其他因素。因此，非对称TSP问题更为切合实际应用场景，所以本文重点研究非对称TSP问题。

本文作者在《基于剪枝算法解决多处理机调度问题的算法研究》一文介绍了一种解决NP问题的方法——笨人算法，本文这里也结合非对称TSP问题进行相应的分析。

贪心算法的核心思想是：总是选择最优解。针对本问题的思路就是一直寻找符合条件的最小值。

笨人算法的核心思想是：通过运算淘汰最不匹配要求的解，直到解只剩下唯一一个，即为本次运算的解。对于非对称TSP问题，就可以转化为：每个城市必须有一条去其他城市的路径，也要有一条到达该城市的路径，并且各自只有一条，也就是最终运行的结果是每行每列有且只有一个元素。同时因为旅行者要依次到达每一个城市，就要保证所有的城市只有一个闭环，内部不会有其他小的闭环。

本文采用笨人算法计算非对称TSP问题的步骤如图1所示。

图1 笨人算法流程图

(1)在经过数据预处理得到的包含城市之间距离的矩阵中，找到最大值从矩阵中删除，并将矩阵中原位置设为空，即从横坐标序号城市无法到达纵坐标序号城市；

(2)继续进行步骤(1)的操作，TSP问题要求每个城市都要经过一次(且仅为一次)，这样每个城市按照要求都要到达和出发各一次。因此当某行或者某列只剩下一个元素时，横坐标编号城市必然要去纵坐标编号城市，然后记录这条路径，出队；

(3)满足出队条件，进行步骤(2)的操作后，删除出队元素所在这一行和这一列的其他元素，将位置设置为空，同时，为了避免内部小闭环问题，也删除步骤(2)出队元素横纵坐标交换的元素，这样就是对原矩阵进行了降阶处理，原矩阵变为了n-1阶，也就是变成了n-1个城市规划路径(但其实还是计算n个城市的路径)重复步骤(1)和(2)，直到完成本次路径规划，得到n条路径[9]。

本文作者在《基于剪枝算法解决多处理机调度问题的算法研究》一文设计笨人算法时，对于在寻找矩阵中最大值遇到相同值的情况，设置了如下两条规则：

(1)当数字相同时，比较该元素所在行及所在列未删除的元素个数(后文为方便讨论，记为：K值)，优先删除K值较大的元素，即该元素所在行及所在列未删除的元素个数较多；

(2)当规则(1)无法判别，即K值相同时，则按照指定顺序(比如先比较行坐标，再比较纵坐标，对于本问题，就是先考虑出发城市，后考虑到达城市)。

笨人算法在查找最大值所设置的规则1)，实际是让整个任务更“笨”了，也就是所做的步骤更多。根据线性代数运算的知识，如果矩阵中一块区域非零值越少，则越容易降阶并计算出结果。规则1)就可以使得笨人算法尽可能地排除更多的值，并计算出作业调度所需的最多步骤[9]。通过这样路径规划的设置，也会使得整个最终路径规划时尽量少出现闭环的情况，使得路径规划顺利完成。

补充说明：(1)本文作者在阅读相关文献时，发现目前贪心算法在TSP问题上的应用，更多是在图论的角度进行的应用：旅行商从某一点出发，选择离他距离最近的城市(未到达过的)作为下一站。这种思路很明显从一开始就陷入局部最优。本文通过将数据集采用矩阵进行分析，贪心算法依次选择最小的元素，然后删除行列降阶，这是一种改进的贪心算法的演算步骤，从而使贪心算法在该问题中的表现会好一些。

(2)TSPLIB数据库中的数据集基本是存储城市的坐标，而不是各个城市的距离，然后算法默认旅行商是从原点开始，再返回原点。但本文认为所谓的原点只是为了理解方便，该问题主要度量的因素是彼此城市之间的距离。所以本文描述并未着重考虑运算的起点，而且最终所有的城市会绕成一个圈，从哪个点开始都没有区别。本文实验主要采用矩阵分析，则需要对TSPLIB数据库中的数据集先进行数据预处理。

(3)在广义上，对称TSP问题是一种特殊的非对称TSP问题，因此对于对称TSP问题也可以按照本文介绍的演算步骤进行分析。

(4)Floyd算法是常用的求解图中任意一对顶点间最短路径的算法，容易理解，代码编写便捷。Floyd算法在分析距离时，需要整体迭代，以每个点依次作为中间点来分析，这样找到最优解，但是Floyd算法比较适用于数据集比较小的情况，在数据集较大的情况下，采用全图遍历依次分析距离的话其成本过大，而TSP问题数据集节点数都比较多，而且研究趋势是针对越来越大的数据集。故本文认为Floyd算法直接用于解决TSP问题效果和运算周期都不会很理想，但可以借鉴其思想，对整体结果集做相应的调整。

2 理论分析

本文这里进行一次路径规划，演示笨人算法在非对称TSP问题上的应用。假设当前有5座城市，要选择5条最短的路径，横坐标i表示出发城市编号，纵坐标j表示到达城市编号，aij表示第i个城市到第j个城市的这条路径，举例可得下面矩阵，如图2所示。

X72348X42543X94567X23361X

如图3所示，对角线上的数字设置为“X”(自身城市到自身城市距离为“0”，但是没有分析的意义)。首先发现数字“9”是矩阵中最大的数字，且为唯一的最大值，则删除a34。为了方便演示，本文将需要删除的元素先标记为阴影斜杠区域，在删除后将该位置设置为空，标记为“X”。根据步骤2)，判断矩阵中任意行列的元素个数均大于2，不满足出队条件，则继续进行步骤1)，删除a21。这时发现a21和a43数值相同，均为7。根据设置的遇到最大值相同而设置的两条规则，计算这两个元素K值(该元素所在行列未删除元素的总数)，两个元素的K值均为6(3+3=6)，则继续根据第二条规则。本文设置先出队横坐标(出发城市)小的元素，则删除a12。然后继续上述操作，依次删除a43，a42，a53，a41，a25，直到第4行只剩下a45。此时，第四行只剩下a45这条路径，根据之前的分析，这是条必须选择的路径，也就是唯一一条由4号城市出发的路径(a45代表是由4号城市前往5号城市的路径)，否则旅行商的行程将无法完成，因此a45出队。将满足出队条件的a45元素标记为阴影方格区域，然后将a45所在行与列删除，降阶为n-1阶矩阵。虽然矩阵进行了降阶，但是各城市之间距离不会发生变化，因此在新的4阶(n-1阶)矩阵中仍然使用原来5阶(n阶)矩阵的坐标。

图3 笨人算法举例流程

在新得到的4阶矩阵(n-1阶)继续重复该操作，先比较a23和a31，根据之前设置的规则，删除a23。然后发现a13和a24同时满足出队条件，则将这两个元素同时做出队处理，原矩阵直接降阶为2阶矩阵。在新的2阶矩阵中首先删除a31，根据线性代数知识，必须选择对角线上的元素：a32和a51。这样完成了这次的路径规划，依次出队的元素是：a45,a13,a24,a32,a51。在调整后，此次旅行商依次通过的城市是：4→5→1→3→2(因为旅行商是依次通过这些城市，起始城市并没有太多影响，只要按照这个先后顺序就可以)，路径共计是12，这样就完成了此次笨人算法对于非对称TSP问题的路径规划。

3 实验

为了对之前的介绍进行验证，本文关于非对称TSP问题进行了实验，数据集选取了在TSP问题上非常经典的TSPLIB数据集。实验选取为本文作者所设计的笨人算法以及贪心算法、蚁群算法。

3.1 数据预处理

TSPLIB数据集是关于TSP问题的非常经典的数据集，但该数据集存储的基本都是关于对称TSP问题的数据集，以及数据集中存储的是各个城市的坐标。本文主要分析的是非对称TSP问题，并且分析手段是选用矩阵的形式。非对称TSP问题的应用场景要比对称TSP问题更为广泛，单独从路程距离的角度来分析，两个地方的来回路径，可选择道路不一定永远是相同的，以及考虑其他因素，比如飞机票的价格等，这样非对称TSP问题更有研究的价值和空间。为了更好地进行实验分析，本文首先对数据进行了预处理：选取TSPLIB数据集中的数据集，根据其中每个点(城市)的坐标，计算出各个点之间的距离，列为矩阵的形式。距离的计算选用欧氏距离计算，小数点保留一位。通过初步变换所得到的矩阵是对称矩阵，然后对于对角线位置的两个相同的数字进行随机处理，其数值会有±5%的波动，并向下取整，这样就将对称矩阵变换成了非对称矩阵。在随机变换中，设原来数值为X，新数值为X*，则可得公式(1)：

X*=X±(0.05X)

(1)

3.2 运算

本文选择最大最小蚁群算法(Max-min ant colony algorithm,MMAS)、贪心算法作为对照组算法，蚁群算法及其改进算法是一种非常经典的算法，其中最大最小蚁群算法是目前公认的处理TSP问题表现最好的算法。贪心算法是一种非常常见的算法，其方便理解易于处理，并且笨人算法就是与贪心算法进行对比而分析产生的。本文选用了eclipse3.0作为实验工具软件，eclipse是一款非常常用的软件，方便有效，搭建基于JDK的Java运行环境。实验主要采用TSPLIB中的Att48、GR21、Linhip38这三个数据集为对比，笨人算法和贪心算法各进行一次，而蚁群算法需要迭代次数比较多，可以分为迭代1次和迭代100次的情况进行分析。

3.3 实验结果分析

对于实验结果，本文对实验结果精度、迭代次数和方差几个方面进行分析。

3.3.1 精度

根据实验的结果，本文列出表1进行分析。最大最小蚁群算法是需要较多迭代次数才可以得到比较优解的算法，如果仅从一次遍历的结果而言，贪心算法、笨人算法要略优于迭代1次的最大最小蚁群算法(MMAS)，这是因为蚁群算法的前几次搜索类似于随机搜索的过程。而随着迭代次数的增加，最大最小蚁群算法的优势逐渐显现出来，符合其目前作为TSP问题最优解算法的特性。但是笨人算法的表现至少说明其作为一种分析最差情况的算法，有一定的价值。

表1 三种算法在数据集上的整体表现

3.3.2 运算次数

对于这类问题，因为没有反馈机制，笨人算法和贪心算法基本会在运算一次后就完成了此次路径规划，即得到了对于该问题的最终解，即使反复迭代，运算结果也不会有明显的变化；而蚁群算法因为轮盘赌、正反馈等因素，往往需要较多的运算迭代次数，无论是哪种改进版本的蚁群算法，基本是不可能一次遍历就能完成整个求解过程，自然求解的成本和周期就会增加。所以即使是目前设备比较先进发达的情况下，求解一些维度较高(比如城市数目在2 000，甚至5 000以上)的TSP问题，都会耗费较长的时间(比如动辄3小时以上)。通过分析可得，蚁群算法及其改进算法其运算次数和迭代次数会明显高于贪心算法和笨人算法，甚至是高出几个数量级。所以，本文这里就对贪心算法和笨人算法在一次路程规划中的运算次数进行分析。

本文通过分析可得：随着数据规模的增加，笨人算法为了有较好的城市路径规划调度结果和方差，算法的计算次数会有所增加，其时间复杂度约为o(n2)。而贪心算法的一次遍历的计算次数是与城市的数量成正比，时间复杂度为：ο(n)，笨人算法会比贪心算法时间复杂度高一个数量级。计算机在n阶矩阵查找一次最大值或最小值的时间复杂度为o(n2)，因此整个实验中贪心算法时间复杂度是o(n3)，笨人算法的时间复杂度为o(n4)。但这是一次作业遍历中进行总的运算量，相比于蚁群算法的迭代次数和每次遍历中的运算次数(以及多次迭代遍历的总共运算次数)，笨人算法的运算量还是非常小的，不需要非常长的运算时间，时间复杂度也较低。

3.3.3 方差

本文在阅读大部分的TSP类问题分析的相关文献的过程中，发现方差是个不太被考虑的因素，因为求解目标是整体路程的最小值，也就是路径规划各个分段路径的和的最小值。在实际旅途分析中，方差可以用来描述各个分段路径的变化程度。如果考虑到交通工具的磨损、人的旅程时间的舒适度，更为均衡的路程分配，会让机器的磨损更为均衡，会让人的旅行不至于过度疲惫，在TSP问题分析中，方差也是一个非常重要的指标。

方差是用来估计实验数据内部之间的差异性，可以用来分析算法计算得到结果数值的差异性，通常方差的衡量采用欧氏距离，则计算方式如公式(2)：

(2)

因为这几组实验的路程中的距离差别较大，本文为了更好地进行分析，对方差进行了归一化处理。归一化处理是一种常用的数据分析、数据预处理的手段，本文通过分析实验数据的数值区间，依次截取得到整个数值区间的最大值(Xmax)和最小值(Xmin)，将数据转换到[0 1]的范围，归一化公式如下：

(3)

通过公式(3)可以将原始数据从原本Xmax、Xmin的区间，压缩到[0 1]的区间。这种方法消除了数值波动所造成的影响，在分析方差时可以对不同样本集的结果进行统一的分析。

通过图4分析可得，笨人算法的方差是最小的，最稳定的。因此笨人算法在处理非对称TSP问题的过程中，有其一定的优势，值得继续深入分析和研究。

图4 三种算法实验结果方差分析

4 结论

TSP问题是一个非常有研究价值的问题，其中非对称TSP问题的应用场景更为广泛。本文通过文献阅读和思考，在目前的主流研究方法之外，采用本文作者提出的笨人算法进行分析，该算法的核心思想是：通过运算淘汰最不匹配要求的解，直到剩下唯一解，则作为本次运算的解。通过实验分析，笨人算法在单次路径规划中有较好的表现(但最大最小蚁群算法经过多次迭代后在精度方面更优，并随着迭代次数的增加会逐渐趋向于最优解)，并且整体的路径长度的解集的方差更小。本文采用笨人算法分析非对称TSP问题具有以下作用和意义：

(1)笨人算法由于其自身的特性，提供了可以估计的算法时间复杂度的上界，即得到理想结果的最大代价。目前蚁群算法在研究TSP问题时，为了精度的提升往往忽略了时间和运算成本，但在实际应用中缺乏意义。笨人算法可在工业实际应用中提供一个求解成本的上限，避免额外开销；

(2)目前TSP问题的研究过度重视蚁群算法，蚁群算法在TSP问题上确实有优秀的表现，但过度的学术资源集中于一个算法会导致学术资源的浪费和僵化。本文避开当前的主流算法，从一个新的角度剖析TSP问题，这可能会为TSP问题的研究提供新的思路。

(3)笨人算法可以称之为“反贪心算法”，通过实验分析：每次局部最优并不一定保证总体最优，而笨人算法虽然运算时间较贪心算法较多，但相比于蚁群算法还是较少的，并且结果集的方差更小，表明挑选出的路径长度较为平均，在实际路径中的油耗、零件的磨损更为可预测，具有更高的实用性。

本文还存在一些不足：

(1)笨人算法在n个城市的路径规划过程中，采用矩阵的形式进行分析时，会由于一次剪枝导致多个元素出队，从而造成漏解的情况，即无法得到满足条件的解。本文目前的解决办法是在单条路径选择完后进行检测，检测是否有区域内闭环，并且删掉与出队元素对称的元素(不能出现由A城市出发到B城市，又由B城市出发到A城市)；如果出现区域内闭环(即无法满足TSP问题要求的条件)，会再次进行分析运算。这个解决方案明显不是最优解决方案，今后会探究更优的解决方案以及如何避免该问题的发生。

(2)本文还将分析借鉴Floyd算法思想，Floyd算法是引入了中间点，多次迭代计算各个点之间的路径，用中间点寻找更短的路径。因此本文借鉴这一思想，对计算得到的结果集可以优化。但是TSP问题数据集是个比较大的数据集，直接采用Floyd算法思想全局优化则成本较高，可以对最终得到的路径，依次选择4个点(至少4个点)，如：A→B→C→D，根据相互间路径长度，调整为：A→C→B→D(这一小段的路径的起点和终点是不能改变的)，然后依次完成整个路径的优化，本文计划后续进行相应的研究。