Screwing on AI: optimizing ATM operation

Tomcat

Professional
Messages
2,661
Reputation
10
Reaction score
652
Points
113
Hi all! This is a short story about how the team of the Big Data and Artificial Intelligence Competence Center at LANIT optimized the operation of the ATM network. The emphasis in the article is not on describing the selection of parameters and choosing the best forecasting algorithm, but on considering the concept of our approach to solving the problem. Anyone interested, welcome to cat.

Banks lose quite a lot of money because it just sits in ATMs. Instead, the money could be successfully invested and receive income. Today, large banks with strong analytical centers have their own solutions in order to calculate the number of banknotes and the time for which they need to be deposited in ATMs before the next collection. Small players, without such decisions, simply focus on the average values obtained during previous trips of collectors.

Thus, the formal formulation of the problem looks like this.

At the entrance:
  • there is a history of withdrawing/receiving cash from ATMs (in our case, this was data for a year and a half);
  • the cost of losses from finding money in ATMs (from idle stocks) depends on the refinancing rate (parameter q ); the cost can be estimated as
    $S*X*(\frac{q}{365})$
    , where S is the amount, X is the number of days;
  • cost of travel for collectors, si (changes over time and depends on the location of the ATM and the route of collectors).

The output is expected to be:
  • a system of recommendations on the number of bills and the time for which they need to be deposited;
  • economic effect of the proposed solution.

The development was carried out jointly with @vladbalv , from whom many proposals were received, including key ones that formed the basis of the described solution.

The general idea is based on finding the minimum cost as a function of the number of days between collections. To explain the final solution, you can first consider a simplified version - under the assumption that the amount of money withdrawn does not change from day to day and is equal to S , and that it only decreases. In this case, the amount of money in the ATM is a decreasing arithmetic progression.

Let's assume that S rubles are withdrawn per day. In addition to the amount of withdrawals, we will also introduce the variable X - the number of days between collections, changing which we will further search for the bank’s minimum costs. It is logical that the amount that is most profitable to put into an ATM, knowing that collection will be in X days, is S*X . With this approach, the day before collection there will be S rubles in the ATM, two days - 2*S rubles, three days - 3*S rubles. etc. In other words, our series can be considered moving from end to beginning, then it will be an increasing arithmetic progression. Therefore, during the period between two collections, the ATM will have (S+S*X)/2 rubles. Now, based on the refinancing rate, all that remains is to calculate the cost of idle stocks of this amount for X days and additionally add the cost of completed collection trips. If there are X days between collections, then collections will be completed in n
$[\frac{n}{X}]+1$
days (where
$[\frac{n}{X}]$
is an integer division), since you will have to come one more time to withdraw the rest of the money.

So the resulting function looks like this:

$TotalCost(S, X, n, q, si) = (S + S*X)/2*\frac{q}{365}+si*([\frac{n}{X}]+1)$


Where:
  • S —amount of withdrawals, rub./day,
  • X is the number of days between collections,
  • n is the period under consideration in days,
  • q — refinancing rate,
  • si is the cost of collection.

However, in reality, different amounts are withdrawn every day, so we have a series of withdrawals/deposits of bills, and every day this series is replenished with new values. If we take this into account, the function will take the following form:

$TotalCost = \sum_{i=1}^{n}Q_{i}*\frac{q}{365} + si*([\frac{n}{X}]+1) \\ q - bet\ , refinancing, \\ n - number\, considered\, days, \\ X - number\, days\, between\, collections, \\ Q_{i} - amount\, in\, ATM\, on\, i-th \, day,\, Q_{i} = encash_{i} - \sum_{k=[\frac{i}{X}]*X}^{i}S_{k} \\ S_{k} - change \, amount\, in\, ATM\, on\, kth\, day, \\ encash_{i} - amount\, last\, on\, i-th\, day\, collection, \\ encash_{i} = \begin{cases} \sum_{k=[\frac{i}{X}]*X}^{([\frac{i}{X}]*X+1)*X}S_{k}, \ ,\,\, if\,sum\, decreasing \\ \\ \sum_{k=[\frac{i}{X}]*X}^{[\frac{i}{X}]*X+3 }S_{k}^{-}, \,\,\, if\,amount\, increasing \end{cases} \\ S_{k}^{-} - amount\, withdrawals\, for\, kth\ , day\\$


What are decreasing and increasing amounts: depending on whether you deposit more or withdraw more, there are bills for which the amount in the ATM accumulates, and there are bills for which the amount in the ATM decreases. In this way, increasing and decreasing amounts of banknotes are formed. In the implementation, three rows were made: incr_sums - increasing bills, decr_sums - decreasing bills and withdrawal_sums - a series of ATM withdrawal amounts (there are bills that are only used for withdrawal).

Also an important point: if the amount is increasing, then we do not need to pledge the entire amount of the whole series; this must be done only for decreasing amounts, since they should completely disappear by the end of the collection period. For increasing amounts, we decided to set aside an amount for three days as a safety net in case something goes wrong.

Among other things, to apply the described function, you need to consider the following points.
  • The most important, complex, and interesting thing is that at the time of collection, we do not know what the amounts will be; they need to be predicted (more on this below).
  • ATMs are of the following types:
    ○ only for deposit/take-out,
    ○ for deposit and take-out at the same time,
    ○ for deposit and take-out at the same time + recycling (due to recycling, the ATM has the ability to issue banknotes that other clients deposit into it).
  • The described function also depends on n , the number of days considered. If we take a closer look at this dependence using real examples, we get the following picture:

aab0478a4d7367d2523375dd0b690012.png

Rice. 1. TotalCost function values depending on X (Days betw incas) and n (Num of considered days)

To get rid of n, you can use a simple trick - just divide the function value by n . In this case, we average and get the average cost of expenses per day. Now the cost function depends only on the number of days between collections. This is exactly the parameter by which we will minimize it.

Given the above, the actual function would have the following template:

TotalCost(n, x, incr_sums, decr_sums, withdrawal_sums, si) where
  • x — maximum number of days between collections
  • n is the number of days that we are tracking, that is, we look at the last n values of the time series supplied as input (as written above, the function does not depend on n , this parameter was added so that we can experiment with the length of the supplied time series)
  • incr_sums — a series of predicted amounts for banknotes only for deposits,
  • decr_sums — a series of predicted amounts for take-out banknotes only,
  • withdrawal_sums — a series of predicted amounts of ATM withdrawals (i.e. here the amount for banknotes in minus the amount for out), filled in with 0 for all ATMs except recycling ones,
  • si is the cost of collection.

The function traverses the input rows with a disjoint window of size X and counts the amounts of money deposited inside the window. Unlike the original function, the sum of the arithmetic progression here turns into a regular sum (this is the amount that was deposited during collection). Next, inside the window, in a cycle by day, there is a cumulative summation/subtraction of the amounts that were deposited/withdrawn from the ATM daily. This is done in order to get the amount that was in the ATM for each day.

Then, from the received amounts, using the refinancing rate, the cost of costs for idle inventories is calculated, and at the end the costs of collection trips are added.

Implementation
Code:
def process_intervals(n, x, incr_sums, decr_sums, withdrawal_sums):

# generator for the number of amounts that

# remain in the ATM every day

# incr_sums - a series of increasing amounts

# decr_sums - a series of decreasing sums

# withdrawal_sums - a number of ATM withdrawal amounts (there are bills that are only used for withdrawal)

# filled in with 0 for all ATMs except recycling ones

# x — number of days between collections

# n - number of days we are tracking

if x>n: return

for i in range(n//x):

decr_interval = decr_sums[i*x:i*x+x]

incr_interval = incr_sums[i*x:i*x+x]

withdrawal_interval = withdrawal_sums[i*x:i*x+x]

interval_sum = np.sum(decr_interval)

interval_sum += np.sum(withdrawal_interval[:3])

for i, day_sum in enumerate(decr_interval):

interval_sum -= day_sum

interval_sum += incr_interval[i]

interval_sum += withdrawal_interval[i]

yield interval_sum
     
# balance of amounts. The whole interval is taken.

# but yield only for the rest of the row

decr_interval = decr_sums[(n//x)*x:(n//x)*x+x]

incr_interval = incr_sums[(n//x)*x:(n//x)*x+x]

withdrawal_interval = withdrawal_sums[(n//x)*x:(n//x)*x+x]

interval_sum = np.sum(decr_interval)

interval_sum += np.sum(withdrawal_sums[:3])

for i, day_sum in enumerate(decr_interval[:n-(n//x)*x]):

interval_sum -= day_sum

interval_sum += incr_interval[i] 

interval_sum += withdrawal_sums[i]

yield interval_sum

def waiting_cost(n, x, incr_sums, decr_sums, withdrawal_sums, si):

# incr_sums - a series of increasing amounts

# decr_sums - a series of decreasing sums

# withdrawal_sums - a number of ATM withdrawal amounts (there are bills that are only used for withdrawal)

# filled in with 0 for all ATMs except recycling ones

 # si — cost of collection

 # x — number of days between collections

 # n is the number of days that we are tracking

assert len(incr_sums)==len(decr_sums)

q = 4.25/100/365

processed_sums = list(process_intervals(n, x, incr_sums, decr_sums, withdrawal_sums))

 # waiting_cost = np.sum(processed_sums)*q + si*(x+1)*n//x

waiting_cost = np.sum(processed_sums)*q + si*(n//x) + si

 # divide by n to get the average amount per day (independent of the number of days)

return waiting_cost/n

def TotalCost (incr_sums, decr_sums, withdrawal_sums, x_max=14, n=None, si=2500):

# x — number of days between collections

# n is the number of days that we are tracking

assert len(incr_sums)==len(decr_sums) and len(decr_sums)==len(withdrawal_sums)

X = np.arange(1, x_max)

if n is None: n=len(incr_sums)

incr_sums = incr_sums[-n:]

decr_sums = decr_sums[-n:]
    
withdrawal_sums = withdrawal_sums[-n:]

waiting_cost_sums = np.zeros(len(X))

for i, x in enumerate(X):

waiting_cost_sums[i] = waiting_cost(n, x, incr_sums, decr_sums, withdrawal_sums, si)

return waiting_cost_sums

Now we apply this function to the historical data of our ATMs and get the following picture:

5ad87f6135850ef14fed4a8100dce2b0.png

Rice. 2. The optimal number of days between collections.

Sharp changes in some graphs are explained by gaps in the data. And the fact that they happened at the same time can most likely be explained by technical work, during which the ATMs were not working.

Next, you need to make a forecast for cash withdrawals/deposits, apply this function to it, find the optimal collection day and load a certain number of bills according to the forecast made.

Depending on the amount of money in circulation (the less money passes through the ATM, the longer the optimal collection period), the number of optimal days between collections changes. There are cases when this number is more than 30. A forecast for such a long period of time will be too big a mistake. Therefore, historical data is first estimated if it is less than 14 days (this value was chosen empirically because the optimal number of days before collection for most ATMs is less than 14 days, and also because the longer the forecast horizon, the greater its error), then in the future, to determine the optimal number of days between collections, a forecast based on a time series is used, otherwise, using historical data.

I will not dwell in detail on how the forecast of withdrawals and deposits is made. If you are interested in this topic, you can watch a video report on how researchers from Sberbank solved a similar problem (Data Science using the example of managing a bank’s ATM network).

Of everything we tested, CatBoostRegressor performed best; the regressors from sklearn were slightly behind in quality. Perhaps, an important role here was played by the fact that after all the filtering and separation of the validation set, only a few hundred objects remained in the training set.

Prophet performed poorly. We didn’t try SARIMA because it had bad reviews in the video above.

Features used (there were 139 in total, after the feature its designation is given in the feature importance graph below)
  • Time lags of the target values of the variable, lag_* (their number can be varied, but we settled on 31. In addition, if we want to forecast not a day ahead, but a week, then the first lag looks not for yesterday, but for a week ago. Thus, the furthest we looked was 31+14=45 days ago).
  • Deltas between lags, delta_lag*-lag*.
  • Polynomial characteristics of lags and their deltas, lag_*^* (only the first 5 lags and their deltas were used and designated).
  • Day of the week, month, month number, weekday, day, month (categorical variables).
  • Trigonometric functions from time values from the point above, weekday_cos, etc.
  • Statistics (max, var, mean, median) for the same day of the week, month, weekday_max, weekday_mean,... (only days earlier than the one considered in the training set were taken).
  • Binary indicators of weekends when ATMs are closed, is_weekend
  • Values of the target variable for the same day of the previous week/month, y_prev_week, y_prev_month.
  • Double exponential smoothing + smoothing based on the values of the objective function for the same days of the previous week/month, weekday_exp_pred, monthday_exp_pred.
  • We tried tsfresh, tsfresh+PCA, but then abandoned it, because there were a lot of these features, and we had few objects in the training set.

The importance of the features for the model is as follows (a model is given for predicting the withdrawal of a 1000 ruble banknote one day in advance):

b389bd5fdee92ec1b491c59189ea4f46.png

Rice. 3. Feature importance of the used features

Conclusions from the pictures above - the greatest contribution was made by lagged features, deltas between them, polynomial features and trigonometric functions of date/time. It is important that in its prediction the model does not rely on any one feature, and the importance of the features decreases evenly (the right side of the graph in Fig. 2).

The forecast graph itself looks like this (days are plotted along the x- axis , the number of bills is plotted along the y- axis ):

d531f70b43dc7bbfa74bb34517421647.png

Rice. 4 — CatBoostRegressor forecast

It shows that CatBoost still poorly identifies peaks (despite the fact that during preprocessing the outliers were replaced by the 95th percentile), but it catches the general pattern, although gross errors also occur, as in the example of a dip in the region sixty days.

The MAE error there fluctuates in the approximate range from several tens to one hundred. The success of the forecast is highly dependent on the specific ATM. Accordingly, the magnitude of the real error is determined by the denomination of the banknote.

The general work pipeline looks like this (all values are recalculated once a day).
  1. For each banknote of each atm there is a different model for each forecasted day (since forecasting a day ahead and a week ahead are different things and withdrawals for different banknotes also vary greatly), so there are about 100 models for each ATM.
  2. Based on the historical data of the ATM, using the TotalCost function , the optimal number of days before collection is found.
  3. If the found value is less than 14 days, then the next day of collection and the pledged amount are selected according to the forecast, which is put into the TotalCost function , otherwise according to historical data.
  4. Based on the forecast or historical data of cash withdrawals/deposits, the amount that needs to be pledged is calculated (i.e., the number of banknotes to be pledged).
  5. The amount + error is entered into the ATM.
  6. Mistake: when depositing money into an ATM, you need to deposit more money, leaving a cushion in case people suddenly want to cash out their savings (in order to transfer them into something more valuable). As this amount, you can take the average withdrawals over the last 2-3 days. In a more complicated version, you can predict withdrawals for the next 2-3 days and additionally deposit this amount (the choice of option depends on the quality of the forecast at a particular ATM)
  7. Now, with each new day, the values of real withdrawals come, and the optimal collection day is recalculated. The closer the collection day, obtained according to the preliminary forecast, the more real data we put into TotalCost instead of the forecast, and the accuracy of the work increases.

We calculated the resulting profit as follows: we took data on withdrawals/deposits for the last three months and from this period on a daily basis, as if we received daily data from ATMs.

For these three months, we calculated the cost of idle cash reserves and collection trips for historical data and for the result of our system. It turned out to be a profit. The daily average values are shown in the table below (the names of ATMs are replaced with Latin characters):

atmprofit (relative)≈profit /day (rub.)
a0.61367
b0.68557
With0.70470
d0.79552
e-0.30-66
f0.49102
g0.41128
h0.4998
i0.34112
j0.48120
k-0.01-2
l-0.43-26
m0.12734
n-0.03-4
o-0.21-57
p0.1424
q-0.21-37

Approaches and improvements that are interesting to consider, but have not yet been implemented in practice (due to the complexity of their implementation and time constraints):
  • use neural networks for forecasting, perhaps even an RL agent,
  • use one model, simply feeding it an additional attribute responsible for the forecast horizon in days.
  • build embeddings for ATMs that aggregate information about geography, location traffic, proximity to stores/shopping centers, etc.
  • if the optimal collection day (at the second step of the pipeline) exceeds 14 days, calculate the optimal collection day according to the forecast of another model, for example, Prophet, SARIMA, or take for this purpose not historical data, but historical data for the forecast period from last year / averaged over the last some years.
  • For ATMs that have a negative profit, you can try setting up various triggers, when triggered, the ATMs are operated in the old mode, or collection trips are made more often/less frequently.

In conclusion, it can be noted that the time series of cash withdrawals/deposits are predictable, and that in general the proposed approach to optimizing the operation of ATMs is quite successful. With a rough estimate of the current work results, it turns out to save about 2,400 rubles per day, respectively, per month this is 72 thousand rubles, and per year - about 0.9 million rubles. Moreover, the greater the amount of money in circulation at the ATM, the greater the profit that can be achieved (since for small amounts the profit is offset by the error from the forecast).

for valuable advice in preparing the article. Thank you for your attention!
 
Top