一个基于填充函数变换的对称TSP问题的局部搜索算法

摘要

该文提出了求对称TSP问题近优解的填充函数算法. 首先, 在用局部搜索算法求得对称TSP问题的一个局部极小解后, 对该问题作填充函数变换得到一新的组合优化问题, 新问题的局部极小解和最优解分别是原问题的局部极小解和最优解, 而且在对称TSP问题的目标函数值大于或等于其目标函数当前极小值的区域中, 新问题只有一个已知的局部极小解. 随后用局部搜索算法求新问题的一个局部极小解, 它或者是已知的局部极小解, 或者是对称TSP问题的更好的局部极小解. 对多个标准实例的计算试验表明,该文所构造的算法优于直接求解对称TSP问题的局部搜索算法.