摘 要 介绍了一种求解旅行商问题的新算法“最小调整法”，给出了该算法求解旅行商问题的具体步骤以及有效性证明，对算法的复杂性及近似程度进行了分析.最后通过典型算例进行了检验说明.与经典算法相比，新算法体现了简单易行的特点，对求解旅行商问题具有一定的启发意义.
关键词 旅行商问题；最小调整法；算法有效性
中图分类号 O221.4 文献标识码 A
1 引 言
旅行商问题（Traveling Salesman Problem，简称TSP）是著名的组合优化问题[1].经典的TSP问题可描述为：设有n个城市1，…，n，由i城市到j城市的路程dij已知，一个旅行商为了推销货物，从某一城市出发，如何选择一条最优路线可以经过所有其他城市，且每个城市正好经过一次，然后回到出发点.容易看出，旅行商有（n-1）！种方案可供选择.即使n是较小的两位数，这类问题仍没有较好的有效算法，因此被称为NPcomplete问题.但是TSP问题在组合优化问题中具有广泛实际背景和深刻经济含义.例如，在计算机的集成电路设计中就出现了这一问题，还包括派车、排序、底板布线、考古学中的排号、自动钻井、工件加工顺序和邮局收发信件等其他许多方面，所有这些需要促使学者们不断地研究TSP问题的算法[2].目前国内外求解TSP问题的较好算法有遗传算法、神经网络算法、模拟退火算法、蚁群算法和粒子群算法等[3-7]，这些算法中遗传算法具有较好的全局搜索能力，但优化过程缓慢，结果准确度不高；粒子群算法局部搜索能力较弱；蚁群算法等存在计算速度较慢等缺点.因此，以这些算法为基础，较多学者相继提出了改进的算法以更好地求解TSP问题[8-13].
2 最小调整法求解TSP问题的思想和步骤
最小调整法[14]是以Dijkstra算法[15]为实现途径的一种多项式算法.本文根据最小调整法，给出了求解TSP问题的一种新的有效启发式算法.该算法较
之以往常用的启发式算法更加简单易行，计算量仅为O（n2），并且由此得到的近似解一般更接近最优解.
下面首先根据指派问题和TSP问题的异同点比较，然后提出将TSP问题先看做指派问题利用最小调整法求解[16]的具体步骤.
2.1 TSP问题与指派问题的异同
对比指派问题和TSP问题，它们有如下异同点：
第一，指派问题中，第i项任务可以由第i人去完成，因此其解可以在效率矩阵（成本）矩阵的主对角线上；但TSP问题中不存在从Ai城市到Ai城市的情况，其解显然不会出现在距离矩阵的主对角线上，即有i≠j的约束条件.
第二，对于有n个人的指派问题，其解由n项任务所组成，这些任务在效率矩阵中既不同行又不同列；对于有n个城市的TSP问题，其解由n段行程构成，这些行程在距离矩阵中既不同行又不同列.
第三，xij=1或0表示指派问题的解，则效率矩阵任一行、任一列的效率参数之和均为1，即∑ni=1xij=1且∑nj=1xij=1（i，j=1，…，n），即每个任务只有一个人承担，每个人只能承担一项任务.TSP问题中∑ni=1xij=1且∑nj=1xij=1（i，j=1，…，n），即在回路上仅由1个城市出发至第j个城市；从第i个城市出发仅通往1个城市，即所有中间城市仅通过一次.
第四，指派问题不存在回路问题，但TSP问题解的各段行程首尾相接，必然构成一个回路.
通过比较指派问题和TSP问题的特点，上述第一和第四点说明指派问题与TSP问题有区别，第二和第三点则是相同的.如果置TSP问题原始距离矩阵主对角线元素为一个相当大的正数M或记为“×”时，把TSP问题当作指派问题去求解，这种指派问题就具备了TSP问题的第一和第四点中某些特点了，然后再对该解检验其作为TSP问题的可行性.
2.2 最小调整法求解TSP问题的思想步骤
若把带权完全图G当前结点当成任务的承担者，另外结点当成任务，边的权（城市间距离）为完成任务所用时间，则寻求最优Hamilton回路[14，15]是把图中结点怎样与别的结点进行单一指派，使每个结点既是一个结点的任务承担者，又是另一个结点的任务，这种指派使完成任务时间最短以及满足这些指派所确定的路径（旅行商走过的路径即指派路径）构成一个回路的条件.指派路径构成一个回路是在一般指派问题中增加的条件.
设TSP问题的关系矩阵为C
其中元素cij表示由第i城市到第j城市的距离.
步骤1 取每列的一个最小值画圈，即得到一个最小方案.若这些画圈元素又分属于不同行，则得到相应指派问题的最优解，转步骤3；否则转步骤2.
步骤2 应把有两个或两个以上画圈元素行中的一个改画到同列别处，待到某一无圈行中有一元素画上圈，则算一次调整.如此进行，直到每行均有一个画圈元素时为止，然后转入步骤3即可.而每次调整均以目标函数（其值为各画圈元素之和）增值最小为原则.
步骤3 如果从步骤1或2得到的指派问题最优解元素的任一行指标i出发，先到其列指标j为下一行指标的元素出发，再到其列指标.如此进行下去，最后回到以i为列指标的元素，便形成一个圈.若圈中的元素恰为n个，则所得方案即为最优方案；否则便会形成两个或两个以上的子圈，它不是最优解，需进行再调整，转步骤4.
步骤4 以增值最小的原则实行对调调整.所谓对调调整，就是在任意两个子圈中各取一个元素，如cij与cst，交换它们的列标号，变成cit与csj，其结果是这两个子圈便合成一个圈，该变化如图1所示
由图1可知，这4个元素形成一个矩形，调整是把矩形原先对角线上的两个画圈元素cij与cst的圈转给了另一对角线上的两个画圈元素cit与csj.显然经过调整，目标函数将增加为Δf=（cit+csj）-（cij+cst）.考虑所有可能的对调调整，取其中增值最小的，加以调整，便破掉一圈.如此进行，直到无子圈为止.
破圈所说的“圈”指的是欧拉圈，它可以分为广义的和狭义的两种：在n个城市的TSP问题中，广义的圈可以由n个城市任选两个以上的城市任意排列构成；而狭义的圈则被严格规定为指派问题最优解即xij=1所在位置，也就是最优解中的画圈元素所构成的回路.狭义的圈在讨论TSP问题时被简称为“圈”.因此，此处可以将“圈”定义为用指派问题最优解所确定的，从一个城市到另一些城市，然后再返回到那个城市的一个闭合回路.对于大规模问题，求最短调整路线可用标号算法，
2.3 最小调整法求解TSP问题算例
先求出相应指派问题的最优解，具体过程为：
以此例的指派问题最优解为c13，c32，c21，c45，c54，转步骤3.检验结果此方案形成两个子圈：（c13，c32，c21）和（c45，c54）如图2（a）和（b）.
容易看出在两个子圈中任意各取一个元素，交换它们的列下标，则这两个圈便合成一个圈.例如将图2（a）的c13与（b）的c45的列下标对调或交换便成为：c15，c54，c43，c32，c21.于是便破掉一个圈，此例经处理便得到一个可行方案.上述处理相当于若把分属于不同圈中的两元素看成为矩形一对角线的二顶点，则其圈调换给了该矩形另外一条对角线的两个顶点对应的元素，即：
调整的结果将导致目标函数值的增加.若每次对调都选择增值最小的进行，当所有的子圈全被破掉后，即得原问题的一个更好的解.
此例中的最优解为：
因此，旅行商问题的最短路线为：1→4→5→3→2→1，最短路线长为f=20.
此例还有其他多种破圈方案在此不再累述.在最小调整最优方案的基础上实施对调调整可在图中直接完成，以上例两个圈进行说明：即以一个圈中的画圈元素与另一个圈的每个画圈元素连线，以该线为对角线的矩形的另两个顶点元素即交叉对角线的两个顶点元素，计算这两个元素之和与原画圈两个顶点元素之和的差，若为0则该对调调整就是最优调整；若不为0，继续将该圈中其他画圈元素仿此处理，最后取差值最小的进行对调调整.若最小调整法的最优方案形成两个以上的圈，也可按照上述两两圈分别进行对调调整差值计算比较，并进行对调调整，直至最终形成一个圈为止.
此问题的最优解并不唯一，另一最优解求解过程为：
此即另一最优解且无需对调调整：1→2→3→5→4→1.该最优解仅通过最小调整法就可解得.
3 最小调整法求解TSP问题的有效性分析
3.1 关于最小对调的分析
给定TSP问题的矩阵C，考虑以指派问题作为它的松弛问题.记指派问题的解为：itjt=1，t=1，…，n，其余ij=0（也可记：ci1j1，ci2j2，…，cinjn），相应最优值为
按下述行列衔接规则排列（1）中的元素：任取一元素citjt排在首位，若其行标为it列标为jt，则将以jt为行标的元素排在其后，使得每一元素的列标都是紧接其后元素的行标，直到以it为列标的元素排上为止.易见，如果上述排列所经历的元素恰为n个，则指派问题的解即为TSP的最优解，TSP的最优值也是式（1），而上述排列过程正好给出最优路线.若排列所经元素个数k ci1i2，ci2i3，…，citit+1，…，ciki1
容易验证，当k cj1j2，cj2j3，…，cjljl+1，…，cisi1， 设指派问题解中有h≥2个子圈，因此可以通过某种方法替换其中的元素，使子圈渐减直到无.经研究发现一种简单的破圈方法，具体如下定理. 定理1 交换分处于二子圈中任意二元素的行标（或列标）后简称为对调，这二子圈便合成一个高阶子圈，从而破掉一圈. 证明 设有二子圈（2）和（3），各任取一元素citjt+1及ciljl+1，交换它们的行标后式（2）和（3）分别变成： 按行列衔接规则重新排列，便有 这样它们便合成一个阶数为k+s的高阶子圈. 证毕. 推论1 若子圈（2）的阶数k≥4，则交换其中任意两个不相邻元素的行标（或列标），则它便一分为二个低阶子圈（注意ci1i2与ciki1也是相邻的）. 这样，对指派问题的解经（h-1）次对调便可得到TSP问题的一个可行解.可得定理1中所述的对调式（4）简记为 对调式（5）在破圈的同时，也引起目标函数值式（1）的增加，其增值为 为使由对调得到的可行解尽可能的好，自然希望增值（6）越小越好.于是每次破圈都选择使对调的增值（6）最小的进行当在首先考虑之中.这就是最小对调，由之得到的可行解称为最小对调解. 3.2 算法复杂性及近似程度分析 最小对调需要考虑所有可能的对调，因此应估算出对调总数.设式（2）的h个子圈所含元素的个数分别为x1，…，xh，则因子圈中任一元素均可与其余子圈中的任一元素实行对调，所以可知对调总数应为 说明对调总数不超过n22，且此上界与子圈个数h无关. 由于计算对调的增值（6）需3次加法运算，所以第一步最小对调的计算量不超过3n22次加法运算.虽说以后还要实行（h-2）步最小对调，但需要再计算的数量却比第一步的少得多.这是因为破掉一子圈后的变化仅在于由原二子圈合成的新子圈中换入了2个新元素，且新子圈所含元素至少为4.因此只需考虑这2个新元素所形成的对调，这时其余子圈的元素总数不超过（n-4），这样第二步需要计算的新对调不超过2（n-4），依此类推可知以后各步需要考虑的对调数之上
综上分析，对指派问题的解相继实行最小对调，直到得到最小对调解，所需考虑的对调总数按最坏情形计算则不超过n2，实行的加法运算次数不超过3n2，因此是十分有效的一种启发式算法.
再从与TSP问题最优解近似程度分析有如下定理2.
定理2 对于TSP的任意一个已知的可行解X，均可通过对指派问题的解实行若干次对调得到.
证明 取行标i=1，设对应列标j1，有x1j1=1.若1j1=1，则转而考查i=2.若1j1=0，则应有列标j2，使1j2=1，同时也有行标i1，使i1j1=1.若i1≠j2，则可实行对调（ci1j1，c1j2）→（c1j1，ci1j2），若对调后的方案仍记为，则已有1j1=x1j1=1.若i1=j2，则对调不能实行，由定理1说明c1j2与ci1j1属同一子圈，这时可于其他子圈中任取一元素ci2j3，先实行对调（ci1j1，ci2j3）→（ci2j1，ci1j3），然后再实行对调（ci2j1，c1j2）→（c1j1，ci2j2），结果仍有1j1=x1j1=1.再取i=2，重复以上过程，则知不超过2n次对调，便可由调整到可行解X.
证毕.
因此，由定理2，TSP问题的最优解也可通过若干次对调得到，它是使各步对调的增值（6）之累积总和最小者.最小对调虽说不能保证（6）之累积总和一定最小，但通常总是较小的，是最优解一个十分理想的上界.事实上，若设最优解为X*，指派问题的解仍为X-，最小对调解为X～，则有
f（）-f（X*）≤f（）-f（）
（10）
上式表明由最小对调解到最优解的改进不超过f（）-f（）.
3.3 算例分析
下面通过两个算例作进一步的对比分析.
例2 设旅行商问题的关系矩阵如下，求其最优解.
求解过程如下：
首先求相应指派问题最优解有
得到相应指派问题最优解：c14，c42，c21，c35，c56，c63.对调数为3×3=9，其中最小对调调整为（c42，c63）→（c62，c43），Δf=9.经过最小对调调整为于是得到：c14，c43，c35，c56，c62，c21；f（）=63，此即最优解.
若采用一般有效的启发式算法，因矩阵C是非对称的，所以无法求2—最优解，只能考虑3—最优解，取一初始路线，如X0：c12，c23，c34，c45，c56，c61，则f（X0）=124.其3—相邻路线共有6（6+1）（6-4）6=14条，其中最短的为X1：c14，c45，c56，c62，c23，c31，f（X1）=80；再求X1的3—相邻路线（除X0外计13条），其中最短的为X2：c14，c43，c35，c56，c62，c21，f（X2）=63；继续求X2的3—相邻路线（计13条），结果发现X2即3—最优解.它即是TSP问题的最优解.此类算法是否成功以及计算量的大小均依赖于初始路线X0，若选得好，既能得到满意解又减少迭代次数；若选得不好，则可能得不到最优解，迭代次数也会很多.例如，若选X0：c14，c45，c56，c63，c32，c21，f（X0）=64，则其3—最优解即TSP最优解；若选X0：c14，c42，c23，c36，c65，c51，f（X0）=65，则因其3—最优解即本身，所以得不到最优解.而所有这些差异事先无法预料，所以不得不随机地取许多初始路线，导致计算量大增，而且即使碰上最好的情形，其计算量也比最小对调大得多.由于指派问题的解的固有性质（f（）≤f（X*）），常使中的不少元素保留在TSP问题的最优解中，所以由→X*的对调调整一般都不太复杂，如果不是有意构造，其最小对调解大多与最优解很接近.因此下面通过一个最小对调解不是最优解的算例进一步进行分析说明.
例3 旅行商问题的关系矩阵如下所示
其对应的指派问题的解，经最小调整法求解得
实行第二步最小对调容易求得最小对调解为：累积增值Δf=12.而不是最优解，最优解为X*：c12，c24，c43，c36，c65，c51，Δf*=6.
如果由于的原因使f（）-f（）大到难以接受的程度（如将矩阵C中除1以外的元素均扩大10倍乃至更多），则应该考虑改进最小对调解.改进的途径有很多，其中容易想到和较为有效的是用二步、三步以至P步对调的增值和最小来代替一步增值最小，并分别记为2—最小对调，3—最小对调等等.如果不特别指出，通常所说最小对调的计算复杂度为O（n3），3—最小对调的计算复杂度是O（n4）等等.实算表明3—最小对调具有计算量不很大且效果好的优点.
若指派问题解的子圈个数h为偶数，则实行P—最小对调时，P取奇数为宜，所以据定理1及其推论，若取P为偶数，则永远不会得到可行解.同样，当h为奇数时，则P取偶数.因此考虑到破圈因素，各种对调混合使用效果可能更好，如果第一步用2—最小对调，然后3—最小对调，最后几步只用1—最小对调等等.甚至只需在累积用1—最小对调的同时，附带着多考虑几个对调，如次最小、三最小对调等等，然后加以比较，取其中最小者，就可能使得到的可行解有明显的改进，而每步的计算量仅有O（n）的增加.如对例3，若采用2—最小对调，便可得到最优解：第一步：（c21，c56）→（c51，c26），Δf1=14；第二步：（c26，c34）→（c36，c24），Δf2=-8.两步对调的增值累积和Δf=Δf1+Δf2=6.其实这里的第一步对调就是次增值最小者，实行1—最小对调时，若将它也附带考虑进去，便可更快得到最优解.因为TSP问题的最优解，虽然不能说一定是由每步增值最小的对调得到，但多半总是由每步增值较小之中的一个得到，所以对那些增值太大的对调一般可以不必考虑.最后根据定理2，对调也不应仅限于子圈之间，例如若h=2，且由P—最小对调得到最优解，则不能认为一定有P=1，因为P可能是其他奇数.这样一来，所考虑的对调数要增加，但数量仍不变，与前边分析的结果相同.任何一步对调都将引起子圈个数的变化，因此进一步研究P—最小对调对子圈变化的影响规律以及其他的破圈途径，以便更迅速有效地求得TSP问题的最优解，则是十分重要和有意义的.
4 结 论
本文基于最小调整法提出了求解TSP问题的一种新算法，给出了具体求解的步骤，并对算法的有效性进行了详细论证.通过对具体算例的求解及检验，说明最小调整法比常用的求解TSP问题近似解的算法更加简单易行.同时指出最小调整法求解该问题有时只能求出其近似解的不足和局限，对需要进一步改进和研究的工作进行了说明.
参考文献
[1] 牛燕影，王增富，王雷震.旅行商问题的一个新算法：堵子回路法＼[J＼].统计与决策，2008，24（13）：145-147.
[2] 吴振奎，王全文，刘振航.中国邮路问题的一个解法[J].运筹与管理，2004，13（3）：44-47.
[3] S LIN， B W KERNINGHAN. An effective heuristic algorithm for the traveling salesman problem[J]. Operation Research， 1971， 21（2）： 498-516.
[4] M DORIGO， L GAMBARDELLA. Ant colony system： a cooperative learning approach to the traveling salesman problem[J]. IEEE Transanctions on Evolutionary Computation， 1997，1（1）：53-66.
[5] G A JAYALAKSHMI， S SATHIAMOORTHY， R RAJARAM. A hybrid genetic algorithm： A new approach to solve traveling salesman problem[J]. International Journal of Computation Engineering Scinece， 2001，2（2） ： 339-355.
[6] Z WANG， X GENG， Z SHAO. An effective simulated annealing algorithm for solving the traveling salesman problem [J]. Journal of Computational and Theoretical Nanoscience， 2009， 6（7）： 1680-1686.
[7] Y MARINAKIS， M MARINAKI. A hybrid multiswarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J]. Computers and Operations Research， 2010， 37（3）： 432-442.
[8] 赵建明，姚念民.Hopfield网络求解旅行商问题有效性的研究[J].科学技术与工程，2009，9（2）：437-440.
[9] 吴新杰，黄国兴.利用粒子滤波求解旅行商问题[J].计算机应用，2012，32（8）：2219-2222.
[10] 柳寅，马良.模糊蚁群算法及其在TSP中的应用[J].数学的实践与认识，2011，41（6）：150-154.
[11] F LIU， G Z ZENG. Study of genetic algorithm with reinforcement learning to solve the TSP [J]. Expert System with Applications， 2009， 36（3）： 6995-7001.
[12] H WANG. Comparison of several intelligent algorithms for solving TSP problem in industrial engineering [J]. Systems Engineering Procedia， 2012， 4： 226-235.
[13] 李煜，马良.用量子蚁群算法求解大规模旅行商问题[J].上海理工大学学报，2012，34（3）：355-358.
[14] 夏少刚.运筹学—经济优化方法与模型[M].北京：清华大学出版社，2005.
[15] J J MODER， S E ELMAGHRABY. 运筹学手册： 基础和基本原理[M].上海：科学技术出版社，1987.
[16] 夏少刚，费威.基于最小调整法求解最短时限指派问题[J]. 数学的实践与认识，2009，39（17）：179-187.
