摘要
建立了描述TSP问题启发集性质的概率模型,并指出了改进启发集的一般方法.进一步,利用局部最优解交集作为近似骨架,提出了一种动态改进启发集的宏启发算法———自适应可变启发集搜索.并将自适应可变启发集搜索与目前广泛使用的算法ILK、LKH相结合,TSPLIB中典型实例上的实验结果表明,改进后的算法在求解质量上有了较大的改进.
A statistical model depicting the properties of candidate sets is built, and the general ways are given to improve them. Using the intersection of local optimal solutions as the approximate backbone, a new meta-heuristic-Self-Adaptive Variable Candidate Sets Search （SAVCSS）, which shrinks the candidate sets dynamically, is proposed. Furthermore, ILK and LKH are incorporated in the new meta-heuristic, Experiment results on TSPLIB indicated that the modified algorithms is capable of better performance in terms of solution quality.
基金
国家"973"项目(G1998030403)
关键词
旅行商问题
启发集
局部搜索
骨架
traveling salesman problem
candidate set
local search
backbone
