系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
Systems Engineering—Theory & Practice
2011年
8期
1419~1428
,共null页
旅行商问题 混合算法 最近邻域算法 插入算法
旅行商問題 混閤算法 最近鄰域算法 插入算法
여행상문제 혼합산법 최근린역산법 삽입산법
traveling salesman problem; the hybrid algorithm; the nearest neighbor algorithm; the insertion algorithm
研究了求解旅行商问题（TSP）的构建型启发式算法中的最近邻域算法和插入算法的特点,集最近邻域算法求解速度快、插入算法求解质量高的优点,提出了一种最近邻域与插入混合算法.分析了混合算法的合理性、复杂度及参数取值,并分别采用以上三种算法求解了TSPLIB标准库中多个算例,结果表明混合算法的求解速度接近最近邻域算法,对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当,而对大规模TSP问题的求解质量明显优于插入算法.
研究瞭求解旅行商問題（TSP）的構建型啟髮式算法中的最近鄰域算法和插入算法的特點,集最近鄰域算法求解速度快、插入算法求解質量高的優點,提齣瞭一種最近鄰域與插入混閤算法.分析瞭混閤算法的閤理性、複雜度及參數取值,併分彆採用以上三種算法求解瞭TSPLIB標準庫中多箇算例,結果錶明混閤算法的求解速度接近最近鄰域算法,對城市數量小于1000的小規模TSP問題的求解質量與插入算法相噹,而對大規模TSP問題的求解質量明顯優于插入算法.
연구료구해여행상문제（TSP）적구건형계발식산법중적최근린역산법화삽입산법적특점,집최근린역산법구해속도쾌、삽입산법구해질량고적우점,제출료일충최근린역여삽입혼합산법.분석료혼합산법적합이성、복잡도급삼수취치,병분별채용이상삼충산법구해료TSPLIB표준고중다개산례,결과표명혼합산법적구해속도접근최근린역산법,대성시수량소우1000적소규모TSP문제적구해질량여삽입산법상당,이대대규모TSP문제적구해질량명현우우삽입산법.
This paper presented a new hybrid construction heuristic algorithm（NNIN） -combination of the nearest neighbor algorithm（NN） and the insertion algorithm（IN）,based on analyzing properties of NN and IN algorithm for solving the traveling salesman problem（TSP）.Moreover,we studied the rationality, complexity,parameter setting of the hybrid algorithm and solved many benchmark instances from TSPLIB using NN,NNIN,IN algorithm respectively.Computational results show that NNIN algorithm whose running time is close to NN can yield solutions as good as IN for small TSP（the number of city is less than one thousand） and better solutions for large TSP than IN,and prove that the efficiency and effectiveness of the proposed hybrid algorithm outperform both NN algorithm and IN algorithm.
