含優先順序混合郊區郵差問題解算之研究

A Tabu Search Heuristic for the Mixed Rural Postman Problem with Hierarchical Constraints

鍾偉仁(Wei-Jen Chung)

指導教授 ： 徐旭昇

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

摘要

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

關鍵字

塔布搜尋法 ； 優先順序 ； 變異數分析 ； 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.

並列關鍵字

Tabu Search method ； Hierarchical Constraints ； ANOVA ； Bonferroni Adjustment

參考文獻

1. Ahuja, R. K., T. L. Magnanti and J. B. Orlin. Network Flows: Thoery, Algorithms, Applications, Prentice-Hall, New Jersey. 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.