基于最小调整法求解旅行商问题

费威

摘 要 介绍了一种求解旅行商问题的新算法“最小调整法”，给出了该算法求解旅行商问题的具体步骤以及有效性证明，对算法的复杂性及近似程度进行了分析.最后通过典型算例进行了检验说明.与经典算法相比，新算法体现了简单易行的特点，对求解旅行商问题具有一定的启发意义.

关键词 旅行商问题；最小调整法；算法有效性

中图分类号 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