臺灣博碩士論文加值系統

供應商管理庫存(Vendor Managed Inventory, VMI)是由供應商來管理顧客的存貨補充作業，不需要顧客下單而由供應商週期性補貨。其中必須決定何時補貨、補貨的數量及補貨的順序，自動販賣機的補貨與配送問題就是供應商管理庫存的一個例子。當只有考慮何時補貨及補貨顧客的順序時，此問題就類似週期性旅行銷售員問題(Period Traveling Salesman Problem, PTSP)，因此本研究以PTSP為基礎再考量補貨之間顧客的存貨成本來建構數學模式，並以自動販賣機的補貨為研究對象。

由於PTSP為旅行推銷員問題的衍生問題，屬於NP-hard的問題，正確解法在求解大問題時需很長的計算時間，因此本研究利用基因演算法求解在VMI下週期性配送問題。其中與一般基因演算法不同的地方是在突變的方式，本研究將區域搜尋結合在突變步驟中，在測試所發展的基因演算法時，首先針對PTSP的標竿問題測試，確定本研究所提出的演算法可行後，再以實務資料驗證。

在33題PTSP測試例題的結果中找到19題目前已知最佳解，另有1題突破目前文獻已知最佳解，而與文獻已知最佳解的平均誤差只有0.13%。另外本研究收集某飲料公司在桃園地區所配送的自動販賣機資料，並從業者建議的淡旺季中各挑選二個區域資料來驗證本研究的模式，其中主要比較週期性配送之總成本及販賣機缺貨情況。由本研究提之方法所得的配送方式與現有配送方式比較，結果發現一個區域的總成本比現況每星期最多可節省12,064元(7.51%)，而且缺貨率最多也降低34.9%，證明本研究之所發展之方法比現行由配送人員經驗法則好，未來可以作為此飲料公司在規劃補貨時參考。

Vendor managed inventory (VMI) is one the most widely discussed partnering initiatives for inventory control in supply chain management. Under such partnerships, the vendor monitors the buyers’ inventory levels and makes periodic replenishment decisions regarding when to serve a customer and how much to deliver to a customer when served. Vending machine replenishment is an example of the VMI policy if both vendor and machines belong to the same company. However, for each day of delivery, the vendor also has to decide what sequence to use in that day.

For the timing and sequencing decisions, they are similar to the period traveling salesman problem (PTSP) if the vendor delivers the goods by only one vehicle. Therefore, we develop a mathematical programming model based on the PTSP and take the delivery quantity question into account. We assume that each vending machine must be visited at least once during the planning horizon. The objective is to minimize the total system cost which includes transportation cost and inventory cost. Since PTSP is an NP-hard problem, an exact solution approach cannot find optimal solution within reasonable computation time for large-scale problem. We propose a genetic algorithm (GA) to solve the period distribution problem. The algorithm is tested in two stages. In the first stage, the algorithm is first tested with 33 PTSP benchmark problems from the literature. The results show that the proposed GA can obtain 19 best known solutions and find a new best solution. We then tested the algorithm with real data collected from a local beverage company who owns over one thousand vending machines.

Two months data of different service areas collected from a local beverage company are analyzed by comparing the proposed heuristic with the current delivery approach. We first compare the total system cost and then simulate daily demand based on the historical data to compare the stockout probability for current and proposed delivery pattern. The results show that our GA heurist provides better total system cost. The proposed delivery pattern can save the total cost by up to NT$22,174/week (7.51%). The simulation results also reveal that the proposed heuristic can reduce the stockout percentage by up to 34.9%.

摘 要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 i
圖目錄 i
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 3
1.3 研究目的 5
1.4 研究範圍 5
1.5 研究架構與流程 6
第二章 文獻探討 8
2.1 車輛途程問題 8
2.1.1車輛途程問題的分類 8
2.1.2車輛途程問題的求解方法 10
2.1.3週期性車輛途程問題 11
2.2週期性旅行銷售員問題 15
2.3存貨途程問題 16
2.4 供應商庫存管理 18
2.5 基因演算法 19
2.6 小結 33
第三章 模式建立 34
3.1問題描述 34
3.2問題假設 35
3.3存貨成本計算 36
3.4模式建構 37
3.5演算法架構 40
3.5.1分群演算流程 40
3.5.2基因演算法演算機制 41
3.6小結 45
第四章 模式測試與分析 46
4.1測試例題 46
4.1.1 參數分析 46
4.1.2 同一參數設定結果 49
4.2實例說明 52
第五章 實例測試 57
5.1 實例資料 57
5.2以最小頻率為調整配送頻率 59
5.2.1以最小頻率為調整配送頻率 59
5.2.1原廠商資料與以最小頻率為配送基準二種配送頻率比較 61
5.3以服務水準考量配送頻率 63
5.3.1以最小頻率為配送與考慮服務水準二基準比較 63
5.3.2各種服務水準比較 64
5.4小結 67
第六章 結論與未來研究方向 68
6.1 結論 68
6.2 未來研究方向 70
參考文獻 71
附錄一 GA各系統測試參數測試方案 76
附錄二 GA各系統測試參數測試結果 78

1.日本自動販賣機工業會：日本自動販賣機工業會網頁。 http://www.jvma.or.jp/
2.呂俊逸 (1996)，『週期性路線規劃應用於感染性廢棄物回收之研究』，國立成功大學資源工程學系碩士論文。
3.卓裕仁 (2001)，『以巨集啟發式方法求解多車種與週期性車輛路線問題之研究』，國立交通大學運輸工程與管理研究所博士論文。
4.林永德 (1998)，『週期性路線規劃應用於感染性廢棄物回收之研究』，國立成功大學資源工程學系碩士論文。
5.林柏齊(1998)，『運用基因演算法於週期性廢棄物收集路線之規劃』，國立成功大學資源工程學系碩士論文。
6.張志華 (2000)，『週期性廢棄物收集規劃之決策系統』，國立成功大學資源工程學系碩士論文。
7.張志鴻(2002)，『無線電自動販賣機商品配送作業之研究』，中華大學科技管理研究所碩士論文。
8.張延吉 (2000)，『考慮派車時段與載重均衡之車輛途程規劃問題』，逢甲大學工業工程研究所碩士論文。
9.劉奕青 (2002)，『自動販賣機存貨途程問題之研究』，元智大學工業工程管理研究所碩士論文。
10.劉銘韻 (1993)，『週期性車輛路線問題(PVRP)啟發式解法之探討』，國立交通大學土木工程研究所管理組碩士論文。
11.韓欽銓，陳姿怡，胡瓊華，簡竹伶，鍾志明 (2001)，『 利用軟式計算技術預測產品銷售與規劃配送路線』，會議論文，中國工業工程學會九十年度年會暨學術研討會。
12.蘇昭銘，張志鴻(2001)，『無線電自動販賣機商品配送系統之研究』，會議論文，中國工業工程師學會學術研討會。
13.Angelelli, E. and G. Speranza, (2002) “The Periodic Vehicle Routing Problem With Intermediate Facilities,” European Journal of Operational Research, 137, 233-247.
14.Baker E. K. and J. R. Schaffer, (1986) “Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constrations,” American Journal of Mathematical and Management Sciences, 6, .261-300.
15.Baptista S., R. C. Oliveira and E. Zuquete, (2002) “A Period Vehicle Routing Case Study,” European Journal of Operational Research. 139, 220-229.
16.Bard, L. H., P. Jaillet and M. Dror, (1998) “A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities,” Transportation Science, 32, 189-203.
17.Beltrami, E. J. and L. D. Bodin, (1974) “Networks and Vehicle Routing for the Municipal Waste Collection,” Networks, 4, 65-94.
18.Bertazzi, L., G. Paletta and M. G. Speranza, (2004) “An Improved Heuristic for Period Treveling Salesman Problem,” Computers and Operations Research, 31, 1215-1222.
19.Bodin, L. and B. Golden, (1981) “Classification in Vehicle Routing and Scheduling,” Networks, 11, 97-108.
20.Bodin, L., B. Golden, A. Assad and M. Ball, (1983) “Routing and Scheduling of Vehicle and Crews: The state of the Art,” Computers and Operations Research, 10, 63-211.
21.Campbell, A., L. Clarke and M. Savelsbergh, (1999) “The Inventory Routing Problem,” In T. Crainic and G. Laporte, editors, Fleet Management and Logistics, Kluwer Academic Publishers. , New York.
22.Chao I. M., B. L. Golden, and E. A. Wasil, (1995) “A new heuristic for the period traveling salesman problem," Computers and Operations Research, 22, 553-565.
23.Chao, I. M., (1993) "Algorithms and solutions to multi-level vehicle routing problems," Ph.D. Dissertation. Applied Mathematics Program, University of Maryland, College Park, MD.
24.Chao, I. M., B. L. Golden and E. A. Wasil, (1995) “A New Heuristic for the Period Treveling Salesman Problem,” Computers and Operations Research, 22, 553-565.
25.Chao, I., B. Golden and E. Wasil, (1995) “An Improved Heuristic for the Period Vehicle Routing Problem,” Networks, 26, 25-44.
26.Chien, T. W., A. Balakrishan and R. T. Womg, (1989) “An Inventory Allocation and Vehicle Routing Problem,” Transportation Science, 23, 67-77.
27.Chiou, S,W. (2005) “Integrating the Inventory Management and Vehicle Routing Problem for Congested Urban Logistics Network,” Journal of Eastern Asia Society for Transportation Studies, 6, 3038-3051.
28.Christofides, N. and J. Beasley, (1984) “The Period Routing Problem,” Networks, 14, 237-256.
29.Clarke, G. and J. W. Wright, (1964) “Scheduling Vehicle from a Central Delivery Depot to a Number of Delivery Points,” Operations Research Quarterly, 12, 568-581
30.Cordeau J. F., M. Gendreau, and G. Laporte, (1995) "A tabu search heuristic for periodic and multi-depot vehicle routing problems," Publication CRT-95-76, Centre de recherche sur les trasports, Université de Montréalc.
31.Cordeau, J. F., M. Gendreau, and G. Laporte, (1997) “A tabu search heuristic for periodic and multi-depot vehicle routing problems," Networks, 30, 105-119.
32.Cordeau, J., M. Gendreau and G. Laporte, (1997) “A Tabu Search Heuristic for Periodic Multi-Depot Vehicle Routing Problems,” Networks, 30, 105-119.
33.Danzig, G.B. and J.H. Ramser, (1959) “The Truck Dispatching Problem,” Management Science, 6, 80-91.
34.Dong, Y. and K. Xu, (2002) “A Supply Chain Model of Vendor Managed Inventory,” Transportation Research Part E, 38, 75-95.
35.Dror, M. and M. Ball, (1987) “Inventory Routing: Reduction from an Annual to Short Period Problem,” Naval Research Logistics Quarterly, 34, 891-905.
36.Drummond L. M. A., L. S. Ochi and D. S. Vianna, (2001) “An Asynchronous Parallel Metaheuristic for the Period Vehicle Routing Problem,” Future Generation Computer System, 17, 379-386.
37.Eilon, S. and W. G. CDT and N. Christofides, (1971) “Distribution Management: Mathematical Modelling and Practical Analysis," London: Griffin.
38.Federgruen, A. and P. Zipkin, (1984) “A Combined Vehicle Routing and Inventory Sllocation Problem,” Operations Research, 32, 1019-1037.
39.Fisher M. L. and R. Jaikumar, (1981) “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, 11, 109-124.
40.Garey, M. R., and D. S. Johnson, (1979) “Computers and Intractability: A Guide to the Theory of NP-Complereness,” Freeman, New York: W. H Freeman and Company.
41.Gaudioso, M. and G. Paletta, (1992) “A Heuristic for the Periodic Vehicle Routing Problem,” Transportation Science, 26, 86-92.
42.Gen, M. and R. Cheng, (1997) “Genetic Algorithms and Engineering Design," Wiley and Sons, New York.
43.Gillett B. and L. Miller, (1974) “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Operations Research, 22, 340-349,
44.Golden, B. L., A. Assad and R. Dahl, (1984) “Analysis of a Large Scale Vehicle
Routing. Problem with an Inventory Component,” Large Scale Systems, 7, 181-190.
45.Hadjiconatantinou, E. and R. Baldacci, (1998) “A Multi-Depot & Period Vehicle Routing Problem Arising in the Utilities Sector,” The Journal of the Operational Research Society, 22, 65-71.
46.Holmstorm, J, (1998) “Implementing Vendor-Managed Inventory the Efficient Way: a Case Study of Partnership in the Supply chain," Production and Inventory Management Journal, 39, 1-5.
47.Kleywegt, A., V. Nori and M. Savelsbergh, (2002) “The Stochastic Inventory Routing Problem with Direct Deliveries,” Transportation Science, 29, 1-41.
48.Lawler E. L, J. K. Lenstra, K. A. Rinnooy, and D. B. Shmoys, (1985) “The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,” Wiley, New York.
49.Lin, S (1965), “Computer Solution of the Traveling salesman Problem,” The Bell System Technical Journal, 44, 2245-2269.
50.Lin, S. and B. W. Kernighan, (1973) “An Effective Heuristic Algorithm for Traveling Salesman Problem,” Operations Research, 21, 498-516.
51.Mator, A. C. and R. C. Oliverira, (2004) “An Experimental Study of the Ant Colony System for the Period Vehicle Routing Problem,” Lecture Notes in Computer Science, Springer-Verlag, 3172, 286–293.
52.Metz, P. J. (1998) “Demystifying Supply Chain Management,” Supply Chain Management Review, 16, 46-55.
53.Michalewicz, Z. (1997) “Heuristic Methods for Evolutionary Computation Techniques," Journal of Heuristics, 1, 177-206.
54.Miyamoto, Y. and M. Kubo, (2001) “Case Study: The Inventory Routing For Vending Machines,” Journal of the Operations Research Society, 44, 378-389.
55.Mole, R. and S. Jameson, (1976) “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion,” Operations Research Quarterly, 27, 503-511.
56.OR-Library: OR-Library Home Page. http://people.brunel.ac.uk/~mastjjb/jeb/info. html
57.Osman, I. H. (1995) “Routing Problems: A Bibliography,” Annals of Operations Research, 61, 227-262.
58.Paletta, G. (2002) “The Period Treveling Salesman Problem: Anew Heuristic Algorithm,” Computers and Operations Research, 29, 1343-1352.
59.Rusdiansyah, A. and D. Tsao, (2005) “An Integrated Model of the Periodic Delivery Problems for Vending-Machine Supply Chains,” Journal of Food Engineering, 70, 421-434.
60.Russell, A. R., (1977) “An Effective Heuristic for the M-Tour Traveling Salesman Problem with Some Side Conditions,” Operations Research, 25, 517-524.
61.Russell, R. A. and D. Gribbin, (1991) “A Multiphase Approach to the Period Routing Problem,”Networks, 21, 747–765.
62.Russell, R. and D. Gribbin, (1991) “An Mutiphase Approach to the Period Routing Problem,” Networks, 12, 747-765.
63.Russell, R. and W. Igo, (1979) “An Assignment Routing Problem,” Networks, 9, 1-17.
64.Shih, L. H. and H. C. Chang, (2001) “A Routing and Scheduling System for Infectious Waste Collection,” Environmental Modeling and Assessment, 6, 261-269
65.Stephen, C. H. L., Y. Wu and K. K. Lai, (2004) “A Study on Vendor-Managed Inventory for Vending Machine Network,” Proceedings of the Fifth Asia Pacific Industrial Engineering and Management Systems Conference.
66.Tan, C. R. and J. E. Beasley, (1984) “A Heuristic Algorithm for the Period Vehicle Routing Problem," Omega, 12, 497–504.
67.Vianna, D. S., L. A. Ochi and L. M. A. Drummond, (1999) “A Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem,” International Parallel and Distributed Processing Symposium, San Juan, Puerto Rico.
68.Webb, R. and R. C. Larson, (1995) “Period and Phase of Customer Replenishment: A New Approach to the Strategic Inventory/Routing Problem,” European Journal of Operational Research, 85, 132-148.
69.Yale, T. H. and R. Levy, (1997) “The Metered Inventory Routing Problem, An Integrative Heuristic Algorithm," International Journal of Production Economics, 51, 69-81.