臺灣博碩士論文加值系統

本研究針對同時收送貨的車輛途程問題加入尖峰時間的因素進行討論，當車輛遭遇尖峰時間塞車時，會提高違反顧客時間窗的機率，造成總旅運成本增加的風險。在軟時窗和車容量的限制下，討論尖峰時間塞車時考量是否繞路的車輛途程問題，求得旅運成本最小的規劃。
本研究首先建立一個考量尖峰時間會造成塞車下之同時收送貨的數學模型，接著建立禁忌演算法進行求解，探討尖峰時間考量繞路時的成本效益。隨後進行敏感度分析，來探討違反時間窗成本及距離成本對旅運成本的影響。
經過例題測試，顯示在尖峰時間造成塞車的狀況下，考量是否繞路的旅運成本優於未考量繞路的旅運成本。敏感度分析方面，收貨比例為75%、取貨比例不管為25%或50%、塞車比例50%下，當車輛遲到處罰成本大於一分鐘40元時，其考量尖峰時間是否塞車繞路所節省的成本會越來越明顯，當距離成本大於一公里25元時，考量尖峰時間是否繞路的旅運成本會趨近於未考量繞路下的旅運成本。

This study considers rush hour of Vehicle Routing Problem with Simultaneously Delivery and Pick-up with Time Window. We try to plan the vehicle routes and minimize the transportation cost in considering rush hour in VRPSDPTW.
First, we construct the mathematical programming model. Second, we construct a heuristic algorithm by Tabu Search to search for optimal cost in this problem and analyze the result. Third, we use sensitivity analysis to get important factors to know how to affect the total transportation cost.
Numerical examples indicated that we consider routes and rush hour at the same time is better than consider rush hour after routes. In sensitivity analysis, we find the greater punishment cost of time window violation, the more successful in this model. We also find when distance cost greater than 25 NT dollars per kilometer considering rush hour is similar to without considering rush hour.

摘要……………………………………………………………………………………i
ABSTRACT…………………………………………………………………………ii
致謝…………………………………………………………………………………iii
目錄…………………………………………………………………………………iv
表目錄………………………………………………………………………………vi
圖目錄………………………………………………………………………………..vii
第一章 緒論…………………………………………………………………………1
1.1研究背景與動機…………………………………………………………1
1.2研究目的…………………………………………………………………2
1.3研究範圍…………………………………………………………………2
1.4 研究流程…………………………………………………………………3
第二章 文獻探討 ……………………………………………………………………5
2.1 車輛途程問題……………………………………………………………5
2.1.1 旅行者推銷問題…………………………………………………5
2.1.2車輛途程問題……………………………………………………6
2.1.3含時窗限制的車輛途程問題……………………………………8
2.1.4含回程取貨的車輛途程問題…………………………………10
2.1.5同時收送貨的車輛途程問題……………………………………13
2.1.6 車輛途程的其它種類………………………………………16
2.2車輛途程問題相關解法……………………………………………17
2.3萬用啟發式演算法…………………………………………………19
2.3.1模擬退火法………………………………………………………20
2.3.2基因演算法……………………………………………………20
2.3.3螞蟻演算法……………………………………………………20
2.3.4禁忌搜尋法…………………………………………………….21
2.4小結……………………………………………………………………23
第三章 問題定義與數學模型……………………………………………………24
3.1問題描敘………………………………………………………………24
3.2問題假設………………………………………………………………24
3.3 數學模型……………………………………………………………32
3.4 模式驗證……………………………………………………………36
3.4.1小例題說明…………………………………………………37
3.4.2求解結果……………………………………………………38
第四章 建立啟發式演算法…………………………………………………40
4.1建構初始解階段…………………………………………………41
4.2禁忌搜尋法………………………………………………………47
4.3移步………………………………………………………………50
4.3.1本研究採取的移步類型……………………………………50
4.3.2加入考量尖峰時間是否繞路的移步…………………………54
4.4演算法完整步驟……………………………………………………55
第五章 範例測試與結果分析…………………………………………………57
5.1 參數設計…………………………………………………………57
5.1.1因子說明………………………………………………57
5.1.2實驗例題說明……………………………………………58
5.1.3實驗結果………………………………………………59
5.2演算法品質測試 ……………………………………………63
5.2.1小規模問題演算法求品質………………………………63
5.2.2比較演算法求品質………………………………………64
5.3 例題分析………………………………………………………65
5.3.1 求解例題介紹…………………………………………65
5.3.2 送貨比例為75%、收貨比例25%求解結果及分析……67
5.3.3 送貨比例為75%、收貨比例50%求解結果及分析……69
5.4敏感度分析……………………………………………………71
5.4.1違反時間窗處罰成本的敏感度分析……………………71
5.4.2 距離成本的敏感度分析…………………………………73
5.5小結……………………………………………………………75
第六章 結論與建議………………………………………………………76
6.1結論……………………………………………………………76
6.2未來研究建議…………………………………………………76
參考文獻…………………………………………………………………77

1. 王生德，「以巨集啟發式方法求解時窗限制回程取貨車輛路線問題(VRPBTW
之研究」，中華大學科技管理研究所碩士論文，2004。
2. 李洪鑫，「含時間窗車輛途程問題各演算法適用範圍之探討」。東海大學工業
工程學系碩士論文，2000。
3. 吳泰熙、張欽智，「以禁忌搜尋法則求解推銷員旅行問題」，大葉學報，第六
卷第一期，pp83-99，1995。
4. 倪佩貞，「ATMS節能減碳成效分析」，中鼎工程股份有限公司，2008。
5. 吳泰熙、陳正芳、徐俊誠，「含取貨之車輛途程問題解法之研究」，Journal of the Chinese Institute of Industrial Engineers,Vol.20,No6,pp651-665，2003
6. 陳百傑，「以啟發式演算法求解時窗限制車輛途程問題」，中原大學工業工程學系碩士論文，2002。
7. 陳惠國等編著，運輸網路分析，五南出版社，台北。
8. 陳正芳，「應用禁忌搜尋法於混合送收貨之車輛途程問題」，逢甲大學工業工程研究所碩士論文，2003。
9. 許哲斌，「在需求變動下具有軟時窗限制之同時收、送貨車輛途程問題，國立雲林科技大學工業工程與管理研究所碩士論文，2008。
10. 敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究，元智大學工業工程研究所碩士論文，1999。
11. 黃信穎，「同時處理收貨與送貨業務之配送路線規劃」，立德管理學院應用資訊研究所碩士論文，2005。
12. 韓復華、卓裕仁，「門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」，運輸學刊，第9卷，第三期 pp113-144，1996。
13. 盧柏翔，「考量混合分批送貨和取貨之車輛途程問題」，國立雲林科技大學工業工程與管理研究所碩士論文，2008。
14. 蘇文清，「軟時窗限制下探討同時正逆向物流之車輛途程問題」，國立中央大學土木工程學系研究所碩士論文，2005。
15. A. Van Breedam., “An Analysis of Effect of Local Improvement Operators in Genetic Algorithms and Simulated Annealing for the Vehicle Routing Problem” RUCA Working Paper 96/14, University of Antwerp, Belgium,1996.
16. Alfredo, F., Montane, T., Galvao R.D., “A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service”, Computers & Operations Research, Vol.33, pp. 595-619, 2006.
17. Bodin. L.,Golden, B. Assad, A. and Ball, M., “Routing and scheduling of vehicle and crews : the state of the art” , Special Issue of Computer & Operations Research, Vol. 10, No.2, pp. 63-211, 1983.
18. Dorigo, M., D.Caro, and Gambardella, L. M., “Ant Algorithms for Discrete Optimization”, Artificial Life, Vol.5, No2, pp.137-172, 1999.
19. Éric Taillard MICHEL GENDREAU., FRANCOIS GUERTIN. and JEAN-YVES POTVIN ., “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows”, TRANSPORTATION SCIENCE,Vol.31, No2 pp. 170-186,2001.
20. Fisher, M.L., Jaikumar, R., “A Generalized Assignment Heuristic for Vehicle Routing”,Networks, Vol. 11 pp.109-124, 1981.
21. Goetschalckx, M,. Jacobs-Blecha,C., “The Vehicle Routing Problem with Backhauls”, European Journal of Operational Research, Vol42, pp39-51,1989.
22. Geonwook Jeon., Herman R. Leep., and Jae Young Shim., “A vehicle routing problem solved by using a hybrid genetic algorithm”, COMPUTERS & INDUSTRIAL ENGINEERING ,Vo.l 53,Issue 4,2007.
23. Gulay Barbarosoglu., and Demet Ozgur., “A tabu search algorithm for the vehicle routing problem”, Computers and Operations Research, Volume 26 , Issue 3, pp 255 - 270 , 1999.
24. Glover, F. and Laguna, M., “Tabu Search”, Kluwer Academic Publishers, Massachusetts, 1997.
25. Holland, J. H., “Adaption in Natural and Artifical Systems”. Univerity of Michigan Pres, Ann Arbor, 1975.
26. Nicolas Jozefowiez., Fre’de’ric Semet. and El-Ghazali Talbi., “Multi-objective5vehicle routing problems”, European journal of operational research189,pp. 293-309 ,2008.
27. Osman, I.H. , "Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem", Annals of Operational Research 41,pp. 421-451, 1993.
28. Kirkpatrick, S., Gelatt. C.D. and Vecchi, J. M. P., “Optimization by Simulated Annealing”, Science, Vol. 220, pp.671-680, 1985.
29. K.C. Tan, L.H. Lee, Q.L. Zhu , & K. Ou ., “Heuristic methods for vehicle routing problem with time windows.”, Artificial intelligence in engineering , 15 (3) , 281-295, 2001.
30. Philppe. B.,Francois .G., Michel .G. and Jean-Yves .P., “A Parallel Tabu
Search ,Heuristic for the Vehicle Routing Problem with Time Windows”, Transpn
Res-C, Vol.5, No2 PP109-122, 1997.
31. Jacque .R.and Fayez F. B., “A Sweep-Based Algorithm for the Fleet Size and Mix Vehicle Routing Problem”, European Journal of Operational Research, 140 pp618-628, 2000.
32. J€org Homberger. and Hermann Gehring., “A two-phase hybrid metaheuristic for the vehiclerouting problem with time windows”, European journal of operational research, 2004.
33. S.C. Ho. And D. Haugland., “A Tabu Search Heuristic for the Vehicle Routing Problem with time Windows and Split Deliveries.Computers & Operations Reasearch,31 1947-1964, 2003.
34. Young Hae Lee.,Jung Woo Jung. And Kyong Min Lee., “Vehicle routing scheduling for cross-docking in the supply chain”,Computers & Industrial Engineering ,51 pp247-256, 2006.
35. Yuvraj Gajpal. and Parkash Abad., “An ant colony system(ACS) for vehicle routing problem with simultaneous delivery and pickup”,Computers & Operations Research, 36 pp3215-3223, 2009.