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

A Modified Nested Partitions Meta-Heuristics for the Traveling Salesman Problem

10.6402/TPJ.200512.0549

張靖(Ching Chang)；卓裕仁(Yuh-Jen Cho)；藍宜祥(Yi-Hsiang Lan)

旅行推銷員問題 ； 巨集啟發式演算法 ； 巢狀分割法 ； Traveling salesman problem TSP ； Meta-heuristics ； Nested partitions

運輸計劃季刊

34卷4期（2005 / 12 / 30）

549 - 573

繁體中文

旅行推銷員問題(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.

1. TSPLIB
2. 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.
3. Junger, M.,Reinelt, G.,Rinaldi, G.(1995).The Traveling Salesman Problem.Handbooks in Operations Research and Management Science,7,115-313.
4. 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.
5. Lin, S.,Kernighan, B.(1973).An Effective Heuristic Algorithm for the Traveling Salesman Problem.Operations Research,21,498-516.
6. Reinelt, G.(1994).The Traveling Salesman: Computational Solutions for TSP Applications.Berlin:Springer-Verlag.
7. Shi L.,O'lafsson, S.(2000).Nested Partitions Method for Global Optimization.Operations Research,3(3),390-407.
8. Shi L.,O'lafsson, S.(2000).Nested Partitions Method for Stochastic Optimization.Methodology and Computing in Applied Probability,2,271-291.
9. Shi L.,O'lafsson, S.,Chen, Q.(1999).A New Hybrid Optimization Algorithm.Computers and Industrial Engineering,2(2),409-426.
10. Shi L.,O'lafsson, S.,Sun, L.(1999).New Parallel Randomized Algorithms for the Traveling Salesman Proble.Computers and Operations Research,4(4),371-394.
11. 卓裕仁(2001)。以巨集啟發式方法求解多車種與週期性車輛路線問題之研究。國立交通大學運輸工程與管理學系。
12. 陳建緯(2001)。大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用。國立交通大學運輸工程與管理學系。
13. 韓復華、王國琛(2000)。中華民國第五屆運輸網路研討會論文集。逢甲大學。
14. 韓復華、卓裕仁(2000)。中華民國第五屆運輸網路研討會論文集。逢甲大學。
15. 韓復華、楊智凱(1995)。門檻接受法在TSP 問題上之應用。運輸計劃季刊，25(2)，163-188。

1. 張靖、卓裕仁、李泰琳(2007)。調適型螞蟻演算法應用於旅行推銷員問題之研究。運輸學刊，19(1)，89-120。