臺灣博碩士論文加值系統

車輛途程問題在過去30年來已經被廣泛討論，而且變化形式非常多，本研究將焦點放在時窗限制下多車種車輛途程問題。這是因為由不同車種組成的車隊往往能獲得較單一車種為佳的解，而且現在是一顧客導向的時代，顧客會要求配送車輛於某特定時間來進行服務，因此加入顧客服務時窗可以提高顧客的滿意程度。
車輛途程問題是一NP-hard問題，不易求得精確解，大部分都是利用啟發式解法來求解，但其缺點是易陷入區域最佳解。為了避免此一情況發生，本研究將利用具有隨機與多點搜尋特性的遺傳演算法來求解車輛途程問題。然而傳統的遺傳演算法並沒有處理限制條件的能力，以致於在問題的解空間做全面、隨機性的搜尋，結果很容易產生不合理的子代，只能利用人為的機制如懲罰函數法來做事後的補救工作，這種方式顯得沒有效率，針對此點本研究在進行遺傳演算時將同步考慮問題的限制條件，合理規劃搜尋的方向避免做無謂的搜尋，以提升求解的效率，並在最後以一測試題目利用統計假設檢定方法來比較限制條件下遺傳演算運作模式(採用互換交配運算子)與傳統的遺傳演算運作模式(採用單點交配運算子與雙點交配運算子) 之優劣。

The vehicle problems have been discussed for thirty years. In this work we address the problem of the fleet size and mix vehicle routing problem with time windows. Typically, researchers assume that all vehicles are identical. In this work, we relax the homogeneous fleet assumption and add the time window constraints to satisfy the time requirement of each customer.
The vehicle problems are NP-hard problems. Most approaches for solving the vehicle problems are heuristics which are easy to find the local optimal solution. In this research, the genetic algorithm is used to avoid finding the local optimal solution. However, the traditional genetic algorithm is unable to handle the constraints of problems. According to the characteristic of the genetic algorithm, we propose a new genetic algorithm to use the constraints to guide the searching of the solution to the problem and increase the efficiency of the problem solving. At last, we use a test problem to compare the new genetic algorithm with traditional genetic algorithm in terms of the statistical hypothesis test.

目錄
中文摘要i
英文摘要ii
誌謝iii
目錄iv
表目錄vi
圖目錄vii
第一章 緒論1
1.1 研究背景與動機1
1.2 研究目的3
1.3 研究範圍5
1.4 研究方法6
1.5 研究架構6
第二章 文獻探討9
2.1 多車種車輛途程問題之相關文獻探討12
2.1.1 以節省法（saving algorithm）為基礎13
2.1.2 以一般指派法（generalized assignment）為基礎13
2.1.3 以權重配對節省法（matching based saving heuristic）為基礎13
2.1.4 途程擾亂法則14
2.2 遺傳演算法簡介14
2.2.1 遺傳演算法的主要特性16
2.2.2 常用的交配運算子簡介16
2.2.3 複製19
2.2.4 突變運算子20
第三章 限制條件下遺傳演算法運作模式21
3.1 依顧客地理位置分群24
3.1.1 競爭式學習25
3.1.2 等大小區域建構28
3.1.3 分群區域演算法30
3.2 限制條件下遺傳演算法運作模式36
3.2.1 編碼37
3.2.2 產生原始族群39
3.2.3 適應性函數之設計41
3.2.4 交配運算43
3.2.5 複製47
3.2.6範例演練48
第四章 範例測試63
4.1 範例產生63
4.2 測試結果64
4.3 模式比較79
4.3.1 結果分析81
第五章 結論與未來研究方向88
5.1 結論88
5.2 未來研究方向89
參考文獻91
附錄一 顧客位置座標表95
附錄二 顧客需求表96
附錄三 顧客服務時間表97
簡歷98
表目錄
表2-1 多車種車輛途程文獻12
表3-1 18位顧客位置資料表30
表3-2 經一學習循環後樣本對各群中心之距離與分群結果35
表3-3 路線編碼表示方式38
表3-4 顧客服務時窗表39
表3-5 分群c第零代路線表47
表3-6 分群c第一代路線線表47
表3-7 分群c產生第二代路線解的母體路線表48
表4-1 第一次學習循環前10次輸入表65
表4-2 第一次學習循環前10次各分群區域權值向量變化表66
表4-3 第一次學習循環結果輸出表67
表4-4 最大分群區域半徑變化表67
表4-5 分群區域演算最後結果輸出表68
表4-6 群一30次演算結果表69
表4-7 群二30次演算結果表72
表4-8 群三30次演算結果表76
表4-9 互換交配運算子運作結果81
表4-10 單點交配運算子運作結果84
表4-11 雙點交配運算子運作結果84
表4-12 單點交配運算子運作結果81
表4-13 雙點交配運算子運作結果82
表4-14 單點交配運算子運作結果86
表4-15 雙點交配運算子運作結果86
圖目錄
圖1-1 車輛途程問題解空間示意圖5
圖1-2 研究架構8
圖2-1 時窗限制車輛途程問題之沿革10
圖2-2 單點交配前之個體17
圖2-3 單點交配後之個體17
圖2-4 雙點交配前之個體18
圖2-5 雙點交配後之個體18
圖2-6 N點交配前之個體19
圖2-7 N點交配後之個體19
圖2-8單點突變過程示意圖20
圖3-1 傳統遺傳演算法搜尋過程示意圖21
圖3-2 解空間切割示意圖22
圖3-3 路線相鄰顧客距離遙遠示意圖23
圖3-4 兩染色體距離遙遠示意圖23
圖3-5 求解系統架構圖24
圖3-6 競爭式學習網路圖26
圖3-7 本研究適用之競爭式學習網路圖27
圖3-8 等大小分群區域結果示意圖28
圖3-9 理想分群結果示意圖29
圖3-10 本研究遺傳演算法運作流程圖36
圖3-11 原始族群(初始解)產生運作流程圖41
圖3-12 互換交配運算子運作流程圖44
圖3-13 互換交配運算子兩路線顧客關係示意圖45
圖3-14 複製運作流程圖48

參考文獻
[1] 工研院機械所，物流中心生產力評估指標，經濟部商業司，台北，1994。
[2] 吳信儀，「以改良之進化策略演算法解決排序問題之研究---SRS演算法與多重工作者系統之發展」，碩士論 文，東海大學工業工程研究所，1994。
[3] 杜世文，「多目標與模糊時窗貨物配送啟發式解法之研究」，碩士論文，交通大學交通運輸研究所，1992 。
[4] 杜志挺、賀嘉生、吳政龍，「應用具有禁步限制條件的遺傳演算法則於車輛途程問題」，中國工業工程年 會八十七年度年會論文集，彰化，476-504，1998。
[5] 林信成、彭啟峰，Oh ! Fuzzy 模糊理論分析，第三波，台北，1994。
[6] 林建良，「應用神經網路與模糊理論之工件分群」，碩士論文，雲林科技大學工業管理研究所，1995。
[7] 郭人介、郭幸民、蘇鈺玲，「物流中心車輛問題規劃之研究」，中國工業工程年會八十七年度年會論文集 ，彰化，510-515，1998。
[8] 曾國雄、王日昌、黃明居，「以基因演算法與樣版路徑求解旅行推銷員問題」，運輸計畫季刊，第二十五卷，第三期，493-516，1996。
[9] 黃木才，「貨櫃運輸公司車輛排程問題之研究-模糊多目標遺傳演算法之應用」，碩士論文，交通大學交 通 運輸研究所，1996。
[10] 詹弘康、張光華、張添盛，「多重迴圈物流配送路徑之啟發式規劃方法」，中國工業工程年會八十四年度 年會論文集，桃園，1995。
[11] 廖忠雄、黃敏亮、王淑娟、陳煌儒、王銘宗，「物流中心之模糊多目標與混合型時窗限制配送車輛途程問 題之研究」，中國工業工程年會八十七年度年會論文集，彰化，476-504，1998。
[12] 鄭博王，「以遺傳演算法及類神經網路應用於旅行推銷員問題」，碩士論文，淡江大學土木工程研究所， 1995。
[13] 謝芬玲、賀力行、郭維凌，「不同負載車輛途程問題之探討」，中國工業工程年會八十七年度會論文集 ， 彰化，376-571，1998。
[14] 蘇木春、張孝德，機器學習類神經網路、模糊系統以及基因遺傳演算法則，全華，台北，1997。
[15] Alsbury, P., "The Vehicle Fleet Mix", International Journal of Physical Distribution, Vol. 3, pp123-125, 1972.
[16] Bodin, L. D., "Twenty Years of Routing and Scheduling". Operations Research, Vol. 38, pp571-579, 1990.
[17] Derochers, M. and T. W. Verhoog, "A New Heuristic or the Fleet Size and Mix Vehicle Routing Problem", Computers Ops. Res, Vol. 3, pp263-274, 1991.
[18] Doll, L. C., "A Quick and Dirty Vehicle Routing Procedure", Interfaces, Vol. 1, pp84-85, 1980.
[19] Eilon, S., "Management Perspectives in Physical Distribution", OMEGA, Vol. 5, pp437-462, 1977.
[20] Etezadi, T. and J. E. Beasley, "Vehicle Fleet Composition", J. Opl. Res. Soc, Vol. 34, pp87-91, 1983.
[21] Ferland, J. A. and P. Michelon, "The Vehicle Scheduling Problem with Multiple Vehicle Types", J. Opl. Res. Soc, Vol. 6, pp577-583, 1988.
[22] Fisher, L. M., K. O. Jornsten and O. B. G. Madsen, "Vehicle Routing with Time Windows: Two Optimization Algorithm", Operations Research, Vol. 45, pp488-492, 1997.
[23] Gheysens, F. G., B. Golden and A. Assad, "A Heuristic for Determining Fleet Size and Composition", Mathematical Programming Studies, Vol. 26, pp233-236, 1986.
[24] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Wesley Publishing Co., 1989.
[25] Golden, B., A. Assad, L. Levy and F. Ghysens, "The Fleet Size and Mix Vehicle Routing Problem", Computers Ops. Res, Vol. 1, pp49-66, 1994.
[26] Gould, J., "The Size and Composition of a Road Transport Fleet", Operations Research Quarterly, Vol. 20, pp81-92, 1969.
[27] Kirby, D., "Is Your Fleet the Right Size", Operations Research Quarterly, Vol. 10, pp252, 1959.
[28] Laporte, G., "The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms", European Journal of Operational Research, Vol. 59, pp345-358, 1992.
[29] Michalewicz, Z., Genetic Algorithm + Data Structures = Evolution Programs, Springer Verg-Berlin Heidelberg, 1994.
[30] Mole, R. H., "Dynamic Optimization of Vehicle Fleet Size", Operations Research Quarterly, Vol. 26, pp25-34, 1975.
[31] Parikh, S. C., "On a Fleet Sizing Problem and Allocation Problem", Management Sciences, Vol. 23, pp972-977, 1977.
[32] Pellazar, M. B., "Vehicle Route Planning with Constraints Using Genetic Algorithms", IEEE Proceedings of the National Aerospace and Electronics Conference, pp111-118, 1991.
[33] Salhi, S. and M. Sari, "A Multi-Level Composite heuristic for the Multi Depot Vehicle Fleet Mix Problem", European Journal of Operational Research, Vol. 103, pp95-112, 1997.
[34] Salhi, S. K. and R. Graham, "Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem", European Journal of Operational Research, Vol. 66, pp313-330, 1993.
[35] Salhi, S., M. Sari, D. Saidi and N. Touati, "Adaption of Some Vehicle Fleet Mix Heuristics", OMEGA Int. J. of Mgmt. Sci., Vol. 20, pp653-660, 1992.
[36] Su, C. T., "The Design of Vehicle Routing and Scheduling of Physical Distribution", Automation, Taichung, pp221-228, 1997.
[37] Thangiah, S. R., K. E. Nygard and P. L. Juell, "GIDEN: A Genetic Algorithm System for Vehicle Routing with Time Windows", Proc. of the 8th IEEE Conf. on Artificial Intelligence Applications, Monterey, California, pp240-246, 1991.
[38] Uchimura, K. and H. Sakaguchi, "Vehicle Routing Problem using Genetic Algorithms Based on Adjacency Relations", Vehicle Navigation and Information Systems Conference (VNIS) IEEE, pp214-217, 1995.
[39] Waters, C. D. J., "Expert System for Vehicle Scheduling", J. Opl. Res. Soc. Vol. 6, pp505-515, 1990.
[40] Woods, D. G. and F. C. Harris, "Truck Fleet Size Composition for Concrete Distribution", International Journal of Physical Distribution, Vol. 10, pp187-188, 1979.
[41] Wyatt, J. K., "Optimal Fleet Size", Operations Research Quarterly, Vol. 12, pp187-188, 1961.