 ICACT20220009 Slide.01
[Big Slide]
|
Chrome  Click!! |
 |
Hi everybody, my name is Tao Bai. For ICACT 2022, I have cooperated with partners from ICBC Jiecong Tang and HUST Shipeng Wang, Songfeng Lu, Jing Xiong. Our presentation today is about a solution for ATM replenishment optimization problem |
| ICACT20220009 Slide.02
[Big Slide]
|
Chrome Click!! |
 |
In the banking industry, cash management refers to the
overall management of the cash under the jurisdiction of
the bank, and the rational distribution of the cash share of
each bank branch and each banknote addition device, so
as to maximize the efficiency of bank cash use and bank
revenue. |
| ICACT20220009 Slide.03
[Big Slide]
|
Chrome Click!! |
 |
Since the ATM cash demand in the cash addition
planning problem is dynamic and random, the solution to this
problem is often divided into two steps, cash forecast and
cash distribution planning. Here we mainly considering the latter and regard the former as a known result by making use of the history data.So what does the bank what to get by using forecasted cash amount and other history data? |
| ICACT20220009 Slide.04
[Big Slide]
|
Chrome Click!! |
 |
How to solve this problem?
Firstly, This problem belongs to a large-scale combinatorial optimization problem.
Based above,we attempt to solve this large-scale problem by using heuristic optimization method.
|
| ICACT20220009 Slide.05
[Big Slide]
|
Chrome Click!! |
 |
Since the current situation is complicated, we must make some problem hypothesis to build the mathmatics model.
|
| ICACT20220009 Slide.06
[Big Slide]
|
Chrome Click!! |
 |
hypothesis1:The state of lack of cash and full cash is judged by the state of the cash box at the time when the cash refilling vehicle arrives at the ATM and when the refilling vehicle ends its day trip.
hypothesis2:Compared with the capacity of the cash box, the capacity of the cash-replenish car is infinite.
other hypothesis include... |
| ICACT20220009 Slide.07
[Big Slide]
|
Chrome Click!! |
 |
Now we start to build the objective function. Based the on the current situation, the objection include 4 parts, thus the punish cost of cash-shortage, punish cost of cash-full , punish cost of cash utilization rate and driving routes cost.
|
| ICACT20220009 Slide.08
[Big Slide]
|
Chrome Click!! |
 |
The cost of money shortage.
If the ATM is in the moneyadding plan, the penalty cost is calculated by judgingwhether the ATM is short of money at two time points,which are when the money adding vehicle arrives at the
ATM and after the effective deposit and withdrawal time
of the day;
if the ATM is not adding money In the plan,it is only judged whether there is a shortage of moneyafter the effective deposit and
withdrawal time on thatday, and the penalty cost is calculated. |
| ICACT20220009 Slide.09
[Big Slide]
|
Chrome Click!! |
 |
The full currency cost. The calculation is similar to the
lack of currency cost, the total full currency cost of all
P sets in the period T is ... |
| ICACT20220009 Slide.10
[Big Slide]
|
Chrome Click!! |
 |
The cost of cash utilization rate. The cost of cash utilization rate is calculated according to the average cash utilization rate of node p in period T. The total cash utilization rate cost of all P collections in period T is ... |
| ICACT20220009 Slide.11
[Big Slide]
|
Chrome Click!! |
 |
The routing cost is calculated based on the mileage charged. The calculation formula of the road cost is ,,,
Where cij is the travel distance from point i to point j; xd
ij is a decision variable. If the banknote adding route
passes (i, j) on the d day, the value is 1, otherwise it is
0. |
| ICACT20220009 Slide.12
[Big Slide]
|
Chrome Click!! |
 |
Since we have gave some problem hypothesis in front, here we should
regard this hypothesis as constraints of variable in objective function, the constraint mainly include: |
| ICACT20220009 Slide.13
[Big Slide]
|
Chrome Click!! |
 |
The heuristic optimization algorithm we take to solve this problem include three class, respectively the genetic algorithm(GA),the particle swarm optimization algorithm(PSO) and the Simulated annealing(SA).
|
| ICACT20220009 Slide.14
[Big Slide]
|
Chrome Click!! |
 |
Based on above, we put forward an improved genetic particle swarm simulated annealing algorithm (IGAPSOSA). The algorithm is divided into three stages.
|
| ICACT20220009 Slide.15
[Big Slide]
|
Chrome Click!! |
 |
From now on , we will introduce the concrete solving process.
Firstly, we should encode the ATM machine serverd pattern.
By encoding, the Pat can represent that which ATM machines shoud be replenished on some days and which not be replenished on other days.
|
| ICACT20220009 Slide.16
[Big Slide]
|
Chrome Click!! |
 |
Aftering encoding, we can formally execute the algorithm.
The first algorithm we take is GA.
To execute GA, firstly we should make a population initialization like the PPT shows.
|
| ICACT20220009 Slide.17
[Big Slide]
|
Chrome Click!! |
 |
After the initial population action,we will do the cross operation.
Here we choose two ATM patterns from two individuals as a example
to introduce the cross operation process.The cross operation process of the whole ATM patterns is similar.
|
| ICACT20220009 Slide.18
[Big Slide]
|
Chrome Click!! |
 |
After the cross operations, we will do the mutation operation, here we also choose one ATM pattern from one individual as a example, here the mutation location of the ATM pattern is the third and the sixth as the PPT shows.
After the above operation( Population initialization, cross operation, mutation operation), we will do the selection by using tournament mechanism with tournament operator K=2.
For each tournament, K individuals will be randomly selected from the population P, and the best individual will be selected as the parent of the next generation after the fitness comparison. |
| ICACT20220009 Slide.19
[Big Slide]
|
Chrome Click!! |
 |
After carrying out the GA algorithm, we will regard the GA's result
as the input of PSO algorithm.
A typical PSO algorithm is like this picture shows.
The different individuals update their locations step by step by using the information of the global best and local best to reach the best global location, |
| ICACT20220009 Slide.20
[Big Slide]
|
Chrome Click!! |
 |
For our problem, we can see the PSO process like this: |
| ICACT20220009 Slide.21
[Big Slide]
|
Chrome Click!! |
 |
After the PSO operation, we will make the PSO results as the input of the SA algorithm.
SA Neighbor solution Search
We propose a selection algorithm based on roulette. The algorithm generates neighbor solutions based on the information of the lack of cash matrix and the full cash matrix . The process is described as follows:
|
| ICACT20220009 Slide.22
[Big Slide]
|
Chrome Click!! |
 |
Following up last PPT, we randomly select a processing operator from the three constructed processing operators to act on ATM machine to obtain a new neighbor solution and return.
Among them, the processing operator is described as:
|
| ICACT20220009 Slide.23
[Big Slide]
|
Chrome Click!! |
 |
Here we do the experiments.
Take a bank as an example——The bank manages 72 ATM machines and uses the above-mentioned IGAPSOSA algorithm for cash replenish plan.
The parameter setting is like the PPT shows. |
| ICACT20220009 Slide.24
[Big Slide]
|
Chrome Click!! |
 |
Table I is the average weekly data statistics of each algorithm in the data set. By comparing the total cost value,the IGAPSOSA algorithm is better than other algorithms, and the total cost of the GAPSO algorithm is reduced by 76.49.
The number of shortages is also the best, which is better than GAPSO. The number of shortages is 0.9 times less.
|
| ICACT20220009 Slide.25
[Big Slide]
|
Chrome Click!! |
 |
Table II is a comparison between the best result of the IGAPSOSA algorithm and the result of manual decision in a selected period. The total cost value of the IGAPSOSA algorithm is 1005.522 less than the cost value of manual decision, the number of shortages is 2 times less, and the cash utilization rate is not up to the standard. The number is less than 8. It can be seen that there are more unqualified numbers of cash utilization rate in manual decision-making.
|
| ICACT20220009 Slide.26
[Big Slide]
|
Chrome Click!! |
 |
Now let's make a conclution.
To solve the ATM replenishment optimization problem, we put forward a hybrid genetic algorithm ——IGAPSOSA，which exceed any single heuristic algorithm.
The results show that the proposed algorithm reduces the total cost of GA by 8 %, reducing the total cost of PSO by 53.6%.
The results have a more than 50% promotion compared with artificial selection, and it make the cash replenish business more automation and Intelligent.
|
| ICACT20220009 Slide.27
[Big Slide]
|
Chrome Click!! |
 |
The end, Thank you for listening!
Any questions of better suggest?
|
