Comparison of Integer Linear Programming and Dynamic Programming Approaches for ATM Cash Replenishment Optimization Problem

Comparison of Integer Linear Programming and Dynamic Programming Approaches for ATM Cash Replenishment Optimization Problem

Fazilet Özer (Middle East Technical University, Ankara, Turkey), Ismail Hakki Toroslu (Middle East Technical University, Ankara, Turkey) and Pinar Karagoz (Middle East Technical University, Ankara, Turkey)
Copyright: © 2020 |Pages: 13
DOI: 10.4018/IJAMC.2020070107


With the automated teller machine (ATM) cash replenishment problem, banks aim to reduce the number of out-of-cash ATMs and duration of out-of-cash status. On the other hand, they want to reduce the cost of cash replenishment, as well. The problem conventionally involves forecasting ATM cash withdrawals, and then cash replenishment optimization based on the forecast. The authors assume that reliable forecasts are already obtained for the amount of cash needed in ATMs. The focus of the article is cash replenishment optimization. After introducing linear programming-based solutions, the authors propose a solution based on dynamic programming. Experiments conducted on real data reveal that the proposed approach can find the optimal solution more efficiently than linear programming.
Article Preview


The increasing use of ATMs facilitates banking services, such as cash withdrawal, for both customer and banks. On the other hand, additional ATM management costs are introduced for banks (Castro, 2009), (Elton, 1974), (Bar-Ilan, 2004). ATM cash replenishment optimization problem mainly aims to lower this cost and focuses on how often and how much cash to be loaded to an ATM in each cash replenishment period. The problem contains two optimization criteria. The first one is that banks aim to reduce the amount of idle cash (i.e. cash that was loaded and was not withdrawn from ATM for a period of time). This amount of cash cannot be utilized in a profitable way; thus, it is considered as a loss. This loss is called interest cost, and it is calculated as an interest lost in terms of the number of days cash stays in ATM idle (Simutis, 2007), (Yao, 2006). On the other hand, cash replenishment incurs loading cost, which involves cash transportation and loading process to an ATM (Berbeglia, 2007), (Agoston, 2016). Hence, it is important to reduce the frequency of replenishment where possible. We call the total cost generated by interest and loading costs as replenishment cost. ATM replenishment optimization is based on keeping these factors balanced. As an additional case, loading small amount of cash causes out-of-cash ATMs and affects customer satisfaction. Within the scope of this work, it is guaranteed that the required amount is always available; hence, out-of cash situation is prevented.

ATM cash replenishment problem can be divided into two steps: forecasting daily amount of withdrawal, and optimizing the cash replenishment schedule. In this work, it is assumed that a reliable money withdrawal forecast is available. For this step, several solutions proposed in the literature can be used (Andrawis, 2016; Teddy, 2011; Ekinci, 2014; Venkatesh, 2014; Kalchschmidt, 2006).

The focus of this work is basically on the second step. Given a reliable forecast for cash withdrawal from ATM, cash replenishment is performed such that, ATM is never out-of-cash, and the schedule of cash replenishment is optimized. Assuming that maximum replenishment frequency is daily, loading only the required amount of daily cash does not create any interest cost while maximizing the loading cost. On the other hand, for the lowest cash loading frequency, such as weekly, the loading cost is minimized, but the interest cost is maximized. Hence, optimization is needed to find a balanced schedule to reduce the overall cost.

There is a limited set of works in the literature that are related to the ATM replenishment problem. The target to optimize and the constraints may vary in the studies. In (Anholt, 2016), the aim is to optimize the cash replenishment routing for loading a set of ATMs on an ATM road network through linear programming (LP). In (Bati, 2017), both the routing and optimum replenishment of a set of ATMs are focused on. Similarly, in (Lazaro, 2018), routing is optimized together with cash management. On the other hand, in (Baker 2013), a simulation-based optimization solution is developed for cash replenishment decision. As one of the few studies working on groups of ATMs, in (Chatoyakul, 2013), mixed integer programming-based approach is developed to solve the cash replenishment problem for a set of ATMs. None of these studies are the same as our problem in terms of object to optimize and constraints. In this work, we introduce the ATM cash replenishment optimization problem which tries to determine the optimum cash loading schedule for a given period for the given interest cost (obtained from the interest rate) and the fixed cash loading cost for each replenishment operation.

For the problem, we firstly present an LP solution, which involves defining the set of constraints as linear equations in order to model the problem, and then solving these equations to determine the optimized cash-loading schedule. Then, by exploiting the analogy to matrix chain problem, we model the ATM cash replenishment problem such that n consecutive days ATM replenishment is considered similarly to the multiplication of a sequence of n matrices. Thus, we develop a dynamic programming solution to the problem.

In (Ozer, 2018), an earlier version of this work is presented. In this paper, we extend the work with LP modeling of the problem and comparison of proposed solution with LP-based solution. Additionally, the solution description and discussions are further enhanced.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing