供應商管理庫存下週期性配送問題之研究-以自動販賣機補貨為例

Period Distribution Problem for Vendor Managed Inventory – A Case Study for Vending Machine Replenishment

陳昆皇(Kun-Huang Chen)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/碩士(2006年)

摘要

供應商管理庫存(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%.

並列關鍵字

Vendor Managed Inventory ； Vending Machine ； Period Traveling Salesman Problem ； Genetic Algorithm ； Supply Chain Management

參考文獻

9. 劉奕青 (2002)，『自動販賣機存貨途程問題之研究』，元智大學工業工程管理研究所碩士論文。

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.