大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用

Abstract

本論文探討應用巨集啟發式解法，求解1000點以上的大規模旅行推銷員問題(Large scale Traveling Salesman Problem, LTSP)，結合鄰域搜尋法(Local Search)與新近發展之巨集啟發式解法建立執行架構，包括門檻接受法(Threshold Accepting, TA)、大洪水法(The Great Deluge Algorithm, GDA)及兩極跳躍法(Flip Flop, FF)等，並以22題1,002至4,461點之國際標竿例題進行測試。 研究中針對TA之起始門檻值參數進行修正，將22題例題之平均誤差由5.256 %降至2.343 %，明顯的改善了TA之效果。此外，提出一創新性之TA執行架構--限制型TA (Bounded TA)，提供另一種執行策略，測試結果顯示限制型TA求解績效非常顯著。整體TA之22題最小成本誤差平均為2.176%。 本研究亦修正原始GDA之概念可能忽略更優解之情形，並針對參數--消退速度(DS)與起始水位(WL0)採取不同進行策略測試，並配合低水位策略，進行求解，整體GDA架構求解各題之最小成本誤差平均為2.508 %(消退速度I)與2.076 %(消退速度II)。 研究架構應用GIDS架構求解之概念：先取得起始解後，進行鄰域搜尋，再以TA與GDA改善，避免陷入區域最佳解(Local Optimum)，此外，在一區域進行深度化搜尋後，使用FF對解空間進行擾動，跳躍至另一區域，增加搜尋之廣度，再度進行搜尋，以此概念將TA、GDA、FF三種巨集啟發式解法進行結合。 測試結果發現：此種架構對單獨執行TA或GDA之改善績效介於9 % 至22 %，但由於多進行一階段的運算，時間增加幅度介於原時間之1.17至2.02倍，最小成本誤差平均更降至1.4 %，突破以往使用傳統交換法之屏障3 % 至5%，表示此種結合深度化與廣度化之求解架構有相當之應用潛力。本研究並對FF進行績效測試，將FF結合Chained Lin-Kernighan演算法進行兩項實驗，發現FF能有效擾動解空間，使後續演算法獲得更精確的解。

This thesis applies various meta-heuristics methods to solve the Large-scale Traveling Salesman Problem (LTSP). We have applied generic meta-heuristics including the Threshold Accepting (TA), Great Deluge Algorithm (GDA), and Flip-Flop (FF). A bank of 22 benchmark TSP instances form the TSPLIB is selected to evaluate the performance of different solution methods. The problem size of the test problems ranges from 1,002 to 4,461. We have developed various hybrid meta-heuristics and coded the programs in C. All the programs are tested on Dual Pentium III 550 PC (Windows 2000 Server). In the research, we modified parameter settings of TA, GDA, and created a new framework of TA -- Bounded TA. The average accuracy deviation from the best known solutions of the 22 tested problems are: 2.176% for TA, 2.508% for GDA(I), and 2.076% for GDA(II). The research also adopts the GIDS (Generic Intensification and Diversification Search) concept, to design two-stage meta-heuristics. We use flip-flop algorithm for diversification search in addition to the TA and GDA generic search engines. Considering different strategies, we developed six implementation procedures for TA-FF-TA, TA-FF-GDA(I), GDA(I)-FF-TA, GDA(II)-FF-TA, GDA(I)-FF-GDA(I), and GDA(II)-FF-GDA(I). Among different two-stage solution methods, TA-FF-TA seems to yield better average performance than others. Results show that the average accuracy deviations of the 22 tested problems are all lower than 2.2%, and the best is merely 1.4%. This also implies that these GIDS meta-heuristics methods are robust.