應用禁制搜尋法求解優先順序旅行推銷員問題之研究

Applying Tabu Search on the Sequential Ordering Problem

葉心蘋(YEH HSIN PING)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(1998年)

摘要

本研究的主要目的是以禁制搜尋法為基礎，發展一套啟發式演算法，求解含有優先順序的旅行推銷員問題（簡稱SOP）。本研究首先利用途徑建構法獲得SOP初始路徑，接著在以禁制搜尋法改善。我們提出兩個初始解法：（1）最鄰近法與（2）隨機法；以及兩個途程解改善法：（1）兩點交換與（2）單點移動，合計四個模組。並以TURBO C 2.0 撰寫上述四個模組之程式。
在禁制搜尋法中，不同的參數設定會影響演算法的效果。在本研究所定義的參數包括初始解法、途程解改善法、最大運算次數、最大連續失敗次數、禁制列長度等。本研究中運用田口實驗設計手法，對禁制搜尋法中的各項參數進行實驗分析，獲得一組最佳運算組合。結果顯示以最鄰近法加單點移動效果為最佳。本研究並以國際題庫TSPLIB中的SOP測試例題驗證演算法的求解效率，測試結果得到誤差率平均為9.53％。

關鍵字

優先順序旅行推銷員問題 ； 禁制搜尋法 ； 田口方法

並列摘要

The purpose of this research is to develop a Tabu Search heuristic algorithm for the Sequential Ordering Problem (SOP), which sometimes is referred to as the Traveling Salesman Problem with Precedence Constraints. Two tour construction heuristics, namely, nearest neighborhood and random selection, are used to find an initial feasible tour of the problem, and two tour improvement procedures, namely, two-swap and one-point move, are used to improve the initial tour.
In our research, the Taguch''s method is used to find the most suitable values of the parameters in the proposed Tabu heuristic. The parameters include the tour construction methods, tour improvement procedures, maximum number of iterations, maximum number of continual failures, and the length of the Tabu list. Our experimental result shows that nearest neighborhood plus one-point move will deliver a better result. Our Tabu heuristic has an average error of 9.53% as compared to the best solution values in the SOP test problems of the TSPLIB.

並列關鍵字

Sequential Ordering Problem ； Tabu Search ； Taguchi method

參考文獻

[1] Balas E., and N.Christofieds, "A Restricted Lagrangean Approach to the Traveling Salesman Problem," Mathematical Programming , Vol.21, pp.19-46, 1981.

[2] Carpaneto G., and P.Toth, "Some New Branching and bounding Criteria for the Asymmetric Traveling Salesman Problem," Management Science, Vol.26, pp.736-743, 1980.

[3] Crowder H., and M.W.Padberg, "Solving Large-Scale Symmetric Traveling Salesman Problems to Optimality," Management Science, Vol.26, pp495-509, 1980.

[4] Desrochers M., and G. Laporte, "Improvements and Extensions to the Miller-Tucker-Zemlin Subtour Elimination Constraints," Operations Research Letters, Vol.10, pp.27-36, 1991.

[5] Duhamel C., J.Povtin, and J.Rousseau, "A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows," Transportation Science, Vol.31, No.1, pp.49-59.1997.