Journal of Industrial Engineering and Management

A heuristic for the inventory management of smart vending machine systems

Yang-Byung Park, Jun-Su 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), 354-363. 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, order-up-to 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 small-size 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 medium-size 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 five-product 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 vendor-managed 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 client-server 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 hydrogen-powered 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 run-out 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, order-up-to 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 stock-out costs. Park and Yoon (2011) proposed a two-phase solution based on a nonlinear integer mathematical model for the operation problem of conventional vending machine supply chains with stock-out based, one-stage item substitution. Among reports regarding inventory-routing 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, order-up-to 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₁            rate of inventory carrying cost per day

b₂            rate of smart vending machine operating cost

b₃            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  stock-outs 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 stock-out of his or her first-choice 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 stock-outs 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, 2-opt algorithm is applied to improve the route solution.

3. Computational Experiments

The five-product 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 small-size 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.

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 one-way analysis of variance (ANOVA) using an Excel spreadsheet, as shown in Table 3. The test statistic was obtained as F₀=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.

Table 2. Average daily profit per smart vending machine for four different service levels

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.

Table 4. Partial solutions obtained in the first replication with the service level of 0.7

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, order-up-to 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 (2011-0004391).

References

Abdelmaguid, T.F. and Dessouky, M.M.A. (2006). Genetic algorithm approach to the  integrated inventory-distribution 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 branch-and-cut algorithm for a vendor-managed inventory-routing problem. Transportation Science, 41(3), 382-391. 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), 568-581. http://dx.doi.org/10.1287/opre.12.4.568

Fuel Cells Bulletin (2009). Jofemar launches hydrogen-powered vending machine. Fuel Cells Bulletin, January, 9-10.

Kelton, W., Sadowski, R.P., & Sturrock, D.T. (2007). Simulation with arena. 4th ed., New York: McGraw-Hill.

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 multi-product multi-period inventory routing problem. International Journal of Production Economics, 133(1), 334-343.  http://dx.doi.org/10.1016/j.ijpe.2010.06.012

Park, Y.B., & Yoon, S.J. (2011). A two-phase solution for the operation problem of vending machine systems with stock-out based, one-stage item substitution. Proceedings of the 16^th Annual International Conference on Industrial Engineering, Stuttgart, Germany, 363-369.

Poon, T.C., Choy, K.L., Cheng, C.K., & Lao, S.I. (2010). A real-time replenishment system for vending machine industry. IEEE International Conference on Industrial Informatics, 209-213.

Salmeron, J.L. (2009). Special issue: New trends in process simulation and modeling. Journal of Industrial Engineering and Management, 2(2), 319-322. http://dx.doi.org/10.3926/jiem.2009.v2n2.p319-322

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.