分支限界法求解实际TSP问题

摘要：

提出一种基于分支限界思想来求解实际TSP问题的算法,并着重介绍上下界的计算.下界值是根据当前路径来计算的,简单易行且占用空间少.上界只计算一个全局的上界值,计算过程中用到实际TSP问题的一个特点——三角不等式性质,求得的值不超过最优值的1.5倍.实际TSP问题另一个特点是对称性,对称性可使解空间树缩小一半,进一步加速搜索过程.提出的求上界和求下界的算法是独立,完全可以分割开来,但是通过例子可以看出将这两种方法用分支限界的思想结合起来是行之有效的,可大大加速解空间树的搜索.

关键词：旅行商问题、三角不等式、上界、下界、解空间树

所属期刊栏目：30

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

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

页数：共4页

页码：2431-2434