A heuristic for the inventory management of smart vending machine systems
YangByung Park, JunSu Yoo
Department of Industrial and Management Systems Engineering, College of Engineering, Kyung Hee University (Republic of Korea)
Received: October 2011
Accepted: August 2012
Byung, Y., & Yoo, J.S. (2012). A heuristic for the inventory management of smart vending machine systems. Journal of Industrial Engineering and Management, 5(2), 354363. http://dx.doi.org/10.3926/jiem.587

Abstract:
Purpose: The purpose of this paper is to propose a heuristic for the inventory management of smart vending machine systems with product substitution under the replenishment point, orderupto level policy and to evaluate its performance.
Design/methodology/approach: The heuristic is developed on the basis of the decoupled approach. An integer linear mathematical model is built to determine the number of product storage compartments and replenishment threshold for each smart vending machine in the system and the Clarke and Wright’s savings algorithm is applied to route vehicles for inventory replenishments of smart vending machines that share the same delivery days. Computational experiments are conducted on several smallsize test problems to compare the proposed heuristic with the integrated optimization mathematical model with respect to system profit. Furthermore, a sensitivity analysis is carried out on a mediumsize test problem to evaluate the effect of the customer service level on system profit using a computer simulation.
Findings: The results show that the proposed heuristic yielded pretty good solutions with 5.7% error rate on average compared to the optimal solutions. The proposed heuristic took about 3 CPU minutes on average in the test problems being consisted of 10 fiveproduct smart vending machines. It was confirmed that the system profit is significantly affected by the customer service level.
Originality/value: The inventory management of smart vending machine systems is newly treated. Product substitutions are explicitly considered in the model. The proposed heuristic is effective as well as efficient. It can be easily modified for application to various retail vending settings under a vendormanaged inventory scheme with POS system.
Keywords: heuristic, inventory management, smart vending machines, decoupled approach

1. Introduction
Smart vending machines that enable sales and inventory information to be remotely monitored through the Internet using embedded online messaging devices were recently introduced. Webster et al. (1999) developed an experimental Java clientserver system with a special purpose hardware interface to control a Pepsi vending machine via the Internet. Jofemar unveiled what it claims is the world’s first autonomous hydrogenpowered smart vending machine at the 2009 National Vending Machine Exposition (Fuel Cells Bulletin, 2009). Figure 1 shows an example of a smart beverage vending machine operated at G20 Seoul Summit Conference in 2010.
Smart vending machines are expected to resolve the problems inherent to conventional vending machines such as runout of products and machine breakdowns left for a long time. Wolson (2000) insisted that smart vending machines are the future of the vending machine industry.
The inventory management of smart vending machine systems with product substitution under the replenishment point, orderupto level policy creates a decision making problem. The problem includes the determination of replenishment points of products at vending machines, product allocation to vending machine storage compartments, replenishment thresholds at vending machines, and vehicle routes for inventory replenishments.
Little work has addressed the inventory management of smart vending machine systems in the literature. Poon et al. (2010) developed an index to make replenishment decisions for smart vending machines to minimize transportation and stockout costs. Park and Yoon (2011) proposed a twophase solution based on a nonlinear integer mathematical model for the operation problem of conventional vending machine supply chains with stockout based, onestage item substitution. Among reports regarding inventoryrouting problems, some are applicable for determining shipping policies in smart vending machine systems (see Archetti et al., 2007; Li et al., 2010; Moin et al., 2011).
Figure 1. Example of a smart vending machine
In this paper, we propose a heuristic for the inventory management of smart vending machine systems with product substitution under the replenishment point, orderupto level policy and conduct computational experiments on several test problems in order to evaluate its optimality. Furthermore, a sensitivity analysis is carried out to evaluate the effect of customer service level on system profit using a computer simulation.
The remainder of this paper is organized as follows: A heuristic for the inventory management of smart vending machine systems is proposed in Section 2. Computational experiments are described in Section 3. Finally, conclusions are drawn in Section 4.
2. A Heuristic for the Inventory Management of Smart Vending Machine Systems
Input parameters
N number of products
M number of storage compartments
Q capacity of a storage compartment
d_{ri} average daily demand for product i at smart vending machine r
v_{i} value of product i
b_{1} rate of inventory carrying cost per day
b_{2} rate of smart vending machine operating cost
b_{3} rate of substitution cost
h allowance ratio of lost sales during a time span
G vehicle capacity
A fixed transportation cost per vehicle per day
e variable transportation cost per kilometer
l_{0r} Euclidean distance from depot 0 to smart vending machine r
u_{ri} replenishment point of product i at smart vending machine r
Decision variables
q_{r} replenishment threshold at smart vending machine r
P_{r} time span between the successive replenishments at smart vending machine r
K_{ri} number of storage compartments for product i at smart vending machine r
F_{rij} amount of product i substituted by j at smart vending machine r during a time span
I^{a}_{ri} inventory level of product i at smart vending machine r at the end of a time span when product substitution is allowed
B^{a}_{ri} lost sales of product i at smart vending machine r during a time span when product substitution is allowed
B^{b}_{ri} stockouts of product i at smart vending machine r during a time span when product substitution is not allowed
Z_{ri} 1 if the inventory level of product i at smart vending machine r is below the replenishment point; 0 otherwise
A smart vending machine is fully replenished when the number of products with inventories that are depleted to their respective replenishment points is equal to the replenishment threshold (an integer value between 1 and the maximum number of products). When a customer is faced with stockout of his or her firstchoice product, he or she may choose a substitute or give up the purchase. When the product substitution takes place, the customer’s unsatisfactory cost is considered as substitution cost.
The replenishment point of a product is determined by the average daily demand and customer service level, assuming the Poisson distribution for customer arrivals and the lead time of one day. The number of product storage compartments and replenishment threshold for smart vending machine r are determined by solving the linear integer mathematical model as follows:
Objective function
Objective function (1) maximizes the profit during the time span between successive replenishments, which is computed by subtracting the sum of the transportation cost, inventory carrying cost, smart vending machine operating cost, and substitution cost from the total revenue.
Constraints
Various constraints are required. The constraints for computing the inventory levels and stockouts of products, restricting the allocation of product storage compartments, limiting the quantities of products for substitution, and restricting the domain of variables are formed by modifying the ones shown in Park and Yoon (2011).
More constraints are needed to determine the replenishment threshold at smart vending machine r, q_{r}. Constraints (2) and (3) determine if product inventories reach their respective replenishment points. q_{r} is computed by counting Z_{ri} with a value of 1 for all products.
Since the objective function is to maximize the profit of a smart vending machine, the time span may be lengthened to the period in which the last remaining product in the vending machine is sold out, generating undesirably a large amount of lost sales. Therefore, Constraint (4) that restricts the amount of lost sales during the time span should be included.
Once the number of product storage compartments and replenishment threshold is determined for all the smart vending machines in the system, the vehicle routes to replenish the smart vending machines that share the same delivery days are constructed. For vehicle routing, the Clarke and Wright’s savings algorithm (1964) is employed while minimizing the transportation cost. The saving expected by combining two routes, s_{qr}, is computed as follows:
where q denotes the last smart vending machine to visit on one route and r denotes the first one to visit on the other route.
A combination of two routes with the largest positive s_{qr} is repeated while checking the feasibility with respect to vehicle capacity and travel time until no more feasible pair exists for which s_{qr}>0. Once routes have been constructed, 2opt algorithm is applied to improve the route solution.
3. Computational Experiments
The fiveproduct smart vending machine locations were generated using a uniform distribution on [0, 100]. The location of a depot was set to (50, 50). The daily demand at each smart vending machine was generated from a Poisson distribution, the average of which was generated from a uniform distribution on [150, 210]. The values of five products were set to 0.525, 0.875, 1.225, 0.7, and 1.05, respectively. The rates of inventory carrying cost, smart vending machine operating cost, and substitution cost were set to 0.01, 0.1, and 0.05, respectively. The vehicle capacity was set to 3200. The fixed and variable transportation costs were set to 100 and 0.4, respectively. The allowance ratio of lost sales was set to 0.3.
It was assumed that the warehouse at the business office always stores the sufficient amount of products to replenish the smart vending machines in the system. Computational experiments were carried out on an IBM compatible Pentium IV PC (2.21GHz CPU, 1GB RAM).
3.1. Comparison of the Integrated Optimization Model and the Proposed Heuristic
We evaluated the performance of the proposed heuristic by comparing it with the integrated optimization mathematical model. The optimization mathematical model determines the number of product storage compartments and replenishment thresholds at smart vending machines and the vehicles routes for daily replenishments in an integrated way while maximizing the system profit during a planning horizon. The integrated optimization model was constructed by basically combining the mathematical model presented in Section 2 and the constraints for vehicle routing proposed by Abdelmaguid and Dessouky (2006).
In order to solve the integrated optimization model within a reasonable amount of computation time, we formed a smallsize base problem consisting of ten smart vending machines with M=20 and Q=20 and constructed three test problems with different daily demand.
Table 1 compares the average daily profit per smart vending machine for the integrated optimization mathematical model and the proposed heuristic in the three test problems. The mathematical models were solved using LINGO 11.0. The optimization mathematical model and the heuristic took about 45 CPU minutes and 3 CPU minutes on average, respectively.
Problem 
Solution 
Revenue 
Cost 
Profit 
Error rate(%) 
1 
Optimization model 
321.1 
269.3 
51.8 
 
Prpoposed heuristic 
305.3 
256.5 
48.8 
5.79 

2 
Optimization model 
329.7 
275.3 
54.4 
 
Proposed heuristic 
313.2 
261.5 
51.7 
4.96 

3 
Optimization model 
348.6 
287.4 
61.2 
 
Proposed heuristic 
327.8 
270.5 
57.3 
6.37 
Table 1. Comparison of two solutions for the average daily profit per smart vending machine
3.2. Sensitivity Analysis
We carried out a sensitivity analysis to evaluate the effect of the customer service level on system profit using the proposed heuristic. We formed a base problem consisting of eighty smart vending machines with M=25 and Q=30. The operation of the smart vending machine system was modeled with Arena 10.0 (Kelton et al., 2007). Salmeron (2009) stated that simulation is one of the most commonly used methodologies employed in operations management research and listed some emerging areas to apply including system design.
During the simulation, when a vehicle faces deficiencies of some products when filling a smart vending machine, it stocks the storage compartments as much as possible and travels to the next vending machine with the remaining supply. When a vehicle still has supply after serving the last vending machine on its tour, it returns to the depot with the remainder. The daily operation of vehicles is limited to 8 hours.
Table 2 shows the average daily profit per smart vending machine for four different service levels in three replications, which were obtained by simulating each level for 365 days. The highest average daily profit per smart vending machine was obtained at a 70% service level. For a statistical confirmation of our finding, we performed a oneway analysis of variance (ANOVA) using an Excel spreadsheet, as shown in Table 3. The test statistic was obtained as F_{0}=15.86>F_{0.05,3.8}=4.07, indicating that the customer service level has a statistically significant effect on profit at the 5% level.
Replication 
Customer service level 

0.5 
0.7 
0.9 
0.99 

1 
89.8 
90.3 
90.2 
89.2 
2 
89.9 
89.9 
89.8 
89.3 
3 
89.9 
90.1 
89.8 
89.3 
Avg. 
89.9 
90.1 
89.9 
89.3 
Table 2. Average daily profit per smart vending machine for four different service levels
Changes in types 
Sum of squares 
Degree of freedom 
Meansquared 
F0 
Pvalue 
F0.05,3 ,8 
Treatment 
1.189167 
3 
0.396389 
15.85556 
0.000994 
4.066181 
Residuals 
0.2 
8 
0.025 



Total 
1.389167 
11 




Table 3. Test statistics of ANOVA for the service level
Table 4 shows the partial solutions of the five smart vending machines randomly selected, which were obtained in the first replication with the customer service level of 0.7. Table 5 shows the monetary outputs obtained in the first replication with the customer service level of 0.7 by simulating the system for 365 days.
Vending machine

No. of storage compartments 
Replenishment threshold 

Product 

1 
2 
3 
4 
5 

1 
2 
7 
3 
9 
4 
4 
36 
1 
6 
3 
7 
8 
4 
49 
2 
5 
4 
7 
7 
5 
58 
1 
8 
3 
9 
4 
3 
80 
1 
7 
6 
8 
3 
5 
Table 4. Partial solutions obtained in the first replication with the service level of 0.7


Revenue 
Cost 
Profit 

Purchase 
Inventory carrying 
machine operating 
Transportation 
Substitution 

fixed 
variable 

13101.4 
8515.9 
252.1 
1310.1 
206.5 
96.1 
61.2 
2659.4 
Table 5. System outputs obtained in the first replication with the service level of 0.7 (1000 units)
4. Conclusions
We proposed a heuristic for the inventory management of smart vending machine systems with product substitution under the replenishment point, orderupto level policy. The heuristic solves the problem in a decoupled way. First, it determines the replenishment points of products at smart vending machines. Second, it determines the number of product storage compartments and the replenishment thresholds at smart vending machines. Third, it determines the vehicle routes for daily replenishments.
The proposed heuristic yielded pretty good solutions with 5.7% error rate on average compared to the optimal solutions obtained by solving the integrated mathematical model. The heuristic took about 3 CPU minutes. It was confirmed through the sensitivity analysis using a computer simulation that the system profit is significantly affected by the customer service level.
Future research is necessary to develop more efficient and effective solutions for the inventory management of smart vending machine systems. Furthermore, it is required to develop an algorithm to find the optimal allowance ratio of lost sales during the time span which maximizes the system profit.
Acknowledgment
This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science, and Technology (20110004391).
References
Abdelmaguid, T.F. and Dessouky, M.M.A. (2006). Genetic algorithm approach to the integrated inventorydistribution problem. International Journal of Production Research, 44(21), 4445 – 4464. http://dx.doi.org/10.1080/00207540600597138
Archetti, C., Bertazzi, L., Laporte, G., & Speranza, M.G. (2007). A branchandcut algorithm for a vendormanaged inventoryrouting problem. Transportation Science, 41(3), 382391. http://dx.doi.org/10.1287/trsc.1060.0188
Clarke, G., & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568581. http://dx.doi.org/10.1287/opre.12.4.568
Fuel Cells Bulletin (2009). Jofemar launches hydrogenpowered vending machine. Fuel Cells Bulletin, January, 910.
Kelton, W., Sadowski, R.P., & Sturrock, D.T. (2007). Simulation with arena. 4th ed., New York: McGrawHill.
Li, J., Chen, H., & Chu, F. (2010). Performance evaluation of distribution strategies for the inventory routing problem. European Journal of Operational Research, 202(2), 412–419. http://dx.doi.org/10.1016/j.ejor.2009.05.018
Moin, N.H., Salhi, S., & Aziz, N.A.B. (2011). An efficient hybrid genetic algorithm for the multiproduct multiperiod inventory routing problem. International Journal of Production Economics, 133(1), 334343. http://dx.doi.org/10.1016/j.ijpe.2010.06.012
Park, Y.B., & Yoon, S.J. (2011). A twophase solution for the operation problem of vending machine systems with stockout based, onestage item substitution. Proceedings of the 16^{th} Annual International Conference on Industrial Engineering, Stuttgart, Germany, 363369.
Poon, T.C., Choy, K.L., Cheng, C.K., & Lao, S.I. (2010). A realtime replenishment system for vending machine industry. IEEE International Conference on Industrial Informatics, 209213.
Salmeron, J.L. (2009). Special issue: New trends in process simulation and modeling. Journal of Industrial Engineering and Management, 2(2), 319322. http://dx.doi.org/10.3926/jiem.2009.v2n2.p319322
Wolson, S. (2000). Remote technology gaining acceptance: smart machines. Food Service Director, 13(8), 13.
Webster, R.W., Ross, P.W., Bailey, T.M., Conrad, S.M., Fiorill, M.J., Flinchbaugh, J.M., & Velkly, E.A. (1999). Controlling a Java enabled Pepsi^{®} vending machine over the world wide web. IECON Proceedings of the 25^{th} Annual Conference of the IEEE, 1(29), 86–90.
This work is licensed under a Creative Commons Attribution 4.0 International License
Journal of Industrial Engineering and Management, 20082024
Online ISSN: 20130953; Print ISSN: 20138423; Online DL: B287442008
Publisher: OmniaScience