應用分散搜尋法求解廣義旅行推銷員問題

A Scatter Search Heuristic for Solving the Generalized Traveling Salesman Problem

廣義旅行推銷員問題為旅行推銷員問題之延伸，與傳統旅行推銷員問題不同點在於多了節點分組的部分。本研究嘗試以分散搜尋法為基本架構，以random key的編碼方式，搭配不同新解產生方法與改善法，並結合門檻接受法，針對文獻既有之測試案例進行測試。一系列的數值實驗用以探討不同的改善法之策略在不同新解產生方法，搭以不同的門檻接受法來測試其求解效率。結果顯示，測試文獻中既有41組標竿案例其求解誤差百分率皆小於1％，節點數200點以下求解時間均較文獻有所改善，31個案例中有17求解效能與文獻相同，且平均時間較短。

The generalized traveling salesman problem (GTSP) is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters. This paper focused on devising an algorithmic procedure based on random key coding technique under the scatter search framework for solving the GTSP. Two different solution combination methods and improvement methods were investigated and validated based on a set of test instances used in the previous study. The numerical results showed that the test errors were less than 1% for all the test instances and the computation times were shorter than the ones obtained by the previous study when the number of nodes is less than 200. With less computation efforts, the procedure proposed by this study can obtain the optimal solutions in 17 out of 31 test instances.