基于四边形最优圈内最短路径的旅行商问题割边方法

摘要：

随着旅行商问题规模的增长,完全图上最优解的搜索空间呈指数增长.为了减小最优解的搜索空间,提出一种针对旅行商问题的割边算法.推导出四边形最优圈内的最短路径包含一般边与最优哈密顿圈边的不同概率,采用一定数量的四边形最优圈内的最短路径计算边频率,根据所有边的平均边频率割边,基于建立的二项分布模型推导出最优哈密顿圈内边的保留概率.任给一个完全图,割边算法有4个步骤:1)随机选取包含每条边的若干个四边形;2)采用所选四边形最优圈内的最短路径计算各边的边频率;3)步删除5/6条最小边频率的边;4)对度数小于2的节点进行添边操作.计算实验表明:保留边数为完全图上边数量的1/6左右,采用精确算法求解割边后旅行商问题的计算时间也有所减少.

关键词：旅行商问题、割边方法、四边形最优圈、最短路径、边频率

所属期刊栏目：49

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

资助基金：国家自然科学基金;国家重点研发计划

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

页数：共7页

页码：199-205