Collector task
We list the tasks that make up the "task collector":
The features of cities with a labyrinth street building are that between two points it is sometimes faster to walk than to get there by transport. This is typical of the historical centers of modern cities, which are also the centers of attraction for many commercial enterprises and the flow of people, and hence the US.
Thus, if two or more US clusters are in close proximity to each other, then the vertices in which they are located are identified on the graph.
')
Part de facto arcs has common areas. For example, bridges, overpasses and the like. When preparing the graph, you will have to “enter” additional “empty” vertices (for example, vertices at the ends of the bridge to which arcs converge from the vertices of this coast). That is, to perform the operation of adding vertices.
Add vertices at the ends of this edge (bridge, railway crossing, racks, etc.) and connect all the vertices of the graph on both sides with the added vertices.
The 0th step is the Matrix of strong connectivity of the digraph obtained by logical element-wise multiplication of the reachability matrix R (G) by the transposed itself.
This operation allows us to obtain subgraphs equal to strongly related components on which we will subsequently allocate subgraphs-clusters.
And on top you need to get condensate. From the vertices entering the condensate, the operation of merging vertices will be performed.
Specialized Internet services (for example, Yandex.Traffic) provide one or several alternative paths between two points-addresses.
At the same time, part of the arcs between the peaks actually pass through the streets through the addresses of other peaks of the cluster. When preparing the graph, it is possible to exclude alternative paths between such vertices.
The cluster's graph is not always, thus it is transitive since there may not be a closing arc between some vertices.
Despite the fact that all vertices of the graph belong to the plane, the loaded digraph based on city traffic, as a rule, is not Euclidean.
It is easy to observe both the example of the organization of traffic, and in certain periods of the time of day due to significant asymmetric changes in traffic. In the latter case, the rule of the triangle of arc weights, expressed in time from one vertex to another, is significantly violated.
Obviously, if the set of CSS is located in such a way that we can select the number of clusters we need based on the physical limitations of the service of the Network, then we could minimize the cost of maintenance.
In addition, clustering opens up the possibility to load the cassettes of each US of a particular cluster with a forecast of spending a cash balance on one given date, which will be the service date, or even accurate to a time interval of several hours within the work shift during which maintenance occurs.
When calculating the route, the weight of the arc must take into account the likelihood of spending the bills before servicing a particular CA and the time taken to replace the cassettes.
When shifting the organization of the Network maintenance process, the cluster should have the property that the sum of the weights of the Hamiltonian cycles of the graph-cluster cycle should be no more than the maintenance period (hereinafter - Shift), that is, less than or equal to the working Change of one service vehicle's team.
The algorithm includes a preliminary determination of the number of clusters based on the capabilities of the provision of the maintenance process of the Network with special equipment and personnel.
Clusters will have properties important for the future development of the Network, such as “compression” and “stretching”.
The first (“compression”) will take place if initially the primary clusters were sufficiently distant from each other, but as the Network grows, new clusters will appear between the older ones, or the “old” clusters will grow, bringing their borders closer to each other.
The “stretching” property will take place when the clusters grow in opposite directions and the centroids of the clusters “leave” from each other for a longer distance.
Clusters formed on the basis of subgraphs of a weighed digraph will not have clear geographic boundaries, because of the dynamic traffic, a weighted digraph is not Euclidean with modern technology for serving the Network.
The situation may change with the technology of cassette delivery to the CSS. Delivery of cassettes with the help of copters can “transplant” service personnel, for example, on motorcycles capable of changing the weight of the digraph, making the digraph almost Euclidean.
Geographically close points do not necessarily belong to the same cluster, since there may not be a direct path between them with acceptable traffic. However, it is possible that it is possible to walk from one DC to another and this will take an acceptable time.
In this case, perhaps, when preparing a cluster digraph to calculate the solution of the “commanding fighter problem”, not only “transfer” the CSS to the neighboring cluster, but also carry out an operation “identification” of these vertices.
If, due to any processes (for example, a marketing plan), there is a list of points on the map of a settlement, which should be provided in the future, then you should start a business process based on the Strategy and Financial Plan. , especially if it is not possible to purchase large lots of US at a time and you have to buy one by one or small wholesale lots.
The choice of the clustering algorithm is determined by the properties of the space and time of day in which the action unfolds.
The settlements were historically built up on the basis of the most diverse principles, the landscape, the presence of natural and artificial unbearable and intolerable objects, and therefore have a unique network of roads and point objects for the most economically sound allocation of CSS.
As a result, the cluster shape on the map will not have clear boundaries. On the contrary, clusters will “grow hair” with an additional growth of the network due to single additions of CSS. At the same time, these “hairs” of neighboring clusters can “intertwine”.
At the same time, a weighted digraph will not already have such visual properties because of the principle of assigning weights based on the traffic, rather than the physical distances of the roads.
The weights of the digraph can be so dynamic that there is a risk that, with the same given number of clusters, some “boundary” CAs can fall, then into one, then into another neighboring cluster. This should not be allowed, because it creates problems when planning the load of the CSS, since the dates and Service Changes of neighboring clusters may not substantially coincide. Consequently, in a number of such cases, it will be necessary to assign such wandering points to clusters.
The network will be presented in the form of a weighted orgraph based on the traffic received from Internet services such as Yandex.Probki, which will save us from geographical problems and we can choose an algorithm from the family of heuristic graph algorithms.
Each cluster simply must be a connected component in order to find the most optimal solution to the traveling salesman problems. But if the cluster as a graph has the property of strong connectivity, then such a solution will certainly be more optimal.
The solution of the placement problem should achieve not only the goal of maximizing the volume of settlement and cash services for bank customers and commission income, but also the task of minimizing network maintenance costs in the future and, as a result, maximizing profit from using the Network.
Note that there are actually two possible tasks to be solved. So the task of placing new CSS in relation to the existing DH is the task inverse to the task of locating the DH relative to the already existing Network. The found coordinates of the cluster centroids will also show us the most optimal hypothetical arrangement of the color centers of the clusters.
As a rule, the majority of banks in one region have only one DH of the Network and, at some point, when the number of CAs on the Web is already large enough, that traffic becomes a significant factor in the growth of time, it becomes necessary to create additional TSO for individual clusters (or groups), which centroids with the growth of the Network inevitably move away from the only existing AC.
The moment when it is necessary to open an additional central office should consider the moment when the sum of current expenditures on reaching remote clusters (Rtek), the cost of funding increased cash balances for a longer period between service dates (Rfond) exceeds the sum of current expenditures of the additional central office taking into account depreciation of fixed assets and the wage fund and the cost of funding the one-time diversion of resources for the acquisition of these fixed assets.
The bank may face the need to organize an additional CO earlier, when the physical “ceiling” of the further scaling up of the existing CO activity on the growing Network is reached.
In a bank with an evolving Network, there should be a regulation on the placement of a CS in which an element of the business process of passing preliminary examination is fixed if there are simultaneously alternative solutions for placement. If there are no alternatives and the points for placing the CA are given directively, then the examination will not help anything and the cost optimization solution will be further in the “traveling salesman problem”.
Forecasting is based on the following source data:
It is important not to confuse the cassette slots with different bills into each cassette (tuned to a certain denomination of a bill and when changing cassettes in the safe deposit box of an ATM) in order to give an amount of no more than insured for a particular ATM. Technical capabilities Usov assumes loading of 4 cassettes. The standard configuration of the banknote composition (100, 1000, 5000) gives the maximum amount of about 4 million rubles.
We assume that the time between the dates of service of the cluster MS cannot be longer than the period of balance exhaustion in at least one device from this cluster. Even more precisely, the emptying of cassettes CSS charged the most "running" bills of large denominations (1000 and 5000).
Thus, we believe that the loading of individual MSs, taking into account the cluster maintenance schedule, may not reach the maximum possible load sizes, which theoretically gives an additional opportunity to reduce the costs for insurance of funds in a particular ATM. However, this is not true for all ATMs, since the forecast must take into account the existence and features of payroll projects with corporate clients of the bank, namely, the schedule for issuing advances and settlements on the salaries of customer employees. On such dates, nearby to the client, the MS are subject to accelerated desolation.
Therefore, insurance (a contract is concluded for a period) for such ATMs must take into account the peak loads of the spending balance. Therefore, in such cases it will be the maximum possible load and save on insurance will not work on all CSS.
Modern urban traffic is characterized by significant for our purposes, variability and difficult predictability due to accidents, road works, precipitation, and the like.
Already while following the route, the traffic load may suddenly increase sharply and unevenly and, in order not to jeopardize the network, it is necessary to use an operational tool to recalculate and get the “cheapest” route for the remaining number of cluster nodes that have not yet been served.
To improve the computational abilities of the service, it is necessary not only to allocate US clusters (“borderline” USUs can change the “registration”), but also to localize their service by time of day (periods of 8 hours in 3 shifts with round-the-clock organization of the fleet and service personnel ).
For example, servicing a cluster located in the part of the city most affected by traffic jams should be planned for the night shift. In addition, in this case, you probably will not have to recalculate the route of the shortest path, since the graph weights will not change during the entire route. However, on the other hand, there is a sharp increase in criminal risk (the risk of an attack on collectors), which will require an increase in the cost of protecting the crew.
As mentioned above, a technical solution is possible to deliver cash to US by copters. However, this does not solve the problem if people are still needed to physically replace the cassettes. This will affect the cost of the car, since the cashier and security guard will not be able to use a special armored car, but a regular one, only for their delivery to the point of placing the CS.
In order not to solve the problem of forecasting changes in weights in time, we propose an algorithm based on the approach of recalculating the remaining route from the current data on city traffic, residuals in the US, and, therefore, the modified weights of the arcs.
Our approach involves the step-by-step calculation of the route while it is being followed by the dispatch service. In this case, the collectors will not know the next point in the route until it is declared by the dispatcher.
That is, by the end of the service of the next vertex, a new route should be calculated taking into account the changed data on the weights of the arcs without including in the calculation of the already served peaks.
That is, at each step, the route is calculated on (N - m) vertices. To do this, at each step, an operation is performed to eliminate the arc along which the collector car passes at the time of the next calculation (Fig. 1 and 2).
This task finds its application in many areas of activity and financial intermediation is no exception to this rule. We will not repeat here the well-known conditions and limitations of this task. Focus on the features of the solution in the framework of the "task collector."
Obviously, a closed version of the solution of the traveling salesman problem must be implemented, since after a detour of all the routes planned in the route, the extracted cassettes must be delivered to the responsible service center.
Imposed restrictions on the solution:
The requirements of the physical security service on the non-repeatability of the previous route. That is, if during the calculation of the route you get a solution similar to the previous one, then it is discarded and another, closest to the result, is accepted for implementation.
The choice of solution is determined not so much by the accuracy of the result, as by the speed of the algorithm in the “field” conditions on the hardware available to the bank in price and quality.
- selection of the form of the transaction for the acquisition of CSS.
- network clustering. The solution to this problem will give us a certain number of sets of CSS for intraday (intra-shift) service if there are restrictions on the number of vehicles and personnel serving the Network.
- location of the service centers and service centers (hereinafter - DH) The solution to this problem gives a "roadmap" of the development of the Network in time and space.
- forecasting the rate of spending of bills (in terms of nominal values) in the US cluster before loading cassettes with banknotes in order to use up the cash balance by the date and time of the service moment (taking into account the tendencies of population transfer to cashless purchases, seasonality, payroll projects nearby, weather forecast, etc. significant factors) with a given probability.
- calculation of the shortest path (traveling salesman problem).
Preparation of the graph
The features of cities with a labyrinth street building are that between two points it is sometimes faster to walk than to get there by transport. This is typical of the historical centers of modern cities, which are also the centers of attraction for many commercial enterprises and the flow of people, and hence the US.
Thus, if two or more US clusters are in close proximity to each other, then the vertices in which they are located are identified on the graph.
')
Part de facto arcs has common areas. For example, bridges, overpasses and the like. When preparing the graph, you will have to “enter” additional “empty” vertices (for example, vertices at the ends of the bridge to which arcs converge from the vertices of this coast). That is, to perform the operation of adding vertices.
Add vertices at the ends of this edge (bridge, railway crossing, racks, etc.) and connect all the vertices of the graph on both sides with the added vertices.
The 0th step is the Matrix of strong connectivity of the digraph obtained by logical element-wise multiplication of the reachability matrix R (G) by the transposed itself.
This operation allows us to obtain subgraphs equal to strongly related components on which we will subsequently allocate subgraphs-clusters.
And on top you need to get condensate. From the vertices entering the condensate, the operation of merging vertices will be performed.
Specialized Internet services (for example, Yandex.Traffic) provide one or several alternative paths between two points-addresses.
At the same time, part of the arcs between the peaks actually pass through the streets through the addresses of other peaks of the cluster. When preparing the graph, it is possible to exclude alternative paths between such vertices.
The cluster's graph is not always, thus it is transitive since there may not be a closing arc between some vertices.
Despite the fact that all vertices of the graph belong to the plane, the loaded digraph based on city traffic, as a rule, is not Euclidean.
It is easy to observe both the example of the organization of traffic, and in certain periods of the time of day due to significant asymmetric changes in traffic. In the latter case, the rule of the triangle of arc weights, expressed in time from one vertex to another, is significantly violated.
Host clustering
Obviously, if the set of CSS is located in such a way that we can select the number of clusters we need based on the physical limitations of the service of the Network, then we could minimize the cost of maintenance.
In addition, clustering opens up the possibility to load the cassettes of each US of a particular cluster with a forecast of spending a cash balance on one given date, which will be the service date, or even accurate to a time interval of several hours within the work shift during which maintenance occurs.
When calculating the route, the weight of the arc must take into account the likelihood of spending the bills before servicing a particular CA and the time taken to replace the cassettes.
When shifting the organization of the Network maintenance process, the cluster should have the property that the sum of the weights of the Hamiltonian cycles of the graph-cluster cycle should be no more than the maintenance period (hereinafter - Shift), that is, less than or equal to the working Change of one service vehicle's team.
The algorithm includes a preliminary determination of the number of clusters based on the capabilities of the provision of the maintenance process of the Network with special equipment and personnel.
Clusters will have properties important for the future development of the Network, such as “compression” and “stretching”.
The first (“compression”) will take place if initially the primary clusters were sufficiently distant from each other, but as the Network grows, new clusters will appear between the older ones, or the “old” clusters will grow, bringing their borders closer to each other.
The “stretching” property will take place when the clusters grow in opposite directions and the centroids of the clusters “leave” from each other for a longer distance.
Clusters formed on the basis of subgraphs of a weighed digraph will not have clear geographic boundaries, because of the dynamic traffic, a weighted digraph is not Euclidean with modern technology for serving the Network.
The situation may change with the technology of cassette delivery to the CSS. Delivery of cassettes with the help of copters can “transplant” service personnel, for example, on motorcycles capable of changing the weight of the digraph, making the digraph almost Euclidean.
Geographically close points do not necessarily belong to the same cluster, since there may not be a direct path between them with acceptable traffic. However, it is possible that it is possible to walk from one DC to another and this will take an acceptable time.
In this case, perhaps, when preparing a cluster digraph to calculate the solution of the “commanding fighter problem”, not only “transfer” the CSS to the neighboring cluster, but also carry out an operation “identification” of these vertices.
If, due to any processes (for example, a marketing plan), there is a list of points on the map of a settlement, which should be provided in the future, then you should start a business process based on the Strategy and Financial Plan. , especially if it is not possible to purchase large lots of US at a time and you have to buy one by one or small wholesale lots.
The choice of the clustering algorithm is determined by the properties of the space and time of day in which the action unfolds.
The settlements were historically built up on the basis of the most diverse principles, the landscape, the presence of natural and artificial unbearable and intolerable objects, and therefore have a unique network of roads and point objects for the most economically sound allocation of CSS.
As a result, the cluster shape on the map will not have clear boundaries. On the contrary, clusters will “grow hair” with an additional growth of the network due to single additions of CSS. At the same time, these “hairs” of neighboring clusters can “intertwine”.
At the same time, a weighted digraph will not already have such visual properties because of the principle of assigning weights based on the traffic, rather than the physical distances of the roads.
The weights of the digraph can be so dynamic that there is a risk that, with the same given number of clusters, some “boundary” CAs can fall, then into one, then into another neighboring cluster. This should not be allowed, because it creates problems when planning the load of the CSS, since the dates and Service Changes of neighboring clusters may not substantially coincide. Consequently, in a number of such cases, it will be necessary to assign such wandering points to clusters.
The network will be presented in the form of a weighted orgraph based on the traffic received from Internet services such as Yandex.Probki, which will save us from geographical problems and we can choose an algorithm from the family of heuristic graph algorithms.
Each cluster simply must be a connected component in order to find the most optimal solution to the traveling salesman problems. But if the cluster as a graph has the property of strong connectivity, then such a solution will certainly be more optimal.
Placement of CSS and DH Networks
The solution of the placement problem should achieve not only the goal of maximizing the volume of settlement and cash services for bank customers and commission income, but also the task of minimizing network maintenance costs in the future and, as a result, maximizing profit from using the Network.
Note that there are actually two possible tasks to be solved. So the task of placing new CSS in relation to the existing DH is the task inverse to the task of locating the DH relative to the already existing Network. The found coordinates of the cluster centroids will also show us the most optimal hypothetical arrangement of the color centers of the clusters.
As a rule, the majority of banks in one region have only one DH of the Network and, at some point, when the number of CAs on the Web is already large enough, that traffic becomes a significant factor in the growth of time, it becomes necessary to create additional TSO for individual clusters (or groups), which centroids with the growth of the Network inevitably move away from the only existing AC.
The moment when it is necessary to open an additional central office should consider the moment when the sum of current expenditures on reaching remote clusters (Rtek), the cost of funding increased cash balances for a longer period between service dates (Rfond) exceeds the sum of current expenditures of the additional central office taking into account depreciation of fixed assets and the wage fund and the cost of funding the one-time diversion of resources for the acquisition of these fixed assets.
The bank may face the need to organize an additional CO earlier, when the physical “ceiling” of the further scaling up of the existing CO activity on the growing Network is reached.
In a bank with an evolving Network, there should be a regulation on the placement of a CS in which an element of the business process of passing preliminary examination is fixed if there are simultaneously alternative solutions for placement. If there are no alternatives and the points for placing the CA are given directively, then the examination will not help anything and the cost optimization solution will be further in the “traveling salesman problem”.
The task of forecasting the consumption of bills
Forecasting is based on the following source data:
- Operational data from the system about the current rate of expenditure of bills.
- Historical data and the probability of the implementation of the forecast for the next period of time between the dates of service of the self-service device.
It is important not to confuse the cassette slots with different bills into each cassette (tuned to a certain denomination of a bill and when changing cassettes in the safe deposit box of an ATM) in order to give an amount of no more than insured for a particular ATM. Technical capabilities Usov assumes loading of 4 cassettes. The standard configuration of the banknote composition (100, 1000, 5000) gives the maximum amount of about 4 million rubles.
We assume that the time between the dates of service of the cluster MS cannot be longer than the period of balance exhaustion in at least one device from this cluster. Even more precisely, the emptying of cassettes CSS charged the most "running" bills of large denominations (1000 and 5000).
Thus, we believe that the loading of individual MSs, taking into account the cluster maintenance schedule, may not reach the maximum possible load sizes, which theoretically gives an additional opportunity to reduce the costs for insurance of funds in a particular ATM. However, this is not true for all ATMs, since the forecast must take into account the existence and features of payroll projects with corporate clients of the bank, namely, the schedule for issuing advances and settlements on the salaries of customer employees. On such dates, nearby to the client, the MS are subject to accelerated desolation.
Therefore, insurance (a contract is concluded for a period) for such ATMs must take into account the peak loads of the spending balance. Therefore, in such cases it will be the maximum possible load and save on insurance will not work on all CSS.
The task of interpreting traffic data for the weights of the arcs and vertices of the graph. Preparing a graph to calculate the route
Modern urban traffic is characterized by significant for our purposes, variability and difficult predictability due to accidents, road works, precipitation, and the like.
Already while following the route, the traffic load may suddenly increase sharply and unevenly and, in order not to jeopardize the network, it is necessary to use an operational tool to recalculate and get the “cheapest” route for the remaining number of cluster nodes that have not yet been served.
To improve the computational abilities of the service, it is necessary not only to allocate US clusters (“borderline” USUs can change the “registration”), but also to localize their service by time of day (periods of 8 hours in 3 shifts with round-the-clock organization of the fleet and service personnel ).
For example, servicing a cluster located in the part of the city most affected by traffic jams should be planned for the night shift. In addition, in this case, you probably will not have to recalculate the route of the shortest path, since the graph weights will not change during the entire route. However, on the other hand, there is a sharp increase in criminal risk (the risk of an attack on collectors), which will require an increase in the cost of protecting the crew.
As mentioned above, a technical solution is possible to deliver cash to US by copters. However, this does not solve the problem if people are still needed to physically replace the cassettes. This will affect the cost of the car, since the cashier and security guard will not be able to use a special armored car, but a regular one, only for their delivery to the point of placing the CS.
In order not to solve the problem of forecasting changes in weights in time, we propose an algorithm based on the approach of recalculating the remaining route from the current data on city traffic, residuals in the US, and, therefore, the modified weights of the arcs.
Our approach involves the step-by-step calculation of the route while it is being followed by the dispatch service. In this case, the collectors will not know the next point in the route until it is declared by the dispatcher.
That is, by the end of the service of the next vertex, a new route should be calculated taking into account the changed data on the weights of the arcs without including in the calculation of the already served peaks.
That is, at each step, the route is calculated on (N - m) vertices. To do this, at each step, an operation is performed to eliminate the arc along which the collector car passes at the time of the next calculation (Fig. 1 and 2).
Features of the solution of the "traveling salesman problem"
This task finds its application in many areas of activity and financial intermediation is no exception to this rule. We will not repeat here the well-known conditions and limitations of this task. Focus on the features of the solution in the framework of the "task collector."
Obviously, a closed version of the solution of the traveling salesman problem must be implemented, since after a detour of all the routes planned in the route, the extracted cassettes must be delivered to the responsible service center.
Imposed restrictions on the solution:
The requirements of the physical security service on the non-repeatability of the previous route. That is, if during the calculation of the route you get a solution similar to the previous one, then it is discarded and another, closest to the result, is accepted for implementation.
The choice of solution is determined not so much by the accuracy of the result, as by the speed of the algorithm in the “field” conditions on the hardware available to the bank in price and quality.
Source: https://habr.com/ru/post/350510/
All Articles