改良型巢狀分割法應用於旅行推銷員問題之研究

A MODIFIED NESTED PARTITIONS META-HEURISTICS FOR THE TRAVELING SALESMAN PROBLEM

旅行推銷員問題 （traveling salesman problem, TSP） 是組合最佳化問題的典型代表，其應用範圍雖廣，解題複雜度卻屬於NP-Complete，因此實務應用上多以啟發式解法 （heuristic） 來求得近似解。本研究以新近發展的巢狀分割法 （nested partitions, NP） 為基礎，導入廣度搜尋 （diversification search） 及深度搜尋 （intensification search） 的概念，輔以傳統鄰域搜尋法來強化NP 法之深度搜尋工具，並配合多種回溯機制的應用，提出一個可應用於求解TSP 問題的改良型NP 法解題架構。為驗證改良型NP法之解題績效，本研究選擇20 題TSP 國際標竿例題 （規模自16 點至561 點），並設計不同的模組組合型態及控制參數來進行測試。結果發現：本研究所提出之強化深度搜尋概念與有限制幅度的回溯機制，其解題績效均優於原NP 法解題架構之績效。此外，門檻參數p 值與回溯幅度h值之間略呈現負相關的趨勢，經由大規模數值測試可知，績效較佳的設定範圍為：p 值0.60 ~ 0.75、h 值8% ~ 10%；其中以p = 0.65、h = 9% 之績效最佳，平均誤差僅1.17%。而測試過程中得到之各題最佳結果平均誤差則降至1.14%，顯示改良型NP 法確實對提升TSP 解題績效有所助益。

This paper presents an implementation of the Modified Nested Partitions(MNP) meta-heuristics for solving the Traveling Salesman Problem (TSP). TheNP method systematically partitions the feasible region and concentrates thesearch in regions that are the most promising. The most promising region isselected in each iteration based on information obtained from random samplingof the entire feasible region and local search. In the MNP, we modified the NPmethod’s random sampling, local search methods and backtracking rules.Twenty problems from TSPLIB library are used to test the quality of the MNP.The average accuracy of the best solutions of the twenty problems computed bythe MNP is 1.14% above the performance of the current best known solutions.