基于二点组合算法的旅行商问题应用性能分析  

Performance Analysis of Two Vertices Combination Algorithm in TSP

作　　者：赵玉章[1] 郭文强[1,2] 冯昊 

机构地区：[1]新疆财经大学计算机科学与工程学院,新疆乌鲁木齐830012 [2]电子科技大学计算机科学与工程学院,四川成都610054 [3]新疆公安厅十一处计算机科,新疆乌鲁木齐830009

出　　处：《计算机技术与发展》2011年第10期137-139,232,共4页Computer Technology and Development

基　　金：国家自然科学基金资助项目(60902074);新疆高校科研计划项目(XJEDU2009S79)

摘　　要：旅行商问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义。为高效快速解决旅行商问题,给出一种基于环路改造的二点组合算法,即选取一条汉密尔顿环路作为目标解,任取两个顶点删除与之相关的边形成2至4个环路片断,对这些环路片断进行排列组合,尝试寻找更优的解替换目标解的方法。仿真实验结果表明,该算法的计算效率和计算误差性能皆优于蚁群算法,实际应用结果也表明本算法在解决中小规模旅行商问题时的实用性。因此,本算法具有较强的理论价值和较强的实用价值,可以较好地完成中等规模的TSP问题,且适用于一系列的优化组合问题。In order to efficiently solve TSP problem, given a two vertices combination algorithm based on loop transformation. Hamilton Circle is selected as the target of a solution, take any two vertices associated with edges removed to form 2 to 4 loop clips, clips of permutations and combinations of these loops, try to find better solutions replaced target solution method. Comparing this method with ant colony algorithm, its time complexity and computational accuracy are better than those of the latter. The results show that this proposed algorithm possesses a better practicability in solving the middle and small scale traveling salesman problem. So, .this method has strong theoretical and practical value. It can better complete the medium-scale TSP problems, and it applied to a series of optimization.

关 键 词：旅行商问题 二点组合算法 环路改造 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]