臺灣博碩士論文加值系統

本研究主要目的是以塔布搜尋法（Tabu Search）為基礎，發展出一套兼
顧解之品質與效率的啟發式演算法來求解含優先順序混合郊區郵差問題。
首先，提出兩個初始解獲得法與三個鄰近解選取法，形成六種塔布搜尋法
模組。其後，以Turbo C++ 撰寫上述六種塔布搜尋法模組之程式並產生模
擬數據。應用變異數分析(ANOVA)與Bonferroni檢定法等統計方法對數據
加以分析，進而獲得各塔布演算法模組在不同問題類型下的最佳參數設定
。各塔布演算法模組在其最佳參數設定下重新收集與分析模擬數據，以決
定在何種問題類型下應使用的塔布演算法模組。

The main purpose of this research is to use Tabu Search method
as the basis to develop a good heuristic algorithm for the Mixed
Rural Postman Problem with Hierarchical Constraints. We propose
two initial solution methods and three neighborhood search
methods which are used to combined into six different heuristic
algorithms. Programming language TURBO C++ is used to encode the
above six heuristics and generate experimental data. Then based
on these data, Analysis of Variance (ANOVA) and Bonferroni
Adjustment are applied to analyze to set the best parameters
values of each heuristics. After this, the heuristics are use to
gather data again in their best settings. As a result for
analyzing these new data, we conclude that Tabu Ⅰand Tabu Ⅳ
are the best heuristics in this research.

書名頁………………………………i
口試委員審定書……………………ii
授權書………………………………iii
中文摘要……………………………vi
英文摘要……………………………vii
誌謝……………………………… viii
目錄…………………………………ix
表目錄………………………………xi
圖目錄………………………………xii
一、 導論 1
1.1 研究背景 1
1.2 研究動機 1
1.3 研究目的 2
1.4 研究範疇與假設 2
1.5 研究流程 3
1.6 研究架構及流程 4
二、 問題描述 5
三、 文獻探討 6
3.1 相關文獻 6
3.2 求解方式 7
3.3 啟發式演算法 7
3.4 塔布搜尋法 8
四、 研究方法 10
4.1 建構初始可行解 10
4.1.1 初始解法Ⅰ 10
4.1.2 初始解法Ⅱ 11
4.2 鄰近解定義 12
4.2.1 部分搜尋 12
4.2.2 區塊搜尋 12
4.2.3 全搜尋 14
4.3 塔布表單 14
4.4 免禁準則 16
4.5 結束法則 16
4.6 執行流程 17
4.7 計算複雜度 18
五、 實驗結果與分析 20
5.1 實驗環境 20
5.2 測試問題之設定 21
5.3 測試參數項目 21
5.4 各模組之測試參數 22
5.5 顯著水準 23
5.6 各模組最佳參數設定 24
5.6.1 任務網枝個數 20 24
5.6.2 任務網枝個數 50 25
5.6.3 任務網枝個數 80 25
5.7 演算法之比較 26
5.7.1 任務網枝個數 20 27
5.7.2 任務網枝個數 50 28
5.7.3 任務網枝個數 80 29
5.8 TABU Ⅰ與TABU Ⅴ的比較 30
六、 結論與展望 32
6.1 結論 32
6.2 未來展望 33
參考文獻 34
附 錄 36

表目錄
頁次
表3-1 相關文獻 6
表3-2 啟發式演算法之比較 8
表4-1 塔布表單記憶架構 14
表4-2 本研究塔布表單記憶架構 16
表4-3 變動後之塔布表單 16
表5-1 塔布搜尋法模組 20
表5-2 參數測試表 22
表5-3 各參數在不同題目類型下之顯著水準表23
表5-4 任務網枝個數為20之最佳參數設定 24
表5-5 任務網枝個數為50之最佳參數設定 25
表5-6 任務網枝個數為80之最佳參數設定 26
表5-7 在不同問題類型下之初始解法Ⅰ與初始解法Ⅱ26
表5-8 任務個數為20之平均成本與求解時間表27
表5-9 任務個數為50之平均成本與求解時間表28
表5-10 任務個數為80之平均成本與求解時間表29
表5-11 各問題類型適用之演算法模組 30
表5-12 任務網枝個數為80之標準題目2的數據 31



圖目錄
頁次
圖1-1 研究流程圖 3
圖2-1 基底網圖 5
圖2-2 網枝優先順序圖 5
圖4-1 初始解法Ⅰ 11
圖4-2 部分搜尋鄰近解 12
圖4-3 區塊搜尋鄰近解 13
圖4-4 搜尋示意圖 13
圖4-5 初始解 15
圖4-6 本研究塔布演算法流程19

1. Ahuja, R. K., T. L. Magnanti and J. B. Orlin. Network Flows: Thoery, Algorithms, Applications, Prentice-Hall, New Jersey. 1993.
2. David, R. A., J. S. Dennis, and A. W. Thomas. Statistics for Business and Economics, West, 427-435. 1993.
3. Dror, Moshe, Langevin, Andre. 〝Generalized Traveling Salesman Problem Approach to the Directed Clustered Rural Postman Problem, 〞 Transportation Science, 31, pp. 187-192. 1997.
4. Dror, M., H. Stern, and P. Tredeau. 〝Postman Tour on a Graph With Precedence Relation on Arcs,〞 Networks, 17, 283-294. 1987.
5. Eiselt, H.A., M. Gendreau, and G. Laporte. 〝Arc Routing Problems, part Ⅰ: The Chinese Postman Problem,〞 Operations Research, 43, pp. 231-242. 1995.
6. Eiselt, H.A., M. Gendreau, and G. Laporte. 〝Arc Routing Problems, partⅡ: The Rural Postman Problem,〞 Operations Research, 44, pp. 399-415. 1995.
7. Garcia, B. L., J. Y. Potvin, and J. M. Rousseau. 〝A Parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problems with Time Window Constraints,〞 Computers Ops Res, 21, Vol. 9, pp. 1025-1033. 1994.
8. Gelians, E. 〝Postman Tour with General Precedence Relation on Arcs,〞Naval Research Logistics Quarterly, Vol. 38. pp. 376-390. 1992.
9. Gendreau, M., A. Hertz, and G. Laporte. 〝A Tabu Search Heuristic for the Vehicle Routing Problem,〞 Management Science, 40, Vol. 10, pp. 1276-1290. 1994.
10. Glover, F. 〝Tabu search, Part Ⅰ,〞ORSA J. Comp, 1, pp. 190-206. 1989.
11. Glover, F. 〝Tabu search, Part Ⅱ,〞 ORSA J. Comp, 2, pp. 4-32. 1989.
12. Golden, B. L. and C. C. Skiscim. 〝Using Simulated Annealing to Solve Routinf and Location Problems,〞 Naval Research Logistics Quarterly, Vol. 33, pp. 261-279. 1986.
13. Lenstra, J. K., and A. H. G. Rinnooy Kan. 〝On General Routing Problem,〞 Networks, 6, pp. 273-280. 1976.
14. Metropolis, N., et al. 〝Equation of State Calculation by Fast Computing Machines,〞 J. of Chem. Phys., 21, pp. 1087-1091. 1953.
15. Orloff, C. S. 〝A Fundamental Problem in Vehicle Routing,〞 Networks. 4, pp. 35-64. 1974.
16. Reeves, C. R. Modern Heuristic Techniques for Combinatorial Problem, John Wiley & Sons. Inc., pp. 70-150. 1993.
17. Roberts, S. M. and B. Flores. 〝An Engineering Approach to the Traveling Salesman Problem,〞 Man. Sci., 13. pp. 269-288, 1966.
18. 呂金河，「變異數分析」，三民書局，民國82年2月。
19. 徐明輝，「多部車一般性車輛途程解算法之研究」，元智工學院，碩士論文，民國86年6月。