臺灣博碩士論文加值系統

物流中心配送成本在物流業中佔很大的成本比例，而減少成本的主要因素，就是要在合理的時間、車輛和配送路徑將產品送達到顧客手中。同時收送貨車輛途程問題擺脫了傳統車輛途程問題，在需求點拜訪一次的限制下，可以進行同時收送貨的作業。本研究的目的主要在硬式時窗限制下，針對不同車容輛的種類與單一車容量的種類的適用時機為何。本研究採用節省法輔以路線內與路線間改善法求的較優良的解，再以粒子群演算法結合模擬退火法的降溫機制去進行途程中的路徑改善，以達到最小總配送成本的目標。而本研究所提出的混合式演算法與最佳化軟體 LINGO 的比較，發現本研究所提出的混合式演算法可以有效率地提出一組優良的解。且當問題規模擴大時，混合式演算法與 LINGO的運算時間之差異程度更為顯著，而在求解的效果上，不會有太大的差異。此結果與啟發式解法比較在總成本的差異上也有平均2 % 的改善，運算時間也無太大差異。而在多車種與單一車種的研究中發現，使用多車種可以有效的降低成本，但如果要使用單一車種，則是以車容量較少的車種比車容量較多的車種表現好。因此本研究所提出的混合式演算法可以有效的求解出較佳的解，也能有效的處理實務上的需求。

Distribution cost accounts for the large percentage of total cost in logistics activities. The combination of fair time, right vehicles, and right routing can cut down the total cost and ensure the delivery to the customers. Vehicle Routing Problem with Simultaneous Delivery and Pickup (VRPSDP) is a variation of classical Vehicle Routing Problems (VRP). Under the limit of visiting once for demand points, the VRPSDP can do delivery and pickup as the same time. The purpose of this study was to adopt the Savings Method and hybrid algorithm based on Particle Swarm Optimization (PSO) and Simulated Annealing (SA) to search for the objective of minimum transportation cost. In comparison with the optimum solutions by LINGO and hybrid algorithm with the test problems, we found that hybrid algorithm had better performance in these test problems. When the problem size becomes larger, the LINGO and hybrid algorithm solution time becomes significantly different. However, the solutions of the LINGO have no significant difference with that of the hybrid algorithm approach in all test problems. The heuristic algorithm has an average of 2% improvement on the total transportation cost, but the solution time is not significant different. This study found that various car types performed better than the unique car type.

目錄
中文摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3研究範圍 3
1.4研究流程 4
第二章 文獻探討 6
2.1 物流有關概念 6
2.1.1 物流之定義 6
2.1.2 物流通路的種類 7
2.1.3 物流中心 9
2.2車輛途程問題相關文獻回顧 10
2.2.1旅行推銷員問題 10
2.2.2車輛途程問題 11
2.2.3 含回程收貨之車輛途程問題 12
2.2.4同時收送貨之車輛途程問題 13
2.2.5 具時窗限制之車輛途程問題 14
2.3車輛途程問題之求解方法 16
2.4 粒子群最佳化演算法 20
2.5模擬退火法 23
第三章 模式建立與求解流程 25
3.1模式基本假設 26
3.2 模式建立 26
3.3起始路線之建構 29
3.4可行解改善 32
3.4.1路線內交換法 32
3.4.2 路線間交換法 34
3.5 粒子群演算法混合模擬退火法降溫程序 36
3.6 研究方法 38
第四章 測試問題與結果分析討論 39
4.1 測試例題說明 40
4.2 程式介面功能說明 43
4.3例題測試 46
4.4 績效驗證準則 52
4.4.1 混合式演算法與 LINGO 軟體求解效果之績效驗證 52
4.4.2 混合式演算法與啟發解求解效果之績效驗證 59
4.5 多車種與單一車種之成本比較 70
第五章 結論與建議 ...74
5.1結論 74
5.2未來研究方向 75
參考文獻 76

附錄一 第一組模擬測試例題消費者資訊表 81
附錄二 第二組模擬測試例題消費者資訊表 82
附錄三 第三組模擬測試例題消費者資訊表 84
附錄四 第四組模擬測試例題消費者資訊表 87
附錄五 第五組模擬測試例題消費者資訊表 90
附錄六 第六組模擬測試例題消費者資訊表 92
附錄七 第七組模擬測試例題消費者資訊表 94
附錄八 第八組模擬測試例題消費者資訊表 97
附錄九 演算法模擬測試例題混合車輛途程資訊表 101
附錄十 視窗介面化之操作步驟 105

圖目錄
圖 1 - 1 傳統與現階段物流型態 1
圖 1 - 2 研究流程圖 5
圖 2 - 1 簡單物流通路 7
圖 2 - 2 多階層物流通 8
圖 2 - 3 複合物流通路 9
圖 2 - 4 旅行推銷員圖形 11
圖 2 - 5 車輛途程問題圖形 12
圖 2 - 6 含回程取貨之車輛途程問題圖形 13
圖 2 - 7 掃描法 16
圖 2 - 8 連結 17
圖 2 - 9 插入 18
圖 2 - 10 合併 18
圖 2 - 11 2-opt交換法 19
圖 2 - 12 粒子搜尋示意圖 20
圖 2 - 13 粒子群演算法基本流程圖 22
圖 2 - 14 模擬退火法流程圖 24
圖 3 - 1 節省法 30
圖 3 - 2 節省法流程圖 31
圖 3 - 3 路線內交換法流程圖 33
圖 3 - 4 1-0節點交換法 35
圖 3 - 5 1-1節點交換法 35
圖 3 - 6 粒子群演算法混合模擬退火降溫程序 37
圖 3 - 7 整體研究方法流程 38
圖 4 - 1 消費者資料格式 39
圖 4 - 2 混合式演算法應用在同時收送貨之初始畫面 43
圖 4 - 3 程式運算結果畫面 44
圖 4 - 4 車輛途程繪圖之畫面顯示 45
圖 4 - 5 第一組消費者為5之母體兩樣本t分析 53
圖 4 - 6 第二組消費者為11之母體兩樣本t分析 53
圖 4 - 7 第三組消費者為16之母體兩樣本t分析 54
圖 4 - 8 第四組消費者為23之母體兩樣本t分析 55
圖 4 - 9 第一組消費者為5之F-檢定Levene’s方法分析 56
圖 4 - 10 第二組消費者為11之F-檢定Levene’s方法分析 57
圖 4 - 11 第三組消費者為16之F-檢定Levene’s方法分析 58
圖 4 - 12 第四組消費者為23之F-檢定Levene’s方法分析 58
圖 4 - 13 第一組消費者為5之母體兩樣本t分析 60
圖 4 - 14 第二組消費者為11之母體兩樣本t分析 60
圖 4 - 15 第三組消費者為16之母體兩樣本t分析 61
圖 4 - 16 第四組消費者為23之母體兩樣本t分析 61
圖 4 - 17 第一組消費者為5之F-檢定Levene’s方法分析 63
圖 4 - 18 第二組消費者為11之F-檢定Levene’s方法分析 64
圖 4 - 19 第三組消費者為16之F-方法Levene’s方法分析 64
圖 4 - 20 第四組消費者為23之F-方法Levene’s方法分析 65
圖 4 - 21 第一組測試例題運算時間ANOVA分析 66
圖 4 - 22 第二組測試例題運算時間ANOVA分析 67
圖 4 - 23 第三組測試例題運算時間ANOVA分析 68
圖 4 - 24 第四組測試例題運算時間ANOVA分析 69













表目錄
表 1 - 1 研究範圍 3
表 4 - 1 各測試例題之基本資料 42
表 4 - 2 第一組測試例題數據 47
表 4 - 3 第一組測試例題之PSO+SA演算法分別與LINGO和啟發解之差距 47
表 4 - 4 第二組測試例題數據 48
表 4 - 5 第二組測試例題之PSO+SA演算法分別與LINGO和啟發解之差距 48
表 4 - 6 第三組測試例題數據 49
表 4 - 7 第三組測試例題之PSO+SA演算法分別與LINGO和啟發解之差距 49
表 4 - 8 第四組測試例題數據 50
表 4 - 9 第四組測試例題之PSO+SA演算法分別與LINGO和啟發解之差距 50
表 4 - 10 第五組測試例題數據 51
表 4 - 11 第五組~第八組測試例題之PSO+SA演算法與啟發解之差距 51
表 4 - 12 第一組測試例題之多種車與單一車輛比較數據 70
表 4 - 13 第二組測試例題之多種車與單一車輛比較數據 71
表 4 - 14 第三組測試例題之多種車與單一車輛比較數據 71
表 4 - 15 第四組測試例題之多種車與單一車輛比較數據 72
表 4 - 16 第五組測試例題之多種車與單一車輛比較數據 72
表 4 - 17 第六組測試例題之多種車與單一車輛比較數據 73
表 4 - 18 第七組測試例題之多種車與單一車輛比較數據 73
表 4 - 19 第八組測試例題之多種車與單一車輛比較數據 73

參考文獻
陳坤賓，「模擬退火演算法應用於車輛途程問題之研究」，元智大學工業工程研究所，碩士論文，1998。
敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學工業工程研究所，碩士論文，1999。
張福榮，「物流經營管理」，五南出版，2000。
高世昌，「考量同時送貨及收貨之多場站車輛途程問題」，逢甲大學工業工程學所碩士論文，2001。
彭冠儒「考量同時送貨及收貨之車輛途程問題」，逢甲大學工業工程學所碩士論文，2001。
莊英群，「應用禁忌搜尋法於混合收送貨之車輛途程問題」，逢甲大學工業工程學所碩士論文，2002。
羅敏華，「蟻群最佳化演算法於載重限制之車輛途程問題的研究」，元智大學工業工程研究所，碩士論文，2002。
林美吟，「可同時收送貨網路下車輛巡行與收送計畫的多期排程」，國立高雄第一科技大學運輸倉儲營運所碩士論文，2003。
黃信穎，「同時處理收貨與送貨業務之配送路線規劃」，立德管理學院應用資訊研究所碩士論文，2004。
黃小芬，「考慮有限巡距離下混合收送貨車輛途程問題」，雲林科技大學工業工程與管理研究所碩士論文，2004。
李佩玲，「以混合基因與粒子群演算法求解旅行推銷員問題」，中原大學資訊管理研究所碩士論文，2005。
張有恆，「現代物流管理」，華泰文化事業股份有限公司，2005。
朱經武、周偉禮，「以啟發式演算法求解單一場站多車種同時收送貨之車輛途程問題」，航運季刊，pp. 63-88, 2006。
曹餘偉，「應用禁忌搜尋法求解多車種多物流中心之區位途程問題」，元智大學工業工程研究所，碩士論文，2006。

邱仕銘，「同時收送貨車輛配送問題之研究」，長榮大學經營管理研究所碩士論文，2006。
莊玫珊，「PSO-SA混合搜尋法與其他結構最佳設計之應用」，中央大學土木工程研究所碩士論文，2006。
黃信翔，「解決具時窗限制的提送貨問題」，交通大學科技與管理學系碩士論文，2006。
涂家偉，「及時資訊下之收送貨巡迴路線模式」，交通大學交通運輸研究所碩士論文，2006。
紀梓民，「粒子群演算法之改善及探討」，中興大學機械工程系所碩士論文，2007。
Alshamrani, A., Mathur., K., and Ballou, R. H., “Reverse logistics :simultaneous design of delivery routes and return strategies,” Computer&Operations Research, 34(2), pp. 595-619, 2007.
Ai, The Jin, and Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,” Computers and Operations Research , 36, pp. 1693-1720, 2009.
Bodin, L. D., B. L. Golden, A. A. Assad and M. O. Ball, “Routing and Scheduling of Vehicles and Crews. The State of the Art,” Computers and Operations Research, 10(2), pp. 63-211, 1983.
Bianchessi, N., and Righini, G., “Heuristic algorithma for the vehicle routing problem with simultaneous pick-up and delivery,” Computer&Operations Research, 34(2), pp. 578-594, 2007.
Clarke, G. and Wright, W., “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operation Research, 12(4), pp. 568-581, 1964.
Casco, D.O., Golden, B.L., and Wasil, E.A., “Vehicle routing with backhauls: models, algorithms, and case studies. In: Golden, L. and Assad, A. (eds),” Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, pp.127-147. 1988.
Chen, J-F., “Approaches for the vehicle routing problem with simultaneous deliveries and pickups,” Journal of the Chinese of Industrial Engineers, 23(2), pp.141-150, 2006.
Chen, J-F., and Wu,T-H., “Vehicle routing problem with simultaneous deliveries and pickups,” Journal of the Operational research Society, 57, pp. 579-587, 2006.
Chen, P., Huang, H., and Dong, X., “An ant colony system based heuristic algorithm for the vehicle problem with simultaneous delivery and pickup,” 2007 Second IEEE Conference on Industrial Electronics and Applications, pp.136-141, 2008.
Gillett, B. E. and. Miller, L. R., “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Operations Research, 22(2), pp. 340-349, 1974.
Golden, B., A. Assad, L. Levy and F. Gheyaens, “The fleet size and mix vehicle routing problem,” Computers & Operations Research, 11(1), pp. 49-66, 1984.
Gribkovskaia, I., et. al., “General solution to the single vehicle problem with pickups and seliveries,” Computer&Operations Research, 180, pp. 568-584, 2007.
Gajpal, Y., and Abad, P. L., “Multi-ant colony system(MACS) for a vehicle routing problem with backhaul,.” European Journal of Operational Research, 196(1), 2008.
Gribkovskaia, I., Laporte, G.., and Shyshou, A., “The single vehicle routing problem with deliveries and selective pickups,” Computer & Operations Research, 35(9), pp. 2908-2924, 2008.
Hoff, A., et.al., “Lasso solution strategies for the vehicle routing problem with pickups and deliveries,” Computer&Operations Research , 192(3), pp. 755-766, 2009
Karp, R., “ Reducibility among Combinatorial Problem,”Complexity of Cpmputer Computation, Plenu, Press, pp. 85-104, 1972.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M.P.,“Optimization by Simulated Annealing,” Science, 220(4598), pp. 671-680, 1983.
Kennedy, J., and Eberhart, R.C., ”Particle Swarm Optimization,”Proc. IEEE International Conf., 4, pp. 1942-1948, 1995.
Karl, F. D., et. al., “Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows,” Computers and Operations Research , 35(9), pp. 3034-3048, 2007.
Liu, F-H., and Shen, S-Y., “A route-neighborhood-based metaheuristic for vehicle routing problem with time windows,” European Journal of Operational Research, 118, pp.485-504, 1999.

Lin, S-W., et. al., “Applying hybrid meta-heuristics for capacitated vehicle routing problem,” Expert Systems with Applications, 36(2), pp. 1505-1512, 2009.
Metropolis, N. et. al., “Equation of State Calculation by Fast Computing Machines,” Journal of Chemical Physics, 21, pp. 1087-92, 1953.
Mole, R. and S. Jameson, “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion,” Operation Research Quarterly, 27, pp. 503-511, 1976.
Min, H., “The multiple vehicle routing problem with simultaneous delivery and pick-up points,” Transportaion Research. Part A, 23(4), pp. 377-386,1989.

Potvin, J., Rousseau, J. “An exchange heuristic for routing problems with time windows,” Journal of the Operational Research Society, 46, pp. 1433-1446.1995.

Schruben, L. W. and Clifton, R. E. “The Lockset Method of Sequential Programming Applied to Routing Delivery and Pickup Trucks,” American Journal of Agricultural Economics, 50(4), pp. 854-867, 1968.
Solomon, M. M., “Algorithms for the Vehicle Routing Problem wih Time Window Constraints,” Operations Reaerch, 35(2), pp. 254-265, 1987.
Toth, P., and Vigo, D., “An exact algorithm for the vehicle routing problem with backhauls,” Transportation science, 31(4), pp 372-385, 1997.
Tang, F.A., and Galvão, R. D., “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,” Computer&Operations Research, 33(3), pp. 595-619, 2006.
Tutuncu, G..Y., Carreto, C. A .C., and Baker, B. M., “A visual interactive approach to classical and mixed vehicle routing problem,” Omega, 37(1), pp.138-154, 2009.

Wassan, N. A., Wassan, A. H. and Nagy, G., “A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries,” Journal of Combinatorial Optimization , 15(4), pp. 368-386, 2008.
Whitney, H., “Analytic extensions of function defined in closed sets,” Transactions of the American Mathmatical Society, 36, pp. 63-89, 1934.
Zachariadis, E. E., Tarantilis, C. D., and Kiranoudis, C. T., “A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service,” Expert Systems with Application, 2007.