分支定界TSP(精)

２００７年第２８卷第２期中北大学学报（自然科学版）Ｖｏｌ．２８　Ｎｏ．２　２００７（总第１１２期）JOURNALOFNORTHUNIVERSITYOFCHINA（NATURALSCIENCEEDITION）（ＳｕｍＮｏ．１１２）文章编号：１６７３-３１９３（２００７）０２-０１０４-０４用分支定界算法求解旅行商问题管　琳，白艳萍（中北大学理学院，山西太原０３００５１）摘　要：　在０－１整数规划的基础上建立了数学模型，利用ＭＡＴＬＡＢ６．５优化工具箱中的ｌｉｎｐｒｏｇ函数进行求解，再经过分支定界算法计算，求出了只含有０和１的解．实验结果表明，该算法可以求解小规模旅行商问题．关键词：　旅行商问题；分支定界；ｌｉｎｐｒｏｇ函数中图分类号：　Ｏ２９　　　文献标识码：ＡABranchandBoundAlgorithmforTravelingSalesmanProblemＧＵＡＮＬｉｎ，ＢＡＩＹａｎ-ｐｉｎｇ（ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＮｏｒｔｈＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎａ，Ｔａｉｙｕａｎ０３００５１，Ｃｈｉｎａ）Abstract：Ｂａｓｅｄｏｎ０－１ｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ，ｍａｔｈｅｍａｔｉｃｓｍｏｄｅｌｉｓｓｅｔａｎｄｓｏｌｖｅｄｂｙｌｉｎｐｒｏｇｆｕｎｃｔｉｏｎｉｎｏｐｔｉｍｉｓｔｉｃｔｏｏｌｂｏｘｏｆＭＡＴＬＡＢ６．５．Ｔｈｅｓｏｌｕｔｉｏｎｏｎｌｙｃｏｎｔａｉｎｉｎｇｚｅｒｏｓａｎｄｏｎｅｓｉｓａｃｑｕｉｒｅｄｕｓｉｎｇｂｒａｎｃｈａｎｄｂｏｕｎｄａｌｇｏｒｉｔｈｍ．ＴｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｓｕｉｔａｂｌｅｆｏｒｓｍａｌｌＴＳＰ（ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ）．Keywords：ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ；ｂｒａｎｃｈ-ａｎｄ-ｂｏｕｎｄａｌｇｏｒｉｔｈｍ；ｌｉｎｐｒｏｇｆｕｎｃｔｉｏｎ１　旅行商问题简介所谓“旅行商问题”，即ＴＳＰ（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ）问题是一个十分有名的难以求解的优化问题，其要求很简单：在个城市的集合中，找出一条经过每个城市各一次，最终回到起点的最短路径．如果用dij表示从城市i到城市j的距离，则路径的总长度d＝∑dij．ＴＳＰ的最优解是求长度d为最短的一条有效的路径．因为对于n个城市的全排列共有n！种，而ＴＳＰ没有限定路径的方向，即为全组合，所以其旅行方案数为n！２n（n≥４）种［１］１２２．若采用穷举搜索法，则需要考虑所有可能的情况，再进行比较，找出最短路经．因其计算复杂度随城市数目的增加呈指数增长，可能无法计算．这类问题称为完全非确定性多项式问题（ＮｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃＰｏｌｙｎｏｍｉａｌＣｏｍｐｌｅｔｅ），简称ＮＰ完全问题．ＴＳＰ问题在组合优化中是一个求最小的带权哈密顿回路问题［１］２１９，哈密顿圈是一个完全无向图，每个顶点的度为２．因此，假设n个城市为n个顶点，顶点集合V＝｛１，２，…，n｝，各个城市之间有路连接就称两个顶点间有一条边，用E＝｛Xij│（i，j），i，j＝１，２，…，n｝表示边的集合，且Xii＝０．用D（dij）表示距离矩阵，D是一个对称阵．xij是一个０－１型变量，且xij＝１，点i与点j之间有边０，否则．由上述假设对磁收稿日期：２００６-０５-２２　基金项目：山西省自然科学基金资助项目（２００５１００６）　作者简介：管琳（１９８１-），女，硕士生．主要从事神经网络算法与应用研究．白艳萍（１９６２-），女，教授，博士．硕士生导师．ＴＳＰ问题建立如下数学模型ｍｉｎz＝∑i∈v∑j∈vxijdij，ｓ．ｔ．∑j∈vxij＝２对所有i∈V，∑i∈S，j∈v－sxij≥２对所有S炒V，３≤S≤［V２］，xij∈｛０，１｝ij∈E．　　以４个城市的ＴＳＰ问题为例，用上述模型求ＴＳＰ的最短路径．随机地取距离矩阵D＝０７８２１１３７８０１１１４２１１１０９１３１３９０，求解得到三组解，这三组解分别构成A，B，C三个邻接矩阵（A，B，C的邻接矩阵图如图１～图３所示）．A＝０１１０１００１１００１０１１０，B＝００１１００１１１１００１１００，C＝０１０１１０１００１０１１０１０．　　由计算可知，最优目标函数值z倡＝５９．显然，这是一个０－１的整数规划问题，可以用分支定界法求解．Fig．１Aａｄｊａｃｅｎｔｍａｔｒｉｘｆｉｇｕｒｅ图１A的邻接矩阵图Fig．２Bａｄｊａｃｅｎｔｍａｔｒｉｘｆｉｇｕｒｅ图２B的邻接矩阵图Fig．３Cａｄｊａｃｅｎｔｍａｔｒｉｘｆｉｇｕｒｅ图３C的邻接矩阵图３２４１３２４１４３２１２　分支定界算法分支定界算法（ＢｒａｎｃｈａｎｄＢｏｕｎｄＭｅｔｈｏｄ，Ｂ＆Ｂ）由ＬａｎｄＤｏｉｇ等人于２０世纪６０年代提出，其算法思想不仅适用于表达成整数线性规划（或混合整数线性规划）的问题，也适用于几乎任何组合优化问题［３］．它采用了类似分而治之的算法策略，在分析一个组合最优化问题一切可行解的过程中，采取了必要的限制条件，设法排除可行域中大量非最优解区域，从而能够求解一些规模较大的问题［２］．设有最小化整数规划问题P，相应的松弛问题P０．P：ｍｉｎz＝c′x，Ax≤b，x≥０，xi为整数；　　　P０：ｍｉｎz＝c′x，Ax≤b，x≥０．　　先求解P的松弛问题P０．P０的最优解不符合P的整数条件，则取其中一个非整数解分量xi＝ai，在约束条件的基础上增加一个整数约束xi≥［ai］＋１或xi≤［ai］，得到P１层的两个线性规划问题．分支定界法就是将P０的可行域F通过每次增加一个整数约束，分成两个子区域F１，F２，F１炒F，F２炒F，称为分支的方法．若子线性规划问题的解仍然不满足整数条件，则重复上述过程；若找到一个满足整数条件的解，则得到一个可行解，那么它的目标函数值就是一个“界限”，可作为衡量其他分支的一个依据，称之为“定界”．因为整数规划问题的可行解集是它的松弛问题可行解集的一个子集，前者最优解的目标函数值不会优于后者［１］２０，所以对于那些目标函数值比上述“界限”差的后继问题可以不再考虑了．当然，如果在以后的分支过程中出现了更好的“界限”，则以它取代原来的．分支定界算法可以等价于在一个深度为n的二叉树上的搜索，在二叉树的每一个节点上求解一个线性规划问题．每一个子节点都是在其父节点线性规划问题基础上增加一个约束xi≥［ai］＋１或xi≤［ai］的线性规划问题．因此，子节点的解不优于父节点［４］，其叶节点中的最优者是原问题P的最优解．可以看到，随着问题规模的增加，要进行约２０＋２１＋２２＋…＋２n个线性规划问题的求解，并且求解过５０１（总第１１２期）用分支定界算法求解旅行商问题（管　琳等）程中要存储大量的数据，进行多次比较，因此对于较大规模的ＴＳＰ问题此算法效率不高．经验表明，在可能的情况下，根据对实际问题的了解，事先选择一个合理的“界限”，可以提高分支定界法的搜索效率［１］１２０．文献［３］对上述分支定界法作了改进，使得求解效率进一步提高．将P０的最优值作为P的目标函数值的一个上界，记为z珔；而P的任意可行解的目标函数值将是的z一个下界，记为Z－．在搜索过程中，还可以逐步减小z珔和增大z－．因此，该方法应设法找到最优解的上下界，在上下界之外的节点不再考虑，称之为剪枝．一般遇到下列情况时需要剪枝：１）Pi无可行解；２）Pi的最优解符合整数约束，则不必再分支；３）Pi的最优值f珚i≥f珚，通过比较，若子问题不剪枝则继续分支［７］．当所有子问题都剪枝了，即没有需要处理的子问题时，达到当前上界的可行解即原问题的最优解，算法结束．由于子节点的解不优于父节点，因此确定下界意义不大，确定上界是一项十分有意义的工作［８］．３　实验结果与分析本文利用ＭＡＴＬＡＢ６．５优化工具箱中的ｌｉｎｐｒｏｇ函数对ＴＳＰ问题进行求解．实验数据由文献［１１］给出，如表１所示．表１　分支定界算法实验结果与最优解对比Tab．１　ＣｏｍｐａｒｉｓｏｎｂｅｔｗｅｅｎＢ＆Ｂｓｏｌｕｔｉｏｎａｎｄｔｈｅｂｅｓｔｓｏｌｕｔｉｏｎ实验数据分支定界最优解最优解Ｔｅｘｔ１６３．２３．２Ｔｅｘｔ２４４．３９９４．３９９Ｕｌｙｓｓｅｓ１６２．１５３５２．１２６Ａｔｔ４８４．４０９６３．８９２Ｅｉｌ１０１７．０６８１７．８１１图４　１６个城市最优路径图Fig．４　Ｂｅｓｔｔｏｕｒｏｆ１６ｃｉｔｉｅｓ图５　２４个城市最优路径图Fig．４　Ｂｅｓｔｔｏｕｒｏｆ２４ｃｉｔｉｅｓ　　从图４和图５中可以看到，分支定界算法对于解决小规模城市分布对称的问题是非常有效的．图６是用分支定界算法求出的路径，不是最优解．图７是该问题的最优路径．可以看到，随着问题规模的增大以及城市分布任意性的增加，运算复杂度呈指数性增长，运算量较大，迭代过程中产生的误差也较大，运算结果不理想．Ｅｉｌ１０１运算结果偏小，主要原因在于约束条件不足，使得路径中形成了多个圈．根据实际问题，可以考虑加入必要的约束条件，避免形成奇数圈和偶数圈．６０１中北大学学报（自然科学版）２００７年第２期图６　１６个不对称城市Ｂ＆Ｂ算法路径图Fig．６　Ｔｏｕｒｏｆ１６ａｓｙｍｍｅｔｒｙｃｉｔｉｅｓｂｙＢ＆Ｂ图７　１６个不对称城市最优路径图Fig．７　Ｂｅｓｔｔｏｕｒｏｆ１６ａｓｙｍｍｅｔｒｙｃｉｔｉｅｓ参考文献：［１］　胡运权．运筹学教程［Ｍ］．北京：清华大学出版社，１９９８：２０９-２１９．［２］　汪祖柱，程家兴．求解组合优化问题的一种方法分支定界法［Ｊ］．安徽大学学报（自然科学版），２００４，２８（１）：１０-１４．ＷａｎｇＺｕｚｈｕ，ＣｈｅｎｇＪｉａｘｉｎｇ．Ａｎａｌｇｏｒｉｔｈｍｏｎｓｏｌｖｉｎｇｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｂｒａｎｃｈ-ａｎｄ-ｂｏｕｎｄｍｅｔｈｏｄ［Ｊ］．ＪｏｕｒｎａｌｏｆＡｎｈｕｉＵｎｉｖｅｒｓｉｔｙＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ，２００４，２８（１）：１０-１４．（ｉｎＣｈｉｎｅｓｅ）［３］　ＭａｔｔｉａｓＥｌｆ，ＣａｒｓｔｅｎＧｕｔｗｅｎｇｅｒ，ＭｉｃｈａｅｌＪüｎｇｅｒ．ＧｉｏｖａｎｎｎｉＲｉｎａｌｄｉ：Ｂｒａｎｃｈ-ａｎｄ-ＣｕｔＡｌｇｏｒｉｔｈｍｓｆｏｒＣｏｍｂｉｎａｔｏｒｉａｌＯｐｔｉｍｉｚａｔｉｏｎａｎｄＴｈｅｉｒＩｍｐｌｅｍｅｎｔａｔｉｏｎｉｎＡＢＡＣＵＳ［Ｍ］，２０００：１６３-１７２．［４］　杜江，孟香惠．一种改进的分支定界算法［Ｊ］．数学杂志，１９９８，１８：５５-５８．ＤｕＪｉａｎｇ，ＭｅｎｇＸｉａｎｇｈｕｉ．Ａｎｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｆｏｒｂｒａｎｃｈ-ａｎｄ-ｂｏｕｎｄｍｅｔｈｏｄ［Ｊ］．ＪａｎｕａｒｙｏｆＭａｔｈ，１９９８，１８：５５-５８．（ｉｎＣｈｉｎｅｓｅ）［５］　ＰＥＭＳｈｕｔｌｅｒ．Ａｎｉｍｐｒｏｖｅｄｂｒａｎｃｈｉｎｇｒｕｌｅｆｏｒｔｈｅｓｙｍｍｅｔｒｉｃｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ［Ｊ］．ＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈＳｏｃｉｅｔｙ，２００１，５２：１６９-１７５．［６］　全惠云．求解ＴＳＰ的演化算法［Ｊ］．湖南师范大学自然科学学报，１９９９，２２（２）：２７-３４．ＱｕａｎＨｕｉｙｕｎ．ＡｎｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｆｏｒＴＳＰ［Ｊ］．ＡｃｔａＳｃｉｅｎｃｅＮａｔｒａｌＵｎｉｖｅｒｓｉｔｙＮｏｒｍＨｕｎａｎ，１９９９，２２（２）：２７-３４．（ｉｎＣｈｉｎｅｓｅ）［７］　吴祈宗．运筹学与最优化方法［Ｍ］．北京：机械工业出版社，２００３：１８０-１９１．［８］　袁亚湘，孙文瑜．最优化理论与方法［Ｍ］．北京：科学出版社，１９９７：４６７-４７３，６０８-６１４．［９］　白艳萍，胡红萍．一个改进的弹性网络算法求解ＴＳＰ问题［Ｊ］．中北大学学报，２００５，２６（４）：２３５-２３８．ＢａｉＹａｎｐｉｎｇ，ＨｕＨｏｎｇｐｉｎｇ．Ａｍｏｄｉｆｉｅｄｅｌａｓｔｉｃｎｅｔａｌｇｏｒｉｔｈｍｆｏｒｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ［