臺灣博碩士論文加值系統

供應商庫存管理(VMI)是由供應商來管理顧客的存貨補充作業，而存貨途程問題(IRP)是實行供應商庫存管理系統時的關鍵問題。存貨途程問題中供應商必須作三項重要的決策：(1)何時需要對顧客補貨？(2)每次需補充多少的數量？(3)配送的途程為何？存貨途程問題就是要協調最好的存貨補充與車輛途程情況。因為必須解決的三個子問題彼此是相互影響的，使整個問題要考慮的情況相當複雜。自動販賣機的補貨與配送問題就是存貨途程問題的一個例子。
本研究中考慮在一服務範圍內自動販賣機M天的補貨作業，各機台在規劃期間內可被服務多次，但每天最多只能被服務一次，並且依據各機台對產品的平均需求率來決定其可選擇的服務日期形態。在車容量與各機台儲存容量有限的情況下，使規劃期間內存貨成本、缺貨成本、運輸成本之總成本最低。在本研究中考慮了三個子問題：(1)指派服務日期形態，(2)車輛途程問題，(3)各產品裝載數量問題。前兩個子問題是屬於週期性車輛途程問題(PVRP)。因為存貨途程問題為NP-Hard問題，要求得最佳解必須要花費很長的時間，因此本研究應用模擬退火法(SA)在可接受的時間內來得到其近似解最佳解。第一階段指派各顧客被服務的日期，第二階段分別求解每天的車輛途程與各產品裝載數量，而各階段彼此間是會相互影響的。
以本研究的模式對某自動販賣機業者2002年六、七月份的補貨資料來改善補貨作業，與現行補貨作業方案比較，改善後的補貨作業總成本較低，每週總成本最多可節省了1326.51元(22.41%)。依據各機台各產品需求分配對改善前後的補貨作業進行模擬，結果顯示改善後的補貨作業每週總成本最多能節省20.77%。對單位距離運輸成本、存貨持有成本率和缺貨持有成本率進行敏感度分析，發現當單位距離運輸成本增加，整個模式趨近於求解PVRP問題；持有成本率愈高裝載數量愈少；缺貨成本率愈高裝載數量愈多。

Vendor managed inventory (VMI) refers to a situation in which a supplier manages the inventory replenishment of its customers. The core problem when we implement the VMI is the inventory routing problem (IRP). Three decisions have to be made for IRP: 1) when to serve a customer? 2) how much to deliver to a customer when it is served? and 3) which delivery routes to use? IRP addresses the coordination of inventory replenishment and vehicle routing decisions and is a very complex problem because the solutions of the three sub-problems are interrelated. The replenishment and delivery problem for vending machine is an example of IRP.
In this research we consider a service region that a driver delivers products during a given M-day period. The vending machines are typically required to be visited once or several times over the period, and once a day at the most. The days of visits must follow one of the allowable visit-day patterns that were built based on stationary-interval inventory property. The objective of the problem is to minimize the system-wide cost consisting of inventory, stockout and transportation costs subject to the vehicle capacity and vending machine capacities constraints. Three sub-problems are considered in this research: 1) visit-day pattern assignment, 2) vehicle routing problem, and 3) product loading problem. The first two sub-problems can be treated as period vehicle routing problem (PVRP). Since IRP is an NP-hard optimization problem, an exact solution approach would most likely be very time-consuming. We propose a simulated annealing (SA) heuristic solves the IRP in a reasonable time and produces high-quality solutions. We start by assigning an allowable day combination to each customer and then solve a classical VRP for each day of the M-day period. Of course, the two phases of this type of solution approach will interact with each other.
The overall scheme was tested on data sets collected from a local soft drink vending machine distributor. Two months data, June and July of 2002, are analyzed by comparing the proposed heuristic against the current delivery pattern. The results show that our heuristic provides better system-wide cost. The new delivery plan can save the total cost up to NT$1326.51/week (22.41%). Based on the collected data, a simulation model is also developed to mimic the demand distribution of each product for each vending machine. The proposed heuristic shows its robustness on the simulation results with cost saving by up to 20.77%.

目 錄
目 錄 i
表 目 錄 iii
圖 目 錄 iv
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 4
1.4 研究範圍 4
1.5 研究架構與流程 5
第二章 文獻探討 7
2.1 車輛途程問題 7
2.1.1 傳統車輛途程問題定義與求解方法 7
2.1.2 週期性車輛途程問題定義與求解方法 11
2.2 供應商庫存管理 14
2.3 存貨途程問題 17
2.4 模擬退火法 20
2.5 小結 21
第三章 模式建立 22
3.1 配送點已知下單一產品之最佳裝載數量 22
3.1.1 問題描述 22
3.1.2 模式建構 23
3.2 配送點已知下多產品之最佳裝載數量 25
3.2.1 問題描述 25
3.2.2 模式建構 25
3.3 需求不確定下存貨途程問題 31
3.3.1 問題描述 31
3.3.2 問題假設與限制 32
3.3.3 模式建構 33
3.3.4 求解流程 36
第四章 實例測試 45
4.1 六月份補貨作業之改善 45
4.2 七月份補貨作業之改善 52
4.3 以六月前三週需求估計六月第四週之補貨作業 57
4.4 模擬補貨作業 58
4.5 敏感度分析 59
4.5.1 對單位距離運輸成本進行敏感度分析 59
4.5.2 對存貨持有成本率進行敏感度分析 61
4.5.3 對缺貨成本率進行敏感度分析 62
4.5.4 小結 63
第五章 結論與未來研究方向 65
5.1 結論 65
5.2 未來研究方向 66
參考文獻 68
表 目 錄
表1-1 2002年日本自動販賣機數量與年銷售金額統計 5
表2-1 PVRP啟發式解法彙整表 13
表2-1 PVRP啟發式解法彙整表(續) 14
表3-1 模擬退火法求解途程問題參數分析 44
表4-1 六月現行補貨作業一週內每天配送的機台集合 46
表4-2 六月現行每天配送順序 46
表4-3 六月現行每週補貨作業平均成本 47
表4-4 補貨日期形態 48
表4-5 補貨週期適用的補貨日期形態 48
表4-6 不同參數設定下對六月份補貨作業進行規劃 49
表4-7 模式求解六月份一週補貨作業總成本 50
表4-8 模式求解六月補貨作業一週內每天配送的機台集合 50
表4-9 模式求解六月一週內每天配送順序 50
表4-10 七月現行補貨作業一週內每天配送的機台集合 52
表4-11 七月現行每天配送順序 52
表4-12 七月現行每週補貨作業平均成本 53
表4-13 不同參數設定下對七月份補貨作業進行規劃 53
表4-14 模式求解七月補貨作業一週內每天配送的機台集合 54
表4-15 模式求解七月一週內每天配送順序 54
表4-16 模式求解七月份一週補貨作業總成本 55
表4-17 不同裝載數量成長率在六月第四週之裝載成本 58
表4-18 模擬補貨作業每週平均成本 59
表4-19 在不同單位運輸成本設定下進行規劃之結果 60
表4-20在不同存貨持有成本率設定下進行規劃之結果 61
表4-21在不同缺貨成本率設定下進行規劃之結果 62
圖 目 錄
圖1-1 日本歷年自動販賣機數量與年銷售金額 2
圖1-2 現行自動販賣機補貨作業 3
圖1-3 研究流程 6
圖2-1 分解主問題與其巡迴子問題間之關係圖 10
圖2-2 VMI作業流程 15
圖2-3 VMI的關鍵成功因素 16
圖3-1 單一產品裝載數量與總成本之關係 24
圖3-2 以窮舉法計算各產品裝載數量與總成本之關係 28
圖3-3 多產品總裝載數量超過最大車容量時之調整策略 30
圖3-4 自動販賣機業者服務區劃分示意圖 31
圖3-5 自動販賣機業者補貨作業之規劃 32
圖3-6 需求不確定下存貨途程問題求解流程 37
圖3-7 隨機產生起始解之流程圖 39
圖3-8 以模擬退火法求解途程問題之程序 42
圖4-1 六月份改善前後每週路線圖(a)改善前(b)改善後 51
圖4-2 七月份改善前後每週路線圖(a)改善前(b)改善後 56
圖4-3 六月各週營業額 58
圖4-4 單位距離運輸成本與各項成本之關係 60
圖4-5 單位距離運輸成本與行駛距離之關係 61
圖4-6 存貨持有成本率與各項成本之關係 62
圖4-7 存貨持有成本率與裝載數量之關係 62
圖4-8 缺貨成本率與各項成本之關係 63
圖4-9 缺貨成本率與裝載數量之關係 63

1. 日本自動販賣機工業會，「自販機普及台數與年度自販金額」，http://www.jvma.or.jp/infoma/info_data01.html，2002
2. 王保元，「物流中心冷凍食品配送模式之研究」，碩士論文，朝陽大學工業工程與管理研究所，民國89年。
3. 台灣QR/ECR推動委員會，「VMI能為企業在補貨流程上創造哪些效益」，http://www.ec.org.tw/organize/qrecr/faq_main.asp?cid=205，民國88年。
4. 林志鴻，陳春益，曹以明，「汽車運送業拖車途程問題之研究」，運輸計劃季刊，第31卷，第一期，民國91年3月，pp.171-206。
5. 卓裕仁，「以巨集啟發式方法求解多車種與週期性車輛路線問題之研究」，博士論文，交通大學運輸工程與管理研究所，民國90年。
6. 洪銘佐，「單一配銷中心裝載車容量之規劃」，碩士論文，雲林科技大學工業工業工程與管理研究所，民國90年。
7. 經濟部商業司，「商業快速回應(QR/ECR)技術手冊」，民國87年。
8. 張志鴻，「無線電自動販賣機商品配送作業之研究」，碩士論文，中華大學科技管理研究所，民國91年。
9. 鄭聰穎，「供應鏈長鞭效應因應政策之研究」，碩士論文，台北科技大學生產系統工程與管理研究所，民國89年。
10. 韓復華，卓裕仁，「包容性深廣度搜尋法在週期性車輛路線問題之應用」，運輸計劃季刊，第31卷，第一期，民國91年3月，pp.1-36。
11. 蘇昭銘，張志鴻，「無線電自動販賣機商品配送系統之研究」，會議論文，中國工業工程師學會學術研討會，民國90年。
12. 蘇雄義譯，供應鏈之設計與管理─觀念、策略、個案，麥格羅．希爾，台北，2001。
13. Angelelli, E., and Speranza, G., “The Periodic Vehicle Routing Problem With Intermediate Facilities,” European Journal of Operational Research, Vol. 137, pp. 233-247, 2002.
14. Bard, L. H., Jaillet, P., and Dror, M., “A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities,” Transportation Science, Vol. 32, pp. 189-203, 1998.
15. Beltrami, E., and Boldin, L., “Networks and Vehicle Routing for Municipal Waste Collection,” Networks, Vol. 4, pp. 65-94, 1974.
16. Bodin, L., and Golden, B., “Classification In Vehicle Routing And Scheduling,” Networks, Vol. 11, pp. 97-108, 1981.
17. Bolte, A., and Thonemann, U. W., “Optimizing Simulated Annealing Schedules with Genetic Programming,” European Journal of Operational Research, Vol. 92, pp. 402-416, 1996.
18. Burns, L. D., Hall, R. W., D. E. Blumenfeld and C. F. Daganzo, “Distribution Strategies That Minimize Transportation and Inventory Costs,” Operations Research, Vol. 33, No. 3, pp. 469-490, 1985.
19. Buzzell, R., and Ortmeyer, G., “Channel Partnerships Streamline Distribution,” Sloan Management Review, Vol. 36, pp. 85-96, 1995.
20. 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.
21. Campbell, A., Clarke, L., and Savelsbergh, M., “An Inventory Routing Problem,” 1999.
22. Cerny, V., “Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm,” Journal of Optimization Theory and Applications, Vol. 45, pp. 41-51, 1985.
23. Chao, I., Golden, B., and Wasil, E., “An Improved Heuristic for the Period Vehicle Routing Problem,” Networks, Vol. 26, pp. 25-44, 1995.
24. Chen, F., Drezner, Z., Ryan, J. k., and Simchi-Levi, D., “Quantifying the Bullwhip Effect in a Simple Supply Chain: the Impact of Forecasting, Lead Times and Information,” Management Science, Vol. 46, pp. 436-443, 2000.
25. Chien, T., Balakrishnan, A., and Wong, R., “An Integrated Inventory Allocation and Vehicle Routing Problem,” Transportation Science, Vol. 23, pp. 67-76, 1989.
26. Christofides, N. and Beasley, J., “The Period Routing Problem,” Networks, Vol. 14, pp. 237-256, 1984.
27. Clarke, G. and Wright, J. W., “Scheduling Vehicle from a Central Delivery Depot to a Number of Delivery Points,” Operation Research Quarterly, Vol. 12, pp. 568-581, 1964.
28. Clemmet, A., “Demanding Supply,” Work Study, Vol. 44, No. 7, pp. 23-24, 1995.
29. Computer Associates International, Inc., “ Computer Associates and cStar Transform Vending Industry Through Optimal Vending Solution,” http://www.cstartech.com/Cacstarsolution.htm, 2000.
30. Computer Associates International, Inc., “Computer Associates dispenses new revenue opportunities for The Vending Machine Industry with nicenter TNG Optimal Vending Solution,” http://www3.ca.com/press/pressrelease.asp?ID=347, 2002.
31. Cordeau, J., Gendreau, M., and Laporte, G., “A Tabu Search Heuristic for Periodic Multi-Depot Vehicle Routing Problems,” Networks, Vol. 30, pp. 105-119, 1997.
32. Dong, Y., and Xu, K. “A Supply Chain Model of Vender Managed Inventory,” Transportation Research Part E, Vol. 38, pp. 75-95, 2002.
33. Federgruen, A. and Zipkin, P., “A Combined Vehicle Routing and Inventory Allocation Problem,” Operations Research, Vol. 32, No. 5, pp. 1019-1036, 1984.
34. Fisher M. L., and Jaikumar R., “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, Vol. 11, pp. 109-124, 1981.
35. Gaudioso, M., and Paletta, G., “A Heuristic for the Periodic Vehicle Routing Problem,” Transportation Science, Vol. 26, pp. 86-92, 1992.
36. Gillett B. and Miller L., “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Operations Research, Vol. 22, pp. 340-349, 1974.
37. Golden, B., Assad, A., and Dahl, R., “Analysis of a Large Scale Vehicle Routing Problem with an Inventory Component,” Large Scale System, Vol. 7, pp. 181-190, 1984.
38. Golden, B., Assad, A., Levy, L., and Gheysens, F., “The Fleet Size and Mix Vehicle Routing Problem,” Comput and Operation Research, Vol. 11, pp. 49-66, 1984.
39. Isochron Data Corporation, “Vending leaders who want to keep sales up and costs down choose VendCast - the only complete information-retrieval system designed specifically for the vending industry,” http://www.isochron.com/solutions_VC.htm, 2002.
40. Kirkpatrick, S., Gelatt, Jr. C. D., Vecchi, M. P., “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, pp. 671-680, 1983.
41. Kleywegt, A., Nori, V., and Savelsbergh, M., “The Stochastic Inventory Routing Problem with Direct Deliveries,” Transportation Science, Vol. 29, No. 3, 2002.
42. Koulamas, C., Antony, S., and Jaen, R., “A Survey of Simulated Annealing Applications to Operations Research Problems,” Omega : International Journal of Management Science, Vol. 22, pp. 41-56, 1994.
43. Lee, H., Padmanabhan, P., and Whang, S., “Information Distortion in a Supply Chain: the Bullwhip Effect,” Management Science, Vol. 43, pp. 546-558, 1997.
44. Lin, S., “Computer Solution of the Traveling salesman Problem,” The Bell System Technical Journal, Vol. 44, pp. 2245-2269, 1965.
45. Lin, S., and Kernighan, B. W., “An Effective Heuristic Algorithm for Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516, 1973.
46. m-Travel.com, “Coca-Cola, DoCoMo Test Wireless Vending Machines,” http://www.m-travel.com/10904.shtml, 2001.
47. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., and Teller, A. H., “Equation of State Calculations by Fast Computing Machines,” The Journal of Chemical Physics, Vol. 21, No. 6, pp. 1087-1092, 1953.
48. Mickey, R. W., and Thomas, L. W., “Solving Quadratic Assignment Problems by Simulated Annealing,” IIE Transactions, Vol. 19, pp. 107-119, 1987.
49. Miyamoto, Y., and Kubo, M., “Case Study: The Inventory Routing For Vending Machines,” Journal of the Operations Research, Vol. 44, No. 4, pp. 378-389, 2001.
50. Mole, R. and Jameson, S., “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion,” Operation Research Quarterly, Vol. 27, pp. 503-511, 1976.
51. Russell, R., and Gribbin, D., “A Multiphase Approach to the Period Routing Problem,” Networks, Vol. 21, pp. 747-765, 1991.
52. Russell, R., and Igo, W., “An Assignment Routing Problem,” Networks, Vol. 9, pp. 1-17, 1979.
53. Shih, L. H., and Chang, H. C., “A Routing and Scheduling System for Infectious Waste Collection,” Environmental Modeling and Assessment, Vol. 6, pp. 261-269, 2001.
54. Tan, C., and Beasley, J., “A Heuristic Algorithm for the Period Vehicle Routing Problem,” OMEGA, Vol. 12, pp. 497-504, 1984.
55. TinyTalksVending.com, “Wireless Vending: Back on the Vend Operator’s Agenda,” http://www.tinytalksvending.com/News/20000925.htm, 2000.
56. Vianna, D. S., Ochi, L. A., and Drummond, L. M. A., “A Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem,” International Parallel and Distributed Processing Symposium, San Juan, Puerto Rico, 1999.