臺灣博碩士論文加值系統

物流業所追求之目標在於貨暢其流，希望在合理的時間、車輛和配送路徑上將產品有效率地送達至顧客群中。本研究探討週期性同時收送貨物之路線規劃問題，此問題為同時收送貨之車輛路徑問題(Vehicle Routing Problem with Simultaneous Pickup and Delivery，VRPSPD)的延伸問題，主要區別在於本研究增加了各個需求點的固定週期，且問題中各個需求點有不同的收貨量和送貨量。本研究將需求點分為四種情境：(1)收貨=送貨(2)收貨>送貨(3)收貨<送貨(4)部份收貨≥送貨、部份收貨≤送貨，其應用包括宅急便、牛奶(瓶)收送、家庭代工收送貨等。
本研究以桃園市某區域為例，將各需求點之收送貨週期假設為每天都需收送貨、兩天收送貨一次、三天收送貨一次，並提出新的編碼方式同時解決貨物的每天收送地點組合與收送路徑順序，再以不同組合的情境、週期、車輛數、車輛容量、目標權重，應用基因演算法(Genetic Algorithms，GA)、免疫演算法(Immune Algorithms，IA)、粒子群演算法(Particle Swarm Optimization，PSO)，來求解此問題，使六天的路徑總距離為最短(目標1)及最小化車輛間每天路徑距離的差距(目標2)。測試數值結果顯示，免疫演算法與基因演算法求解品質較為穩定，且優於粒子群演算法。

The goal of logistics is to deliver goods to customers efficiently. This thesis explored the periodic vehicle routing problem with simultaneous delivery and pickup. This problem is also an extension of the vehicle routing problem with simultaneous pickup and delivery. The main difference is that this study assumes the periodic demand quantity and receipt quantity for each point. In this thesis, we have studied four types of periodic demand quantity and receipt quantity for points, namely, (1) pickup quantity =delivery quantity for all points, (2) pickup quantity > delivery quantity for all points, (3) pickup quantity <delivery quantity for all points, (4) pickup quantity ≥ delivery quantity for some points and pickup quantity ≤ delivery quantity for some points. Applications of this considered problem include delivery service, milk (bottle) delivery and the family foundry delivery.
In this thesis, we explored an example in Taoyuan City, and we assume three types of periodic frequency: pickup and delivery once for every day, once for every two days or once for every three days. In addition, we also propose a new encoding method to solve the considered problem under various combinations including number of vehicles, vehicle capacity, weight of objective etc. In this thesis, we applied genetic algorithm (GA), immune algorithm (IA), particle swarm algorithm (PSO) to solve this problem. The numerical results show that these three algorithms can schedule the demand points and the routes effectively such that the total routing distance of six days is minimized (objective 1) and the gap of routing distance among the vehicles is minimized (objective 2). Numerical results show that immune algorithm and genetic algorithm are superior to particle swarm algorithm.

摘要...i
Abstract...ii
誌謝...iii
目錄...iv
表目錄...vi
圖目錄...ix
第一章 緒論...1
1.1研究背景與動機...1
1.2研究目的...1
1.3研究方法與步驟...2
1.4論文架構...2
第二章 文獻探討...4
2.1車輛路徑問題...4
2.2週期性車輛路徑問題...5
2.3同時收送貨之車輛路徑問題...6
2.4研究方法簡介...7
2.4.1基因演算法...7
2.4.2免疫演算法...8
2.4.3粒子群演算法...11
2.4.4田口方法...12
第三章 研究問題與方法...16
3.1研究問題...16
3.1.1問題描述...16
3.1.2問題假設...17
3.2研究方法...18
3.2.1編碼方式...18
3.2.2參數設定...22
3.2.2.1基因演算法(GA)與免疫演算(IA)法參數設定...22
3.2.2.2粒子群演算法(PSO)參數設定...24
第四章 測試結果與分析...26
4.1設備環境及參數設定...26
4.2測試問題...26
4.3測試結果...30
4.3.1測試問題一之數值結果分析(需求點=16)...30
4.3.1.1情境一(收貨=送貨)之車輛容量、車輛組合及目標權重的分析比較...30
4.3.1.2情境二(收貨>送貨)之車輛容量、車輛組合及目標權重的分析比較...31
4.3.1.3情境三(收貨<送貨)之車輛容量、車輛組合及目標權重的分析比較...31
4.3.1.4情境四(部份收貨≥送貨、部份收貨≤送貨)之車輛容量、車輛組合及目標權重的分析比較...32
4.3.2測試問題二之數值結果分析(需求點=24)...33
4.3.2.1情境一(收貨=送貨)之車輛容量、車輛組合及目標權重的分析比較...33
4.3.2.2情境二(收貨>送貨)之車輛容量、車輛組合及目標權重的分析比較...34
4.3.2.3情境三(收貨<送貨)之車輛容量、車輛組合及目標權重的分析比較...34
4.3.2.4情境四(部份收貨≥送貨、部份收貨≤送貨)之車輛容量、車輛組合及目標權重的分析比較...35
4.4統計檢定...61
第五章 結論...75
5.1結論...75
5.2未來研究方向...75
參考文獻...76
附錄一...78
附錄二...106
附錄三...134
Extended Abstract...137
簡歷...140

1.李新秋(2010)，具平衡之週期性車輛派遣問題的探討，國立虎尾科技大學工業工程與管理研究所，碩士論文。
2.李輝煌(2015)，田口方法：品質設計的原理與實務，頁1-75，高立圖書，台北。
3.周鵬程(2007)，遺傳演算法原理與應用－活用Matlab，頁3-39，全華圖書，台北。
4.林信宇(2013)，以模擬退火法求解同時收送貨之區位途程問題，台灣科技大學工業工程與管理研究所，碩士論文。
5.邱仕銘(2006)，同時收送貨車輛配送問題之研究，長榮大學經營管理研究所，碩士論文。
6.施孟慧(2013)，允許提早送貨之週期性車輛途程問題探討，雲林科技大學工業工程與管理研究所，碩士論文。
7.徐志明、陳子安、李漢宗(2011)，以基因規劃和人工免疫演算法最佳化薄型晶圓片切割參數，明新學報，37卷，2期，頁165-183。
8.涂慧敏(2004)，週期性車輛排程問題之研究，大同大學資訊經營學系(所)，碩士論文。
9.張哲維(2006)，修正禁忌搜尋法求解週期性車輛途程問題，東華大學企業管理學系，碩士論文。
10.許文軒(2015)，考量碳足跡之同時收送貨醇或途程配銷之決策支援系統，龍華科技大學大學資訊管理研究所，碩士論文。
11.許正良(2013)，應用人工智慧法於居家照顧服務排程路徑規劃問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。
12.陳國良、莊鎮泉、王東生、王煦法(2001)，遺傳算法及其應用，頁1-65，人民郵電出版社，北京。
13.渡部 義晴(2011)，田口方法的應用，頁3-20，國家教育研究院與頂冒圖書合作翻譯，台北。
14.鄞玉婷(2015)，應用人工智慧演算法於大樓的週期性資源回收之路線規劃問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。
15.劉芸希(2013)，接駁式轉運下具同時收送貨之車輛途程問題，雲林科技大學工業工程與管理研究所，碩士論文。
16.劉朝華(2014)，混合免疫智能算法理論及應用，頁1-55，電子工業出版社，北京。
17.劉選泓(2010)，二階供應鏈聯合補貨策略下週期性車輛途程問題之規劃，雲林科技大學工業工程與管理研究所，碩士論文。
18.謝騰飛(2010)，使用螞蟻演算法求解隨機需求車輛路徑問題－以販賣機補貨車為例，國立高雄第一科技大學運籌管理所，碩士論文。
19.簡銓蔚(2013)，粒子群演算法應用於具容量限制的開放式車輛途程問題，元智大學工業工程與管理研究所，碩士論文。
20.蘇朝墩(2013)，品質工程：線外方法與應用，頁74-148，前程文化，台北。
21.Christofides, N. and Beasley, J. (1984), “The Period Routing Problem.”, Networks, Vol. 14, pp. 237-256.
22.Dantzig, G. and Ramser, J. (1959), “The truck dispatching problem.”, Management science, Vol. 6, pp. 80-91.
23.Dethloff, J. (2001). “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up.” OR Spektrum, Vol. 23, pp. 79–96
24.Hemmelmayr, C., Doerner, F. and Hartl, F. (2009), “A Variable Neighborhood Search Heuristic for Period Routing Problems.”, European Journal ofOperational Research, Vol. 195, pp. 791-802.
25.Holland, J., (1975), “Adaptation in Natural and Artificial Systems”, University of Michigan Press, Ann Arbor.
26.Kennedy, T. and Eberhart, R. (1995). “A new optimizer using particle swarm theory”, Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pp. 39-43.
27.Leonard, W. and Ruth, E.(1968), “The Lockset Method of Sequential Programming Applied to Routing Delivery and Pickup Trucks.”, American Journal of Agricultural Economics, pp. 854-867.
28.Min, H. (1989),”The multiple vehicle routing problem with simultaneous delivery and pick-up points.” Transportation Research Part A: General, Vol. 23, 377-386.
29.Russell, R. and Gribbin, D. (1991), ”A Multiphase Approach to the Period Routing Problem,” Networks, Vol. 21, pp. 747-765.
30.Salhi, S. and Nagy, G. (1999), “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling.”, Journal of the Operational Research Society, Vol. 50, pp. 1034-1042.
31.Wang, H. and Chen, Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems. Computers & Industrial Engineering, pp. 84–95