论文研究 一种混合局部搜索算法的嵌套分区算法.pdf

提出了一种混合多种局部搜索算法的嵌套分区算法用于求解中小规模旅行商问题。该算法使用加权抽样法产生初始最可能域，用带约束的3-opt局部搜索算法搜索每个子域的最优解，然后对Lin-Kernighan算法进行了改进，并且用改进的Lin-Kernighan算法搜索每个裙域的最优解，最后通过实验分析法确定了子域和裙域最优的抽样个数及初始最可能域的长度。对TSPLIB中15个问题实例的仿真结果表明，所提出的混合局部搜索算法的改进嵌套分区算法在求解旅行商问题时可以获得高质量的解。