巨集啟發式解法在求解大規模旅行推銷員問題之應用

Applications of Metaheuristics to Large-Scale Traveling Salesman Problems

本研究整合門檻接受法(Thresho1d Accepting,TA)、大洪水法(The Great De1uge Algorithm,GDA)、兩極跳躍法(Flip F1op,FF)與傳統交換型改善法等方法，發展應用於大規模旅行推銷員問題(Large-Sca1e Trave1ing Sa1esman Prob1em,LTSP)之巨集做發式求解工具。本研究共設計了三種求解LTSP的執行無構，其分別為單一樣組之深度搜尋LTSPl、組合式模組之深度搜尋LTSP2、跳躍式模組之廣度搜尋LTSP3執行蔡構，並且自國際標竿題庫選擇12題(節點數500-1000點)LTSP{:列題進行各執行架構解題績效之分析與比較。經以C語言撰寫程式並設定多組測試參數於PC(W但dows呵，Pentium450,64MB RAM)土進行測試，結果發現:在兩種LTSPl測試祭構中，LTSP1(GDA)之解題績效為1.86%較LTSP1(TA)佳，但執行時間較長;在四種LTSP2測試蔡構中，以LTSP2(GDAlGDA)之執行模組求解績效1.86%最佳，且其第二階段鼓動參數之設定需以第一階段起始解為設定基準;在三種LTSP3測試蔡構中，以限制性跳躍方式之求解績效1.77%較佳，此一新發現可供未來研究FF控制參數之參考。此外，就各標竿例題的最佳結果而言，12題的平均誤差為1.26%'並有兩題(ali535、p654)突破文獻最佳紀錄。本研究結果顯示:有效結合深度搜尋與廣度搜尋之各種巨集敘發式方法，在大規模的問題求解上具有相當樂觀的應用潛力與機會。

This paper investigates how to integrate TA, GDA and FF metaheuristics with traditional exchange-heuristics for solving Large-Scale Traveling Salesman Problem. In the paper, we designed three hybrid metaheuristics, i.e. LTSP1, LTSP2, LTSP3,for solving LTSP. LTSP 1 has an intensification search framework with only one single TA or GDA module as the generic search engine. LTSP2 has an enhanced intensification search which has a two-stage generic search using TA or GDA at each stage. LTSP3 uses Flip-Flop algorithm for diversification search in addition to the TA and GDA generic search engines. All these hybrid metaheuristics were programmed in C and tested on a Pentium 450 PC ρVindow98). A set of 12 benchmark LTSP problems with 500 的1000 nodes were adopted as the test instances for testing our proposed metaheuristic methods. It is found that GDA in general yielded better results than TA. Restricted Flip-Flop is more effective than full Flip-Flop for solving LTSP. The average deviation between our best found solutions and the best-known solutions adopted in literature of the 12 tested benchmark problems is merely 1.2%. We also have found the new best-known solutions for two benchmark problems, i.e. ali535 and p654.