改进的求解TSP混合分支裁剪法

摘要：

分支裁减法是一种有效的求解小规模TSP的整数规划方法.随着TSP规模的逐步扩大,问题求解的复杂性也随之增加.在TSP的可计算数学研究领域中,局部搜索算法能快速求解TSP的局部最优解.通过将局部搜索算法与分支裁减法结合,利用局部搜索算法对分支裁减法获得上界所对应环路进行优化,使分支限界算法的上界更快地向全局最优解靠近,提高算法的求解效率,扩大了分支裁减法求解TSP的规模.

关键词：分支裁剪法、局部搜索算法、旅行商问题、问题规模、算法效率

所属期刊栏目：29

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金40473029

在线出版日期：2008-05-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：424-425,499