臺灣博碩士論文加值系統

大部分存貨途程問題文獻在求解方面是以模擬試題方式來求解，而不是以物流業者實際案例來解決問題，且很少同時考量在同一時間做收貨與送貨。因此，本研究以一家實際的物流公司做為研究對象，來解決同時收送貨存貨途程問題。首先，我們針對途程規劃發展一個同時收送貨存貨途程數學模式，以節省法、2opt與2swap啟發式解法做為初始解，再以本研究的混合禁忌演算法找出最佳解。本研究是以文化行銷物流公司實際數據，來規劃求出各門市點的最佳運送路線、經濟訂購量、再訂購點及顧客服務水準。演算結果皆顯示本研究提出的混合免疫禁忌演算法比現行作業、節省法、2opt、2swap及禁忌搜尋法都來的好。最後，本研究也針對不同單位退貨成本、持有成本比例、單位缺貨成本、單位運輸成本及車容量做相關的敏感度分析，以提供物流業者在未來同時收送貨存貨途程規劃實務上做為決策的重要參考依據。

Most literatures of Inventory-Routing problems find the solutions by simulation, rather than solve the real case problem of logistics firms. Furthermore, few of them consider pickup and delivery problems at the same time. Therefore, this research applies a real publishing logistics firm’s operating data to study the Inventory-Routing problem with simultaneous pickup and delivery (IRPSPD). We first develop a mathematical model for this proposed Inventory-Routing problem with simultaneous pickup and delivery (IRPSPD), then apply Savings method, 2-opt heuristic methods, and 1-1 interchange method to obtain the initial feasible solution, finally implement Hybrid Immunity Tabu Search Algorithm to find the optimal solution. The numerical examples are illustrated by applying this publishing logistics firm’s real operating data to acquire the optimal delivery routes, and related economic order quantities, optimal reorder points and customer service levels of the retail stores located in those proposed routes. Furthermore, the performance of this proposed method is compared with Savings method, heuristic approach, Tabu search and current routing planning implemented by this specific logistics company. Finally, the sensitivity analysis is also conducted base on parameters including the unit cost of returning goods, inventory carrying cost percentage, unit shortage cost, unit transportation cost, and vehicle capacity; the outcomes are showed to be very promising in many aspects and helpful to this logistics company for their future planning.

摘要 i
ABSTRACT ii
誌　謝 iii
目　錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1研究動機與背景 1
1.2研究目的 3
1.3研究流程 3
1.4重要性 6
第二章 文獻探討 7
2.1文化行銷公司物流配送狀況 7
2.2車輛途程問題 9
2.3存貨途程問題 15
2.4同時收送貨之車輛途程問題 20
2.5萬用啟發式解法 25
2.5.1禁忌搜尋法(Tabu Search, TS) 25
2.5.2模擬退火法(Simulated Annealing, SA) 27
2.5.3遺傳演算法(Genetic Algorithms, GA) 29
2.5.4免疫演算法(Immune Algorithm, IA) 31
2.6.小結 33
第三章 模型建構 34
3.1問題描述 34
3.2研究限制與假設 34
3.3符號說明與定義 35
3.3.1已知變數與輔助變數 35
3.3.2決策變數 36
3.4 建構之求解數學模式 36
3.4.1限制式之說明 37
3.4.2目標函數的使用成本項目 38
第四章本研究模型求解步驟 42
4.1初始解求解說明 42
4.1.1節省法 42
4.1.2節點改善階段 43
4.2免疫演算法的演算步驟 45
4.3禁忌搜尋法的演算步驟 46
4.4主模式的演算流程 48
4.4.1初始解的演算步驟 49
4.4.2混合免疫禁忌演算法的演算步驟 50
4.4.3禁忌演算法的演算步驟 52
第五章　實例驗證與分析 54
5.1研究案例之背景描述 54
5.2參數設定 55
5.2.1目標函數參數設定 55
5.2.2演算法參數設定 56
5.3車輛途程比較分析 57
5.4同時收送貨存貨途程成本分析 58
5.4.1演算結果模擬分析 58
5.4.2演算法比較分析 59
5.5敏感度分析 60
5.5.1退貨成本比較分析 60
5.4.2持有成本比較分析 65
5.4.3缺貨成本比較分析 70
5.4.4運輸成本比較分析 75
5.4.5貨車載重分析 80
第六章 結論 85
參考文獻 88
附錄 96

1.林我聰、馬芳資、曹書銘、陳日陞，農學公司-圖書產業的協同商務，財團法人光華管理策進基金會，(2007)。
2.王朝慶，研究兩階段禁忌搜尋法於物流管理中具接駁式轉運之車輛運途問題，碩士論文，國立臺灣科技大學工業管理系碩士班，台北(2010)。
3.白健志，利用分組基因遺傳演算法解決多旅行推銷員的問題，碩士論文，南華大學資訊管理學系碩士班，嘉義(2010)。
4.王豪山，運用類免疫演算法求解都市交通貨物運輸問題，碩士論文，國立成功大學交通管理學系碩士班，台南(2009)。
5.呂志航，自動販賣機訂購量配送作業問題之研究，碩士論文，國立高雄第一科技大學運籌管理研究所，高雄(2006)。
6.吳明昌，應用兩階段模擬退火法於貨架指派問題之研究，碩士論文，元智大學工業工程與管理學系碩士班，桃園(2009)。
7.余進彬，考量權重策略下之即時性存貨途程問題，碩士論文，私立大葉大學工業工程研究所，彰化(2007)。
8.李浩瑋，以混合免疫基因演算法探討文化行銷物流公司配銷系統之途程存貨問題，碩士論文，龍華科技大學資訊管理所，桃園(2010)。
9.李洪鑫，含時間窗車輛途程問題各演算法適用範圍之探討，碩士論文，東海大學工業工程研究所，台中(2000)。
10.李盈鋒，在考量尖峰時間下之同時收送貨的車輛途程問題，碩士論文，雲林科技大學全球運籌管理研究所碩士班，雲林(2009)
11.李順斌，物流配銷系統下整合區位途程與存貨問題之研究，碩士論文，國立屏東科枝大學資訊管理研究所，屏東(2002)。
12.吳宗祐，改良型螞蟻演算法結合模擬退火法於車輛途程問題之應用，碩士論文，華梵大學資訊管理學系碩士班，台北(2007)。
13.吳鈴淳，以兩階段基因免疫演算法改良生存策略求解流程型排程問題，碩士論文，元智大學工業工程與管理學系碩士班，桃園(2008)。
14.李國村，以群蟻演算法求解動態車輛途程規劃，碩士論文，朝陽工業工程與管理研究所，台中(2006)。
15.林大為，結合模擬退火之改良粒子群演算法於結構最佳化設計的研究，碩士論文，國立中央大學，桃園(2008)。
16.林美吟，可同時收送貨物網路下車輛巡行與收送計畫的多期排程，碩士論文，國立高雄第一科技大學運輸倉儲營運所，高雄(2003)。
17.俞慧蓮，以動態排課策略因素及禁忌搜尋法求解自動排課問題，碩士論文，屏東科技大學資訊管理系所，屏東(2008)。
18.夏祖文，應用模擬退火法於限制性經費之車輛途程問題，碩士論文，華梵大學資訊管理學系碩士班，台北(2006)。
19.殷敏修，應用基因演算法求解卡車拖車途程問題，碩士論文，國立高雄第一科技大學運籌管理研究所，高雄(2007)。
20.許哲斌，在需求變動下具有軟時窗限制之同時收送貨車輛途程問題，碩士論文，雲林科技大學工業工程與管理研究所碩士班，雲林(2007)。
21.張哲旗，以混合啟發式演算法求解具模糊時窗限制車輛途程問題，碩士論文，龍華科技大學商學與管理研究所，桃園(2008)。
22.邱仕銘，同時收送貨車輛配送問題之研究，碩士論文，長榮大學經營管理研究所，台南(2006)。
23.黃玫珍，和弦搜尋演算法應用於同時收送貨之旅行推銷員問題，碩士論文，元智大學工業工程與管理學系碩士班，桃園(2009)。
24.邱美姿，應用改良式遺傳演算法於資訊系統專案排程改善之研究，碩士論文，東吳大學資訊管理學系碩士班，台北(2008)。
25.黃俊傑，應用原罪遺傳演算法於運動賽事旅行成本最小化問題，碩士論文，輔仁大學資訊管理學系碩士班，台北(2009)。
26.黃信穎，同時處理收貨與送貨業務之配送路線規劃，碩士論文，立德管理學院應用資訊研究所，台南(2005)。
27.楊明仁，模擬退火法結合禁忌搜尋法求解車輛回程途徑問題，碩士論文，華梵大學資訊管理學系碩士班，台北(2010)。
28.楊勝印，應用免疫演算法與行車操控模組於捷運系統電聯車排程最佳化之研究，碩士論文，國立高雄應用科技大學電機工程系碩士班，高雄(2006)。
29.莊志諒，配銷網路之設計研究，碩士論文，國立交通大學運輸研究所，新竹(1988)。
30.莊淑惠，以免疫演算法為基礎的兩階段法於可靠度系統最佳化問題之研究，碩士論文，虎尾科技大學工業工程與管理研究所，雲林(2007)。
31.郭益銘，使用禁忌搜尋法進行多準則網站結構重組，碩士論文，暨南國際大學資訊管理學系碩士班，南投(2009)。
32.劉選泓，二階供應鏈聯合補貨策略下週期性車輛途程問題之規劃，碩士論文，雲林科技大學工業工程與管理研究所碩士班，雲林(2010)。
33.劉曄，整合同時收送貨與選擇貨運公司服務之車輛途程問題，碩士論文，國立臺灣海洋大學航運管理學系碩士班，基隆(2004)。
34.謝君強，考量人員分區與同時收送之車輛途程問題，碩士論文，雲林科技大學工業工程與管理研究所碩士班，雲林(2010)。
35.陳志勇，物流中心配銷系統之途程存貨問題研究-以實際物流業者為例，碩士論文，國防管理學院後勤管理研究所，桃園(2007)
36.賴志豪，宅配路線規劃應用禁制搜尋法之研究，碩士論文，逢甲大學交通工程與管理學系碩士班，台中(2006)。
37.陳岸佐，週期性存貨途程問題彈性規劃模式與模式解之研究，碩士論文，屏東科技大學資訊管理所，屏東(2009)。
38.陳怡菁，考慮同時收送貨之自有車隊與委外貨運的車輛途程問題，碩士論文，雲林科技大學工業工程與管理研究所碩士班，雲林(2010)。
39.陳俊瑞，二階層供應鏈下整合定價與存貨途程問題之研究，碩士論文，屏東科技大學資訊管理所，屏東(2008)。
40.陳威甫，應用類免疫演算法於國民中學排課問題，碩士論文，國立台北教育大學資訊科學系碩士班，台北(2010)。
41.李洪鑫，含時間窗車輛途程問題各演算法適用範圍之探討，碩士論文，東海大學工業工程學系碩士班，台中(2000)。
42.蔡佩紋，應用禁忌搜尋法求解多車種多產品宅配中心之車輛途程問題，碩士論文，元智大學工業工程與管理學系碩士班，桃園(2007)。
43.楊雅惠，供應鏈網路下整合存貨管理與車輛途程設計之研究，碩士論文，國立東華大學企業管理研究所，花蓮(2004)。
44.鄭雁嬬，混合式演算法應用於同時收送貨之車輛途程問題，碩士論文，元智大學工業工程與管理學系碩士班，桃園(2008)。
45.Bard, L. H., Jaillet, P. and Dror, M. “A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities,” Transportation Science, 32, 2, 189-203(1998).
46.Bodin, L. and Golden, B.L. “Classification in vehicle routing and scheduling,” Networks, 11, 2, 97-108(1981).
47.Campbell, A., Clarke, L., Kleywegt, A., and Savelsbergh, M., “The Inventory
Routing Problem,” In T. Crainic and G. Laporte, editors, Fleet Management and
Logistics, Kluwer Academic Publishers,(1998).
48.Casco, D. O., B. L. Golden and E. A. Wasil, “Vehicle routing with backhauls: Models, algorithms, and case studies,” In: Golden, B.L., Assad, A.A. (Eds.), Vehicle Routing: Methods and Studies. Elsevier, Amsterdam, 127-147 (1988).
49.Chen, J. F., “Approaches for the vehicle routing problem with simultaneous deliveries and pickups,” Journal of the Chinese Industrial Engineers, 23(2), 141-150 (2006).
50.Chien, T. W., Balakrishnan, A. W. and Wong, R. T. “An Integrated Inventory Allocation and Vehicle Routing Problem,” Transportation Science, 23, 2, 67-76(1989).
51.Christofides, N. and Eilon, S, “An Algorithm for Vehicle Dispatching Problem, ”Operational Research Quarterly, 20(3), 309-318, (1969).
52.Clarke, G. and Wright, J. W. “Scheduling of vehicles from a Central Depot to a Number of delivery points,” Operations Research, 12, 4, 568-581(1964).
53.Cornuejols, G., Fisher, M. L. and Nemheuser, G. L, “Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms,” Management Science, Vol. 23, pp. 19-77(1977).
54.Dantzig, G.B. and Ramser, J.H. “The Truck Dispatching Problem,” Management Science, 6, 1, 80–91(1959).
55.D.T. Pham and D. Karaboga, UK, “Intelligent Optimization Techniques” Springer, (2000).
56.Du, T.C., Li, E.Y. and Chou, D. “Dynamic vehicle routing for online B2C delivery,” Omega, 33, 1, 33-45(2005).
57.Easton, K., Nemhauser, G., & Trick, M.A., The traveling tournament problem: Description & benchmarks, Principles & Practice of Constraint Programming – CP, (2001)..
58.Federgruen, A. and Zipkin, P. “A Combined Vehicle Routing and Inventory Allocation Problem,” Operations Research, 32, 5, 1019-1036(1984).
59.Fisher, M. L. and Jaikumar, R. “A Generalize Assignment Heuristic for Vehicle Routing Problems,” Networks, 11, 2, 109-124(1981).
60.Garcia, B. L., Potvin, J. Y. and Rousseau, J. M. “A parallel implementation of the tabu search heuristic for vehicle routing problem with time windows constraints,” Computers &Operations Research, 21, 9, 1025-1033 (1994).
61.Gillett, B. E. and Miller, L. R. “A heuristic algorithm for the vehicle-dispatch problem,” Operations Research, 22, 2340-349(1974).
62.Glover, F. “Tabu search: partⅠ,”ORSA Journal onComputing,1(3),190-206(1989).
63.Glover, F. “Tabu search: part II,” ORSA Journal on Computing, 2, 4-32 (1990).
64.Golden, B., Assad, A. and Dahl, R. “Analysis of a Large Scale Vehicle Routing Problem with an Inventory Component,” Large Scale System, 7, 2-3, 181-190, (1984).
65.Golden, B.L., A. Assad, L. Levy and F.G. Gheysens, “The Fleet Size and Mix Vehicle Routing Problem,” Computers& Operations Research, Vol. 11, pp.49-66 (1984).
66.Golden, B., E. Baker, J. Alfaro and J. Schaffer, “The vehicle routing problem with backhauling: two approaches,” Proceedings of the Twenty-First Annual Meeting of S.E.TIME, Myrtle Beach, 2, 90-92 (1985).
67.Ibrahim Hassan Osman, “Metastrategy simulated annealing and tabu search algorithm for the vehicle routing problem,” Annals of Operations Research, 41, pp. 421-451. (1993)。
68.Jaillet, P., Bard, J. F., Hung, L. and Dror, M. "Delivery Cost Approximations for Inventory Routing Problems in a Rolling Horizon Framework," Transportation science, 36, 3, 292-300(2002).
69.Karp, R., 1972, “Reducibility among combinatorial problems, Complexity of Computer Computations,” Plenum Press, New York, pp. 85-104.
70.Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, pp. 671-680(1983).
71.Kleywegt, A., Nori, V., and Savelsbergh, M., “The Stochastic Inventory Routing Problem with Direct Deliveries,” Transportation Science, Vol. 29, No. 3, 2002.
72.Krolak et al., “A Computational Modification to the Savings Method of Vehicle Scheduling”, Operation Research Quarterly, Vol.24. pp,281-283(1971).
73.Lin, S. “Computer solutions of the traveling salesman problem,” Bell System Technology Journal, 44, 1, 2245-2269(1965).
74.Lin, S. and Kernighan, B. “An effective heuristic algorithm for the traveling salesman problem,” Operational Research, 21, 2, 498-516 (1973).
75.Salhi, S. and G. Nagy, “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling,” Journal of the Operational Research Society, 50, 1034-1042 (1999).
76.Sakanashi, H., Suzuki, H. and Kakazu, Y. “Filtering-GA : the Evolutionary TSP landscape modifier,” Evolutionary Computation, Sapporo, 390-395(1996).
77.Savelsbergh, M. and Song, J.H. “An optimization algorithm for the inventory routing problem with continuous moves,” Computers & Operations Research, 35, 7, 2266-2282 (2008).
78.Srinivas, M. and Patnaik, L. M. “Genetic Algorithms: A Survey,” IEEE Computer, 27, 6, 17-26(1994).
79.Srivastava, R, “Alternate solution procedures for the location-routing problem”, Omega International Journal of Management Science, Vol. 21, pp. 497-506, (1993).
80.Tang, F. A. and R. D. Galvão, “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,” computer &operations research, 33, 595-619 (2006).
81.Thomas, D. J. and Griffin, P. M. “Coordinated supply chain management,” European Journal of Operational Research, 94, 1, 1-15(1996).
82.Thompson, P. M. and Psaraftis, H. “Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems,” Operations Research, 41, 5, 935-946,(1993).
83.Tuzun, D. and Burke,L. I. “A two-phase tabu search approach to the location routing problem,” European Journal of operational Research, 166, 1, 87-99 (1999).
84.Webb, M. H. J. “Cost functions in the location of depot for multiple-delivery journeys,” Operational Research Quarterly,19, 3, 311-328 (1968).
85.Willard, J.A.G.“Vehicle Routing using R-optimal Tabu Search, ”M.S. thesis, Management School, Imperial College, London(1989).
86.Zhong, Y. and M. H. Cole, ”A vehicle routing problem with backhauls and time windows: a guided local search solution,” Transportation Research, 41, 131-144 (2005).
87.http://www.taiwanservices.com.tw/台灣服務貿易商情網。
88.http://www.talm.org.tw/中華民國物流協會。
89.http://www.wds.com.tw/大智通文化行銷股份有限公司。