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

《基于最小调整法求解旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于最小调整法求解旅行商问题摘要介绍了一种求解旅行商问题的新算法“最小调整法”，给出了该算法求解旅行商问题的具体步骤以及有效性证明，对算法的复杂性及近似程度进行了分析•最后通过典型算例进行了检验说明.与经典算法相比，新算法体现了简单易行的特点，对求解旅行商问题具有一定的启发意义.关键词旅行商问题；最小调整法；算法有效性中图分类号0221.4文献标识码A1引言旅行商问题(TravelingSalesmanProblem,简称TSP)是著名的组合优化问题[1].经典的TSP问题可描述为：设有n个城市1,…，n,由i城市到j城市的路程dij已知，一个旅行商为了

2、推销货物，从某一城市出发，如何选择一条最优路线可以经过所有其他城市，且每个城市正好经过一次,然后回到出发点•容易看出，旅行商有(n-1)!种方案可供选择•即使n是较小的两位数，这类问题仍没有较好的有效算法，因此被称为NPcomplete问题•但是TSP问题在组合优化问题中具有广泛实际背景和深刻经济含义•例如,在计算机的集成电路设计中就出现了这一问题，还包括派车、排序、底板布线、考古学中的排号、自动钻井、工件加工顺序和邮局收发信件等其他许多方面，所有这些需要促使学者们不断地研究TSP问题的算法［2］.目前国内外求解TSP问题的较好算法有遗传算法、神经网络算

3、法、模拟退火算法、蚁群算法和粒子群算法等［3-7］,这些算法中遗传算法具有较好的全局搜索能力，但优化过程缓慢，结果准确度不高；粒子群算法局部搜索能力较弱；蚁群算法等存在计算速度较慢等缺点.因此，以这些算法为基础，较多学者相继提出了改进的算法以更好地求解TSP问题［8-13］.2最小调整法求解TSP问题的思想和步骤最小调整法［14］是以Dijkstra算法［15］为实现途径的一种多项式算法.本文根据最小调整法，给出了求解TSP问题的一种新的有效启发式算法•该算法较之以往常用的启发式算法更加简单易行，计算量仅为0(n2),并且由此得到的近似解一般更接近最优解

4、.下面首先根据指派问题和TSP问题的异同点比较，然后提出将TSP问题先看做指派问题利用最小调整法求解［16］的具体步骤.2.1TSP问题与指派问题的异同对比指派问题和TSP问题，它们有如下异同点：第一，指派问题中，第i项任务可以由第i人去完成，因此其解可以在效率矩阵(成本)矩阵的主对角线上；但TSP问题中不存在从Ai城市到Ai城市的情况，其解显然不会出现在距离矩阵的主对角线上，即有iHj的约束条件.第二，对于有n个人的指派问题，其解由n项任务所组成，这些任务在效率矩阵中既不同行又不同列；对于有n个城市的TSP问题，其解由n段行程构成，这些行程在距离矩阵中

5、既不同行又不同列.第三，xij=l或0表示指派问题的解，则效率矩阵任一行、任一列的效率参数之和均为1,即Lni=lxij=l且工nj=lxij=l(i,j=l,…，n),即每个任务只有一个人承担，每个人只能承担一项任务.TSP问题中工ni=lxij=l且Znj=lxij=l(i,j=l,…，n),即在回路上仅由1个城市出发至第j个城市；从第i个城市出发仅通往1个城市，即所有中间城市仅通过一次.第四，指派问题不存在回路问题，但TSP问题解的各段行程首尾相接，必然构成一个回路.通过比较指派问题和TSP问题的特点，上述第一和第四点说明指派问题与TSP问题有区别

6、，第二和第三点则是相同的•如果置TSP问题原始距离矩阵主对角线元素为一个相当大的正数M或记为“X”时，把TSP问题当作指派问题去求解，这种指派问题就具备了TSP问题的第一和第四点中某些特点了，然后再对该解检验其作为TSP问题的可行性.2.2最小调整法求解TSP问题的思想步骤若把带权完全图G当前结点当成任务的承担者，另外结点当成任务，边的权（城市间距离）为完成任务所用时间，则寻求最优Hamilton回路［14,15］是把图中结点怎样与别的结点进行单一指派，使每个结点既是一个结点的任务承担者，又是另一个结点的任务，这种指派使完成任务时间最短以及满足这些指派所

7、确定的路径（旅行商走过的路径即指派路径）构成一个回路的条件.指派路径构成一个回路是在一般指派问题中增加的条件.设TSP问题的关系矩阵为C其中元素cij表示由第i城市到第j城市的距离.步骤1取每列的一个最小值画圈，即得到一个最小方案.若这些画圈元素又分属于不同行，则得到相应指派问题的最优解，转步骤3；否则转步骤2.步骤2应把有两个或两个以上画圈元素行中的一个改画到同列别处，待到某一无圈行中有一元素画上圈，则算一次调整•如此进行，直到每行均有一个画圈元素时为止，然后转入步骤3即可.而每次调整均以目标函数（其值为各画圈元素之和）增值最小为原则.步骤3如果从步骤

8、1或2得到的指派问题最优解元素的任一行指标i出发，先到其列指标j为下一行指标的元