臺灣博碩士論文加值系統

多車種之車輛途程問題在理論及實務研究領域皆為十分重要之課題。本研究嘗試以遺傳演算法為基本架構，結合區域搜尋，針對文獻既有之測試案例進行測試。探討不同區域搜尋之策略，以及區域搜尋後，取代解之不同門檻值設定，與各案例之車隊配置、節點空間分佈是否有相關性。結果顯示，在車隊配置方面，並無明顯相關性；在節點空間分佈方面，求解之區域搜尋策略，與其路線成本佔總成本之比例有相關性。所佔比例以15%為一區隔，比例越高，搜尋策略越重單途程（排程）；反之，較重多途程（分群）之區域搜尋策略。門檻值的部份，當解的值偏高時，線性遞減之門檻值設定優於定值設定；反之，定值設定優於線性遞減設定。而本研究發展出四種區域搜尋方法，與文獻中的五種區域搜尋方法合併使用，結果發現，加上本研究所提出之四種區域搜尋方法之求解績效，較原有僅使用文獻中的五種區域搜尋方法所獲得之平均目標函數值改善1.19%~11.79%。在目前最佳解求解績效方面，12個測試案例中，6個案例與現有文獻之最佳解相同；2個案例比現有文獻所獲得之最佳解更佳；4個案例與文獻相近，誤差率介於0.01%~2.1%。就區域搜尋策略與門檻值設定整體而言，區域搜尋之策略以先單途程後多途程且門檻值以0.0之設定，求解績效最佳。

The Heterogeneous Fleet Vehicle Routing Problem（HVRP） is an important theoretical and practical topic in the study of routing problem. This study incorporates various local search methods and threshold values into genetic algorithm for solving a set of test instances adopted in the past studies. The performance of different local search methods and threshold values was investigated. The results showed that the single routing local search strategy perform well when the ratio between variable cost (i.e., cost of routing) and total cost gets higher. With high objective function value, the linear decreasing threshold value performs better than the fixed threshold value strategy. Moreover, the average obtained objective values can be improved 1.19% to 11.79% by adding four local search methods, which was developed in this thesis. Based on the best known solutions associated with different instances from the previous studies, the genetic local search method proposed in this study can obtain better objective function values in two instances and the same values in six instances among 12 testing instances.

目錄 ………………………………………………………………………………… Ⅰ
圖目錄 ……………………………………………………………………………… Ⅲ
表目錄 ……………………………………………………………………………… Ⅳ


第一章 緒論 ……………………………………………………………………… 1
1.1 研究背景與動機 ………………………………………………………… 1
1.2 研究目的 ………………………………………………………………… 2
1.3 研究方法 ………………………………………………………………… 2
1.4 研究內容 ………………………………………………………………… 3
1.5 研究流程 ………………………………………………………………… 3
第二章 文獻回顧 ………………………………………………………………… 5
2.1 問題定義 ………………………………………………………………… 5
2.2 數學規劃 ………………………………………………………………… 7
2.3 啟發式解法 ……………………………………………………………… 8
2.4 小結 ……………………………………………………………………… 10
第三章 方法論 …………………………………………………………………… 12
3.1 遺傳演算法 ……………………………………………………………… 12
3.2 結合區域搜尋之遺傳演算法 …………………………………………… 18
3.2.1 初始演化族群產生 ……………………………………………………… 20
3.2.2 適應函數 ………………………………………………………………… 22
3.2.3 區域搜尋 ………………………………………………………………… 22
3.2.4 改良式交配 ……………………………………………………………… 28
3.2.5 菁英主義 ………………………………………………………………… 31
第四章 實驗設計與結果 ………………………………………………………… 32
4.1 測試案例產生方式 ……………………………………………………… 32
4.2 實驗設計 ………………………………………………………………… 34
4.3 區域搜尋初步測試 ……………………………………………………… 38
4.4 小規模案例測試之結果 ………………………………………………… 42
4.5 中規模案例測試之結果 ………………………………………………… 45
4.6 大規模案例測試之結果 ………………………………………………… 47
4.7 總體結果 ………………………………………………………………… 49
4.8 小結 ……………………………………………………………………… 53
第五章 結論與建議 ……………………………………………………………… 55
5.1 測試結果之結論 ………………………………………………………… 55
5.2 研究後之建議 …………………………………………………………… 57
5.3 後續研究 ………………………………………………………………… 57
參考文獻……………………………………………………………………………… 58
附錄 本研究各測試案例之最佳解 …………………………………………… 61

1.劉祐興、周榮昌、王正傑，「運用遺傳演算法求解機率旅行推銷員問題」，物流產業電子化學術與實務研討會 （2004a）.
2.劉祐興、周榮昌、馬凱賢，「機率旅行推銷員問題」，收錄於「運籌管理：二十一世紀新經營典範」 （2004b）.
3.Baker, B. M. and Ayechew, M. A., “A Genetic Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 30, pp. 787-800, （2003）.
4.Cheng, V.H.L., Crawford, L.S. and Menon, P.K., “Air Traffic Control Using Genetic Search Techniques,” IEEE International Conference on Control Applications, Vol. 1, pp. 249-254, （1999）.
5.Choi, E. and Tcha, D.-W., “A Column Generation Approach to the Heterogeneous Fleet Vehicle Routing Problem,” Computers & Operations Research, Vol. 34, Issue 7, pp. 2080-2095, （2007）.
6.Croes, G., “A Method for Sovling Traveling Salesman Problems,” Operations Research, Vol. 6, pp. 791-812, （1958）.
7.Dullaert, W., Janssens, G. K., Sorensen, K. and Vernimmen, B., “New Heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows,” Journal of the operational research society, Vol. 53, pp. 1232-1238, （2002）.
8.Gendreau, M., Laporte, G., Musaraganyi, C. and Taillard, É. D., “A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem,” Computers & Operations Research, Vol. 26, pp. 1153-1173, （1999）.
9.Gillett, B.E. and Miller, L.R., “A Heuristic Algorithm for the Vehicle dispatch Problem,” Operations Research, Vol. 22, pp. 240-349, （1974）.
10.Golden, B., Assad, A., Levy, L. and Gheysens, F., “The Fleet Size and Mix Vehicle Routing Problem,” Computers & Operations Research, Vol. 11, No. 1, pp. 49-66, （1984）.
11.Ho, S. C. and Haungland, D., “A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries,” Computers & Operations Research, Vol. 31, pp. 1947-1964, （2004）.
12.Holland, J.H., “Adaptation in Natural and Artificial System,” University of Michigan Press, Ann Arbor, MI. （1975）.
13.Krasnogor, N. and Smith, J., “A Memetic Algorithm with Self-adaptive Local Search: TSP as A Case Study,” Genetic and Evolutionary Computation Conference, pp. 987-994, （2000）, （GECCO-2000）.
14.Laporte, G., Gendreau, M., Potvin, J.-Y. and Semet, F., “Classical and Modern Heuristic for the Vehicle Routing Problem,” International Transactions in Operation Research, Vol. 7, pp. 285-300, （2000）.
15.Lima, C. M. R. R., Goldbarg, M. C. and Goldbarg, E. F. G., “A Memetic Algorithm for Heterogeneous Fleet Vehicle Routing Problem,” Electronic Notes in Discrete Mathematics, Vol. 18, pp. 171-176, （2004）.
16.Liu, Y.-H., “A Hybrid Scatter Search for the Probabilistic Traveling Salesman Problem,” Computers & Operations Research, Vol. 34, pp. 2949-2963, （2007）.
17.Liu, Y.-H. and Mahmassani H. S., “Global Maximum Likelihood Estimation Procedures for Multinomial Probit（MNP）Model Parameters,” Transportation Research B, Vol. 34B, No. 5, pp. 419-449, （2000）.
18.Mazzeo, S. and Loiseau, I., “A Ant Colony Algorithm for the Capacitated Vehicle Routing,” Electronic Notes in Discrete Mathematics, Vol. 18, pp. 181-186, （2004）.
19.McKinney, D.C. and Lin, M.D., “Genetic Algorithm Solution of Groundwater Management Models,” Water Resources Research, Vol. 30, No. 6, pp. 1897-1906, （1994）.
20.Moscato, P., “On Evolution, Search, Optimization, Genetic Algorithm and Martial Arts: towards Memetic Algorithm,” Technical Report Caltech Concurrent Computation Program, Report. 826, California Institute of Technology, Pasadena, California, USA, （1989）.
21.Ochi, L. S., Vianna, D. S., Drummond, L. M. A. and Victor, A. O., “A Parallel Evolutionary Algorithm for the Vehicle Routing Problem with Heterogeneous Fleet,” Future Generation Computer Systems, Vol. 14, pp. 285-292, （1998）.
22.Potvin, J.-Y., “Genetic Algorithm for the Traveling Salesman Problem,” Annals of Operations Research, Vol. 63, pp. 339-370, （1996）.
23.Prins, C., “A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 31, pp. 1985-2002, （2004）.
24.Renaud, J. and Boctor, F. F., “A Sweep-based Algorithm for the Fleet Size and Mix vehicle Routing Problem,” European Journal of Operational Research, Vol. 140, pp. 618-628, （2000）.
25.Rodríguez, M. A. and Jarur, M. C., “A Genetic Algorithm for Searching Spatial Configurations,” IEEE Transactions on Evolutionary Computation, Vol. 9, NO. 3, pp. 252-270, （2005）.
26.Taillard, É. D., “A Heuristic Column Generation Method for the Heterogeneous Fleet VRP,”RAIRO, Vol. 33, pp. 1-14, （1999）.
27.Tarantilis, C. D., Kiranoudis, C. T. and Vassiliadis, V. S., “A Threshold Accepting Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem,” European Journal of Operational Research, Vol. 152, pp. 148-158, （2004）.
28.Tarantilis, C. D., Kiranoudis, C. T. and Vassiliadis, V. S., “A List Based Threshold Accepting Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem,” Journal of the Operational Research Society, Vol. 54, pp. 65-71, （2003）.
29.Valenzuela, J. and Smith, A. E., “A Seeded Memetic Algorithm for Large Unit Commitment Problems,” Journal of Heuristics, Vol. 8, pp. 173-195, （2002）.
30.Waters, C.D.J., “A Solution Procedure for the Vehicle Scheduling Problem Based on Iterative Route Improvement,” Journal Operational Research Society, Vol. 38, pp. 833-839, （1987）.
31.Wren, A. and Holliday, A., “Computer Scheduling of Vehicle from One or More Depots to A Number of Delivery Points,” Operational Research Quarterly, Vol. 23, pp. 333-344, （1972）.
32.Yan, S. and Luo, S.-C., “Probabilistic Local Search Algorithm for Concave Cost Transportation Network Problems,” European Journal of Operational Research, Vol. 117, pp. 511-521, （1999）.