臺灣博碩士論文加值系統

車輛路線相關問題（Vehicle Routing Related Problems, VRRP）在物流運輸之應用與研究領域中扮演相當重要的角色；隨著實務狀況與限制條件之不同，更衍生出許多複雜的應用類型。由於大多數VRRP的解題複雜度屬於NP-Hard，因此實務應用時大多採用能快速求解的啟發式方法，近年來更朝向巨集啟發式方法（Meta-heuristics）之發展。
本論文選擇VRRP當中較為困難的多車種車輛路線問題（Heterogeneous Fleet Vehicle Routing Problem, HVRP）與週期性車輛路線問題（Periodic Vehicle Routing Problem, PVRP）做為研究的對象，並發展一套可有效求解HVRP與PVRP之巨集啟發式方法及工具。本研究結合多種巨集啟發式方法的特性與優點，將接受劣解、變換鄰域、擾動成本與多重起點等巨集策略融合在深度搜尋與廣度搜尋的概念中，發展出一套「包容性深廣度搜尋（Generic Intensification and Diversification Search, GIDS）」的巨集啟發式方法。GIDS法共包含：(1) 多起始解構建（Multiple Initialization Constructor, MIC）、(2)深度化包容搜尋（Generic Search for Intensification, GSI）與(3) 廣度化擾動搜尋（Perturbation Search for Diversification, PSD）三個策略群組。整套GIDS法係以傳統鄰域搜尋為實際執行求解之工具，以深度搜尋之GSI群組為核心，再搭配廣度搜尋之PSD與MIC群組。此外，本研究更設計了五種模組來執行GIDS之策略群組：即在MIC群組構建有加權起始（Weighted Initialization, WI）模組與鄰域搜尋（Neighborhood Search, NS）模組；在GSI群組設計有G1與G2兩種包容搜尋（Generic Search）模組；在PSD群組中則構建有成本擾動（Cost Perturbation, CP）模組。
為檢視新提出之GIDS巨集啟發式方法在HVRP與PVRP應用上的適用性與發展潛力，本研究以實驗設計的理念配合選取若干國際標竿測試例題來進行平均狀況分析，並藉由撰寫電腦執行程式及測試國際標竿例題，與國內外文獻發表之最佳已知解（Best Known Solution）進行比較分析。歸納本論文之具體研究成果如下：
1. 在方法架構方面，GIDS法具有以下三項優點：(1) 不需要記憶結構，因此節省電腦的記憶體空間，可加快運算速度；(2) 控制參數少，參數設定容易；(3) 模組組合與執行方式更具有彈性，應用到不同的VRRP問題時，可以很快地設計出適當的解題架構。
2. 在例題測試方面，GIDS找到六題PVRP例題新的最佳紀錄；無論是HVRP或PVRP，GIDS的最佳解與文獻已知最佳解的平均誤差分別為0.58%與0.26%。
總而言之，GIDS的解題績效並不亞於國際文獻報導的數個績效最佳之方法，而且對控制參數之設定值較不敏感，證明GIDS法不僅適合求解VRRP這類複雜的問題，也是一個有效、穩健（Robust）且具有應用潛力的一個巨集啟發式方法。

The Heterogeneous Fleet Vehicle Routing Problem (HVRP) and Periodic Vehicle Routing Problem (PVRP) are two important variants of the conventional vehicle routing problem (VRP). Due to the NP-hard complexity of HVRP and PVRP, most existing methods for solving HVRP and PVRP are heuristics or metaheuristics.
The major contribution of this research is that we have developed a new metaheuristic approach, i.e. the Generic Intensification and Diversification Search (GIDS), for solving HVRP and PVRP. The GIDS integrates the use of some recently developed generic search methods such as Threshold Accepting (TA) and Great Deluge Algorithm (GDA), and the meta-strategies of intensification and diversification for intelligent search. The GIDS includes three components: Multiple Initialization Constructor (MIC), Generic Search for Intensification (GSI), and Perturbation Search for Diversification (PSD). We also designed five modules and proposed several modified algorithms for the implementation of the GIDS to HVRP and PVRP. As compared with the well-known tabu search, GIDS shares some similar ideas in the search strategies of intensification and diversification but does not require complicated memory scheme for computer implementation.
Both HVRP and PVRP benchmark instances were selected and tested by several different implementations of GIDS. The numbers of benchmark instances tested for HVRP and PVRP are twenty and thirty-two respectively. All programs were coded in UNIX C and ran on a SUN SPARC 10 workstation. Computational results are very encouraging; GIDS yielded comparable results with recent successful applications using the tabu search. Using GIDS, we have updated the best-known solutions for six of the PVRP instances. Moreover, for PVRP, the average deviation of our best solutions from the published best-known solutions is merely 0.26 %. For HVRP, the average deviation of our best solutions from the published best-known solutions is 0.58%. Such results imply that GIDS may provide an efficient and robust tool for real-world HVRP and PVRP applications.

目錄
中文摘要
英文摘要
目錄
圖目錄
表目錄
第一章緒論
1.1研究背景與目地
1.2研究流程與步驟
1.3章節簡述
第二章文獻回顧
2.1車輛路線相關問題之特性分析
2.2傳統啟發式方法回顧
2.3巨集啟發式方法回顧
第三章包容性深廣度搜尋方法架構
3.1GIDS法之解題概念
3.2GIDS法之執行模組設計
第四章GIDS于多車種車輛路線問題之應用分析
4.1HVRP問題定義與解法回顧
4.1.1HVRP定義與數學規劃模式
4.1.2HVRP啟發式解法回顧
4.2HVRP測試題庫之建立
4.3GIDS＿HVRP之模組設計
4.4GIDS＿HVRP之測試分析
4.4.1實驗設計與參數設定
4.4.2各階段測試結果歸整
4.4.3最佳結果之比較
4.4.4小結
第五章GIDS於週期性車輛路線問題之應用分析
5.1PVRP問題定義與解法回顧
5.1.1PVRP定義與數學規劃模式
5.1.2PVRP啟發式解法回顧
5.2PVRP測試題庫之建立
5.3GIDS＿PVRP之模組設計
5.4GIDS＿PVRP之測試分析
5.4.1參數設定與測試結果
5.4.2最佳結果比較
5.4.3小結
第六章結論與建議
6.1結論
6.2後續研究方向
參考文獻
附錄一：本研究求得20題HVRP例題之最佳結果
附錄二:本研究求得6題PVRP例題之最佳結果

Aarts, E. & J. Lenstra eds.(1997), Local Search in Combinatorial Optimization, John Wiley & Sons, New York.
Ball, M.(1988), "Allocation/Routing: Models and Algorithms," in B. Golden and A. Assad (eds.), Vehicle Routing: Methods and Studies,North-Holland, Amsterdam, pp.199-221.
Battiti, R. & G. Tecchiolli (1994), "The Reactive Tabu Search," ORSA Journal on Computation, Vol.6, pp.126-140.
Beltrami, E. & L. Bodin (1974), "Networks and Vehicle Routing for Municipal Waste Collection," Networks, Vol.4, pp.65-94.
Bodin, L., B. Golden, A. Assad & M. Ball (1983), "Routing and Scheduling of Vehicle and Crew: The State of Art," Special Issue of Computers and Operations Research, Vol.10, No.2, pp.63-211.
Chao, I., B. Golden and E. Wasil (1995), "An Improved Heuristic for the Period Vehicle Routing Problem," Networks, Vol.26, pp.25-44.
Charon, I. & O. Hudry (1993), "The Noising Method: a New Method for Combinatorial Optimization," Operations Research Letters, Vol.14, pp.133-137.
Christofides, N. & S. Eilon (1969), "An Algorithm for Vehicle Dispatching Problem," Operational Research Quarterly, Vol.20, pp.309-318.
Christofides, N. & J. Beasley (1984), "The Period Routing Problem," Networks, Vol.14, pp.237-256.
Clarke, G. & J. Wright (1964), "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, Vol.12, pp.568-589.
Cordeau, J., M. Gendreau, & G. Laporte (1997), "A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems," Networks, Vol.30, pp.105-119.
Desrochers, M., & T.W. Verhoog (1991), "A New Heuristic for the Fleet Size and Mix Vehicle Routing Problem," Computers & Operations Research, Vol.18, pp.263-274.
Dror, M. & M. Ball (1987), "Inventory/Routing: Reduction from an Annual to a Short-period Problem," Naval Research Logistics Quarterly, Vol.34, pp.891-905.
Dueck, G. & T. Scheuer (1990), "Threshold Accepting: a General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing," Journal of Computational Physics, Vol.90, pp.161-175.
Dueck, G.(1993), "New Optimization Heuristics: the Great Deluge Algorithm and the Record-to-Record Travel," Journal of Computational Physics, Vol.104, pp.86-92.
Eilon, S. (1977), "Management Perspectives in Physical Distribution," OMEGA, Vol.5, pp.437-462.
Feo, T. & M. Resende (1995), "Greedy Randomized Adaptive Search Procedures," Journal of Global Optimization, Vol.6, pp.109-133.
Fisher, M.(1995), "Vehicle Routing," in M. Ball, T. Magnanti, C. Monma and G. Nemhauser (eds.), Network Routing, Handbooks in Operations Research and Management Science 8, North-Holland, Amsterdam, pp.1-33.
Gaudioso, M. & G. Paletta (1992), "A Heuristic for the Periodic Vehicle Routing Problem," Transportation Science, Vol.26, pp.86-92.
Gendreau, M., A. Hertz & G. Laporte (1992), "New Insertion and Postoptimizatioin Procedures for the Traveling Salesman Problem", Operations Research, Vol.40, No.6, pp.1086-1094.
Gendreau, M., G. Laporte, C. Musaraganyi & E. Taillard (1999), "A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem," Computers & Operations Research, Vol.26, pp.1153-1173.
Gheysens, F.G., B.L. Golden & A. Assad (1984), "A Comparison of Techniques for Solving the Fleet Size and Mix Vehicle Routing Problem," Operations Research Spektrum, Vol.6, pp.207-216.
Gheysens, F.G., B.L. Golden & A. Assad (1986), "A New Heuristic for Determining Fleet Size and Composition," Mathematical Programming Studies, Vol.26, pp.233-236.
Glover, F.(1986), "Future Paths for Integer Programming and Links to Artificial Intelligence," Computers & Operations Research, Vol.13, pp.533-549.
Glover, F. (1995), Tabu Search Fundamentals and Uses, Work Report, Graduate School of Business, University of Colorado.
Glover, F. & M. Laguna (1997), Tabu Search, Kluwer Academic Publishers, Massachusetts.
Golden, B.L., A. Assad , L. Levy & F. Cheysens (1982), The Fleet Size and Mix Vehicle Routing Problem, Management Science and Statistics Working Paper No.82-020, College of Business and Management, University of Maryland, College Park, MD.
Golden, B.L., A. Assad, L. Levy & F.G. Gheysens (1984), "The Fleet Size and Mix Vehicle Routing Problem," Computers & Operations Research, Vol.11, pp.49-66.
Golden, B. & E. Wasil (1987), "Computerized Vehicle Routing in the Soft Drink Industry," Operations Research, Vol.35, pp.6-17.
Gould, J. (1969), "The Size and Composition of a Road Transport Fleet," Operations Research Quarterly, Vol.20, pp.81-92.
Gu, J. & X. Huang (1994), "Efficient Local Search With Search Space Smoothing: A Case Study of the Traveling Salesman Problem (TSP)," IEEE Transaction on Systems, Man and Cybernetics, Vol. 24, No. 5, pp.728-736, 1994.
Han, A.F. & B.C. Chang (1995), "New Heuristics for Fleet Size and Mix Vehicle Routing Problem," paper presented at INFORMS Fall''95 International Conference Meetings, New Orleans, October 29- November 1, 1995.
Han, A. & Y. Cho (1999), "A New Meta-Heuristic Approach to the Fleet Size and Mix Vehicle Routing Problem," Journal of the Eastern Asia Society for Transportation Studies, Vol.3, pp.255-270.
Han, A. & Y. Cho (1999), "Generic Intensification and Diversification Search on the Fleet Size and Mix Vehicle Routing Problem," Proceedings of the Third Metaheuristics International Conference (MIC''99), Angra dos Reis, Rio de Janeiro, Brazil, pp.269-273.
Han, A. & Y. Cho (to appear), "A GIDS Meta-heuristic Approach to the Fleet Size and Mix Vehicle Routing Problem," in C. Ribeiro, & P. Hansen (eds.), Essays and Surveys in Metaheuristics, Kluwer Academic Publishers, Massachusetts.
Henning, J.L. (2000), "SPEC CPU2000: Measuring CPU Performance in the New Millennium," Computer, July 2000, pp.28-35.
Kirby, D. (1959), "Is Your Fleet the Right Size?" Operations Research Quarterly, Vol.10, p.252.
Kirkpatrick, S., C. Gelatt (1983), & M. Vecchi, "Optimization by Simulated Annealing," Science, Vol.220, pp.671-680.
Lenstra, J. & A. Rinnooy Kan (1981), "Complexity of Vehicle Routing and Scheduling Problem," Networks, Vol.11, pp.221-227.
Lin, S.(1965), "Computer Solutions of the Traveling Salesman Problem," Bell System Technology Journal, Vol.44, pp.2245-2269.
Lin, S. & B.W. Kernighan (1973), "An Effective Heuristic Algorithm for the Traveling Salesman Problem," Operations Research, Vol.21, pp.498-516.
Liu, F., and Shen, S. (1999), "The fleet size and mix vehicle routing problem with time windows," Journal of the Operational research Society, Vol.50, pp.721-732.
Mladenovic, N. & P. Hansen (1997), "Variable Neighborhood Search," Computers & Operations Research, Vol.24, pp.1097-1100.
Or, I.(1976), Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking, Ph.D. Dissertation, Northwestern University.
Osman, I. & J. Kelly (1996), "Metaheuristics: an Overview," in I. Osman and J. Kelly (eds.), Metaheuristics: Theory and Applications, Kluwer Academic Publishers, Massachusetts, pp.1-21.
Osman, I. & S. Salhi (1996), "Local Search Strategies for the Vehicle Fleet Mix Problem," in V. Rayward-Smith, I. Osman, C. Reeves & G. Smith (eds.), Modern Heuristic Search Methods, John Wiley & Sons, New York, pp.131-153.
Rayward-Smith, V., I. Osman, C. Reeves, & G. Smith eds.(1996), Modern Heuristic Search Methods, John Wiley & Sons, New York.
Reeves, C. ed.(1993), Modern Heuristics Techniques for Combinatorial Problems, John Wiley & Sons, New York.
Rosenkrantz, D., R. Sterns, & P. Lewis (1977), "An Analysis of Several Heuristics for the Traveling Salesman Problem," SIAM Journal of Computing, Vol.6, pp.563-581.
Russell, R. & W. Igo (1979), "An Assignment Routing Problem," Networks, Vol.9, pp.1-17.
Russell, R. & D. Gribbin (1991), "A Multiphase Approach to the Period Routing Problem," Networks, Vol.21, pp.747-765.
Salhi, S. & G.K. Rand (1993), "Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem," European Journal of Operational Research, Vol.66, pp.313-330.
Tan, C. & J. Beasley (1984), "A Heuristic Algorithm for the Period Vehicle Routing Problem," OMEGA, Vol.12, pp.497-504.
Tsubakitani, S. & J. Evans (1998), "An Empirical Study of a New Metaheuristics for the Traveling Salesman Problem," European Journal of Operation Research, Vol.104, pp.113-128.
Wyatt, J.K. (1961), "Optimal Fleet Size," Operations Research Quarterly, Vol.12, pp.187-188.
劉銘韻 (1993)，(指導教授：韓復華)，週期性車輛輛路線問題啟發式解法之研究，國立交通大學土木研究所運工管組碩士論文。
張祖明 (1994)，(指導教授：韓復華)，多車種車輛輛路線問題啟發式解法之研究，國立交通大學土木研究所運工管組碩士論文。
楊智凱 (1995)，(指導教授：韓復華)，以門檻接受法改善TSP與VRP路網成本之研究，國立交通大學土木研究所運工管組碩士論文。
陳國清 (1996)，(指導教授：韓復華)，成本擾動法(NM)與兩極跳躍法(FF)在TSP問題應用之研究，國立交通大學運輸工程與管理學系畢業專題報告。
陳國清 (1998)，(指導教授：韓復華)，GDA與RRT啟發式解法在VRP問題上之應用，國立交通大學交通運輸研究所碩士論文。
韓復華、張靖 (1996)，車輛路線問題研究：SA、TA、NM、SSS與交換型啟發式解法之綜合應用分析，國立交通大學運輸工程與管理學系，八十五年度國科會專題研究計畫成果報告(NSC-85-2211-E-009-023)。
韓復華、張靖 (1997)，路線與排程問題研究：結合交換型解法與AI演算法之應用，國立交通大學運輸工程與管理學系，八十六年度國科會專題研究計畫成果報告(NSC-86-2621-E-009-001)。
韓復華、張靖 (1998)，混合型啟發式方法在多車種車輛路線問題之應用，行政院國家科學委員會委託研究報告(NSC-87-2211-E-009-024)。
韓復華(1999)，混合型AI啟發式方法在週期性車輛路線問題(PVRP)之應用，行政院國家科學委員會委託研究報告 (NSC-88-2218-E-009-036)。
韓復華、楊智凱、卓裕仁 (1997)，「應用門檻接受法求解車輛路線問題之研究」，運輸計劃季刊，第廿六卷，第二期，頁253-280。
韓復華、陳國清、卓裕仁 (1997)，「成本擾動法在TSP問題上之應用」，中華民國第二屆運輸網路研討會論文集，中央大學，頁283-292。
韓復華、盧嘉棟、卓裕仁 (1997)，「搜尋空間平滑法在TSP問題上之應用」，中華民國第二屆運輸網路研討會論文集，中央大學，頁293-302。
韓復華、卓裕仁 (1998)，「門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」，運輸學刊，第九卷，第三期，頁113-144。
韓復華、卓裕仁、陳國清 (1999)，「五種巨集啟發式方法在VRP問題上的應用與比較」，中華民國第四屆運輸網路研討會論文集，成功大學，72至82頁。
韓復華、卓裕仁 (2000)，「巨集啟發式方法在TSP與VRP上之應用：參數設定與執行機制之探討」，中華民國第五屆運輸網路研討會論文集，逢甲大學，72至82頁。