运筹与管理
運籌與管理
운주여관리
OPERATIONS RESEARCH AND MANAGEMENT SCIENCE
2012年
6期
1-9
,共9页
运筹学%旅行商问题%改进贪婪算法%Held Karp 模型
運籌學%旅行商問題%改進貪婪算法%Held Karp 模型
운주학%여행상문제%개진탐람산법%Held Karp 모형
operations research%traveling salesman problem%improved greedy heuristic%Held Karp model
分析了求解旅行商问题(Traveling Salesman Problem,TSP)的经典贪婪算法(Greedy Heuristic,GR)的特点,发现影响 GR 求解质量的主要因素是在构造后期添加的边过长,从而导致最终求解质量不高.为此,借鉴Held Karp 模型的思路,构造了一种新的距离矩阵改造法(Transforming Distance Matrix, TDM). GR 结合 TDM 得到的改进贪婪算法 GR-TDM 能够有效地克服传统 GR 在构造后期添加长边的缺点.通过计算来自 TSP 算例标准库和 TSP 世界挑战赛网站中的40个算例表明,GR-TDM 耗时较 GR 仅增加了0.5~2%,然而 GR-TDM 的求解质量较传统的 GR 提高了43%.另外,通过与当前构建型算法比较发现,GR-TDM 的求解性能达到一流构建型算法水平.
分析瞭求解旅行商問題(Traveling Salesman Problem,TSP)的經典貪婪算法(Greedy Heuristic,GR)的特點,髮現影響 GR 求解質量的主要因素是在構造後期添加的邊過長,從而導緻最終求解質量不高.為此,藉鑒Held Karp 模型的思路,構造瞭一種新的距離矩陣改造法(Transforming Distance Matrix, TDM). GR 結閤 TDM 得到的改進貪婪算法 GR-TDM 能夠有效地剋服傳統 GR 在構造後期添加長邊的缺點.通過計算來自 TSP 算例標準庫和 TSP 世界挑戰賽網站中的40箇算例錶明,GR-TDM 耗時較 GR 僅增加瞭0.5~2%,然而 GR-TDM 的求解質量較傳統的 GR 提高瞭43%.另外,通過與噹前構建型算法比較髮現,GR-TDM 的求解性能達到一流構建型算法水平.
분석료구해여행상문제(Traveling Salesman Problem,TSP)적경전탐람산법(Greedy Heuristic,GR)적특점,발현영향 GR 구해질량적주요인소시재구조후기첨가적변과장,종이도치최종구해질량불고.위차,차감Held Karp 모형적사로,구조료일충신적거리구진개조법(Transforming Distance Matrix, TDM). GR 결합 TDM 득도적개진탐람산법 GR-TDM 능구유효지극복전통 GR 재구조후기첨가장변적결점.통과계산래자 TSP 산례표준고화 TSP 세계도전새망참중적40개산례표명,GR-TDM 모시교 GR 부증가료0.5~2%,연이 GR-TDM 적구해질량교전통적 GR 제고료43%.령외,통과여당전구건형산법비교발현,GR-TDM 적구해성능체도일류구건형산법수평.
In this paper, we analyze the properties of the classic construction heuristic GR .It is found that the main disadvantage of GR is that the edges added by GR at last are too long , resulting in a poor tour.Thus an ap-proach transforming distance matrix(TDM)is proposed to improve the tour quality of GR , based on the theory of Held Karp model.As a consequence, GR combining TDM(GR-TDM)results in an efficient and effective heuris-tic, and GR-TDM overcomes significantly the disadvantage of GR .The experimental results on 40 instances from TSPLIB and TSP Challenge website show that GR -TDM is slower by 0.5 ~2% than GR for all instances, but the average tour quality of GR-TDM is better by 43% than that of GR.Moreover, GR-TDM is the first class heuristic among existing construction heuristics by comparing their tour quality and running time .
