计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2015年
3期
752-758
,共7页
嵌套分区算法%局部搜索算法%Lin-Kernighan算法%带约束的3-opt算法%旅行商问题
嵌套分區算法%跼部搜索算法%Lin-Kernighan算法%帶約束的3-opt算法%旅行商問題
감투분구산법%국부수색산법%Lin-Kernighan산법%대약속적3-opt산법%여행상문제
nested partitions algorithm%local search algorithm%Lin-Kernighan algorithm%restricted 3-opt algorithm%traveling salesman problem(TSP)
提出了一种混合多种局部搜索算法的嵌套分区算法用于求解中小规模旅行商问题.该算法使用加权抽样法产生初始最可能域,用带约束的3-opt局部搜索算法搜索每个子域的最优解,然后对Lin-Kemighan算法进行了改进,并且用改进的Lin-Kemighan算法搜索每个裙域的最优解,最后通过实验分析法确定了子域和裙域最优的抽样个数及初始最可能域的长度.对TSPLIB中15个问题实例的仿真结果表明,所提出的混合局部搜索算法的改进嵌套分区算法在求解旅行商问题时可以获得高质量的解.
提齣瞭一種混閤多種跼部搜索算法的嵌套分區算法用于求解中小規模旅行商問題.該算法使用加權抽樣法產生初始最可能域,用帶約束的3-opt跼部搜索算法搜索每箇子域的最優解,然後對Lin-Kemighan算法進行瞭改進,併且用改進的Lin-Kemighan算法搜索每箇裙域的最優解,最後通過實驗分析法確定瞭子域和裙域最優的抽樣箇數及初始最可能域的長度.對TSPLIB中15箇問題實例的倣真結果錶明,所提齣的混閤跼部搜索算法的改進嵌套分區算法在求解旅行商問題時可以穫得高質量的解.
제출료일충혼합다충국부수색산법적감투분구산법용우구해중소규모여행상문제.해산법사용가권추양법산생초시최가능역,용대약속적3-opt국부수색산법수색매개자역적최우해,연후대Lin-Kemighan산법진행료개진,병차용개진적Lin-Kemighan산법수색매개군역적최우해,최후통과실험분석법학정료자역화군역최우적추양개수급초시최가능역적장도.대TSPLIB중15개문제실례적방진결과표명,소제출적혼합국부수색산법적개진감투분구산법재구해여행상문제시가이획득고질량적해.