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

旅行推銷員問題(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). The NP method systematically partitions the feasible region and concentrates the search in regions that are the most promising. The most promising region is selected in each iteration based on information obtained from random sampling of the entire feasible region and local search. In the MNP, we modified the NP method'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 by the MNP is 1.14% above the performance of the current best known solutions.

並列關鍵字

Traveling salesman problem TSP ； Meta-heuristics ； Nested partitions

參考文獻

Lawler, E.,Lenstra, J.,Rinnooy Kan, A.,Shmoys, D.(1985).The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization.Chichester:John Wiley and Sons.

Google Scholar

Bodin, L.,Golden, B.,Assad, A.,Ball, M.(1983).Routing and Scheduling of Vehicle and Crew: The State of Art.Computers and Operations Research.2(10),63-211.