Automated Teller Machine Replenishment Policies with Submodular Costs

We develop an automated teller machine (ATM) replenishment policy for a bank that operates multiple ATMs. The aim is to minimize the cost of replenishments and stockouts, taking into account the economies of scale involved in replenishing multiple ATMs simultaneously. When the replenishment is outsourced to an outside vendor, the replenishment cost is typically additive. However, when it is done by in-house operations, the replenishment cost is a submodular function of the set of ATMs being replenished. The additive replenishment cost function yields a tractable and separable inventory management problem. However, the submodular cost function creates a much harder problem. We construct a Markov decision process model and study the structure of the optimal strategy that minimizes the long-run average cost. Since the optimal policy is analytically and computationally intractable for the case of a large number of ATMs, we study a heuristic policy (called the index policy) in the case of submodular replenishment costs. We find that the index policy performs close to the optimal policy (when it can be computed) and performs much better than the benchmark (namely, an ( s , M ) policy) in general. We demonstrate similar findings in a real-world data set with 139 ATMs and 20 months of historical demand data. Finally, we recommend that the bank managers use the index policy to design a replenishment schedule.