自動販賣機存貨途程問題之研究

The Inventory Routing Problem for Vending Machines

劉奕青(Yi-Ching Liu)

指導教授 ： 丁慶榮

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

摘要

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

並列關鍵字

Vending Machine ； Inventory Routing Problem ； Periodic Vehicle Routing Problem ； Simulated Annealing

參考文獻

10. 韓復華，卓裕仁，「包容性深廣度搜尋法在週期性車輛路線問題之應用」，運輸計劃季刊，第31卷，第一期，民國91年3月，pp.1-36。

4. 林志鴻，陳春益，曹以明，「汽車運送業拖車途程問題之研究」，運輸計劃季刊，第31卷，第一期，民國91年3月，pp.171-206。

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.