Collector task

We list the tasks that make up the "collector task":

  • the choice 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 DC sets for intraday (intra-shift) service if there are restrictions on the number of cars and personnel serving the Network.
  • deployment of CSS and service centers (hereinafter - CH) Networks. The solution to this problem provides a “road map” for the development of the Network in time and space.
  • predicting the rate of spending of bills (in the context of denominations) in the CA cluster before loading cassettes with banknotes in order to use up the cash balance by the date and time of service (taking into account the population’s transition to cashless payments for purchases, seasonality, salary projects nearby, weather forecasts, and the like significant factors) with a given probability.
  • shortest path calculation (salesman problem).

Count preparation


The peculiarities of cities with labyrinthine street development are that between two points it is sometimes faster to walk than to reach by transport. This is characteristic of the historical centers of modern cities, which are also centers of attraction for many trading enterprises and flows of people, and hence the CSS.

Thus, if two or more CSS clusters are in close proximity to each other, then the vertices in which they are located on the graph are identified.

Part of the arcs de facto has common areas. For example, bridges, flyovers and the like. In preparing the graph, you will have to “enter” additional “empty” peaks (for example, peaks at the ends of the bridge to which arcs converge from the peaks of this shore). That is, carry out the operation of adding vertices.

Add the vertices at the ends of this rib (bridge, railway crossing, overpass, etc.) and connect all the vertices of the graph on both sides with the added vertices.

The 0th step is the Strong Connect Matrix of the digraph obtained by the logical element-wise multiplication of the reachability matrix R (G) by the transposed self.

This operation allows us to obtain subgraphs equal to strongly connected components on which we will subsequently select cluster subgraphs.

And to top it off, you need to get condensate. From the vertices entering the condensate, the operation of merging the vertices will be performed.

Specialized Internet services (for example, Yandex. Traffic) provide one or more alternative paths between two address points.

At the same time, part of the arcs between the vertices actually pass through the streets through the addresses of other vertices of the cluster. In preparing the graph, alternative paths between such vertices may need to be excluded.

The cluster digraph is not always, thus it is transitive, since there may not be a closing arc between some vertices.

Despite the fact that all the vertices of the graph belong to a plane, a loaded digraph based on urban traffic, as a rule, is not Euclidean.

You can easily observe both the example of the organization of traffic and at certain periods of the day due to significant asymmetric changes in traffic. In the latter case, the rule of triangle of the weights of arcs expressed in time of reaching from one vertex to another is substantially violated.

Host Clustering


Obviously, if the set of DCs are located so that we can select the number of clusters we need based on the physical limitations of the network, then we could minimize the cost of maintenance.

In addition, clustering opens up the possibility of loading cassettes of each DC of a particular cluster with a forecast of the remaining cash balance on one given date, which will be the date of service, or even accurate to a time period of several hours inside the work shift during which the service takes place.

When calculating the route, the weight of the arc should take into account the probability of spending bills before servicing a particular CSS and the time taken to replace the cartridges.

During the shift organization of the Network maintenance process, the cluster must have the property according to which the sum of the weights of the arcs of the Hamiltonian cycle of the graph-cluster should be no more than the time of the service period (hereinafter referred to as the Change), i.e. less than or equal to the working Change of the team of one serving vehicle.

The algorithm includes a preliminary determination of the number of clusters based on the capabilities of the network maintenance process with special equipment and personnel.
Clusters will possess properties important for the future development of the Network, for example, 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, either new clusters will appear between the “older” ones, or the “old” clusters will grow closer to each other with their boundaries.

The “stretching” property will take place when the clusters grow in opposite directions and the centroids of the clusters “go away” from each other at further distances.
Clusters formed on the basis of subgraphs of a weighted digraph will not have clear geographical boundaries, because due to dynamic traffic, a weighted digraph is not Euclidean with modern technology for servicing the Network.

The situation may change along with the technology of cassette delivery to CSS. Cassette delivery with the help of copters can be “transplanted” by staff, for example, on motorcycles that can change the digraph weights, making the digraph practically Euclidean.

Points geographically close to each other do not necessarily belong to one cluster, since there may not be a direct path between them with acceptable traffic. However, it is possible despite the fact that it is possible to walk from one DC to another and it will take an acceptable time.
In this case, perhaps when preparing the cluster digraph for calculating the solution to the "traveling salesman problem" not only "transfer" the CSS to the neighboring cluster, but also carry out the operation of "identifying" these vertices.

If the bank, as a result of any processes (for example, a marketing plan), has a list of points on the map of the settlement that you need to provide in the future with CSS, then based on the Strategy and the Financial Plan, you should start a business process the product of which will be a network development schedule , especially if it is not possible to purchase large batches of bulk at one time and you have to buy one-piece or small lots.
The choice of clustering algorithm is determined by the properties of the space and time of day in which the action takes place.

Settlements have historically been built up on the basis of a variety of principles, the landscape, the presence of natural and artificial intolerable and intolerable objects, and therefore have a unique network of roads and point facilities for the most economically feasible placement of CSS.

As a result, the shape of the cluster on the map will not have clear boundaries. On the contrary, clusters will “grow hair” with additional growth of the network due to single additions of CSS. Moreover, these “hairs” of neighboring clusters can be “intertwined”.

At the same time, a weighted digraph will not possess such visual properties by virtue of the principle of assigning weights based on traffic, but not on physical distances of roads.
The digraph weights can be so dynamic that there is a risk with the same given number of clusters, some “borderline” DCs can fall into one neighboring cluster or another. This should not be allowed, because this creates problems when planning the load of the OS, since the dates and Service Shifts of neighboring clusters may not substantially coincide. Therefore, in a number of such cases, it is necessary to force such wandering points to assign clusters.

The network will be presented in the form of a weighted digraph based on traffic received from Internet services such as Yandex.Traffic, which will save us from geographical problems and we can choose an algorithm from the family of heuristic graph algorithms.

Each cluster is simply obliged to 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 be certainly more optimal.

Placement of network and central heating networks


The solution to the placement problem should achieve not only the goal of maximizing the volume of settlement and cash services for bank customers and fee and commission income, but also the problem of minimizing the costs of servicing the network in the future and, as a result, the task of maximizing profits from using the Network.

Note that there can actually be two problems to be solved. So the task of placing new CSS in relation to the existing DH is the task inverse to the task of placing DH in relation to the existing Network. The found coordinates of the cluster centroids will also show us the most optimal hypothetical arrangement of the center clusters.

As a rule, most banks in one region have only one Network Center and, at some point, when the number of DCs on the Network is already large enough that traffic becomes a significant factor in the growth of time costs, it becomes necessary to create additional Central Centers for individual clusters (or their groups), whose centroids with the growth of the Network inevitably move away from the only existing DH.

The moment when an additional central heating facility should be opened should be considered the moment when the amount of current expenses for reaching remote clusters (RTek), the cost of funding increased cash balances for a longer period between service dates (Rfond) will exceed the amount of current costs of an additional central heating center taking into account depreciation of fixed assets and payroll and the cost of funding a one-time diversion of resources for the acquisition of these fixed assets.
The bank may be faced with the need to organize an additional DH before the physical “ceiling” is reached to further scale the activities of the existing DH on the growing Network.

In a bank with a developing Network, there should be a regulation on the placement of CSS in which an element of the business process of passing the preliminary examination is fixed if there are simultaneously alternative solutions for the placement. If there are no alternatives and points are given for directing the placement of the joint venture, then the examination will not help in any way, and the decision to optimize costs will be further in the “traveling salesman problem”.

The task of predicting the expense of notes


Forecasting is based on the following initial data:

  1. Operational data from the system about the current rate of spending notes.
  2. Historical data and the likelihood of a forecast for the next period of time between the service dates of the self-service device.

In each cassette (configured for a certain denomination of the banknote and when changing the cassettes in the safe compartment of the ATM, it is important not to confuse the cassette slots with the various banknotes), a tab is added to ultimately give an amount of no more than the insured for a particular ATM. Technical capabilities of the CSS requires the loading of 4 cassettes. The standard configuration of the bill composition (100, 1000, 5000) gives a maximum volume of about 4 million rubles.

We assume that the time between the service dates of the CA cluster cannot be longer than the term of exhaustion of the remainder in at least one device from this cluster. More precisely, the emptying of US cassettes charged with the most “running” banknotes of large denominations (1000 and 5000).
Thus, we believe that the loading of individual DCs, taking into account the cluster service schedule, may not reach the maximum possible load sizes, which theoretically provides an additional opportunity to reduce the cost of money insurance at a particular ATM. However, this is not true for all ATMs, since the forecast is required to take into account the presence and characteristics of salary projects with corporate customers of the bank, namely, the schedule for issuing advances and payroll payments to customer employees. On such dates, the CSS located near the client are subject to accelerated devastation.

Consequently, insurance (a contract is concluded for a period) for such ATMs should take into account the peak burden of spending the balance. Therefore, in such cases it will be the maximum possible load and save on insurance will not work for all CSS.

The task of interpreting traffic data for the weights of arcs and vertices of the graph. Preparation of the graph for calculating the route


Modern urban traffic is characterized by significant variability and difficult predictability for our purposes due to accidents, road works, rainfall, and the like.
Already during the route, the traffic load can suddenly increase sharply and unevenly, and in order not to jeopardize the network, you need to use an online tool to recount and get the “cheapest” route for the remaining number of cluster nodes that have not yet been serviced.

To improve the computing capabilities of the service, it is necessary not only to single out clusters of control units (“borderline” control units can change the “residence permit”), 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 personnel serving the business process )

For example, maintenance of a cluster located in the part of the city that is most affected by traffic jams should be planned for a night shift. In addition, in this case, most likely you will not have to recalculate the shortest route, since the graph weights will not change during the entire route. However, on the other hand, the criminal risk (the risk of attacking collectors) increases sharply, which will require an increase in the cost of guarding the crew.

As mentioned above, a technical solution is possible for the delivery of cash to US 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 the security guard will not be able to use the special armored car, but the usual one, only for their delivery to the point of deployment of the unit.

In order not to solve the problem of forecasting changes in weights over time, we propose an algorithm based on the approach of recalculating the remaining route from the current data on city traffic, balances in the DC and, therefore, the changed weights of arcs.

Our approach involves a step-by-step calculation of the route while it is being followed by the dispatch service. In this case, collectors will not know the next point in the route until it is declared by the dispatcher.

That is, by the time the next vertex is finished serving, a new route should be calculated taking into account the changed data on the weights of the arcs without including already-served vertices in the calculation.

That is, at each step, the route to (N - m) peaks is calculated. To do this, at each step, an arc elimination operation is performed 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 application in many industries and financial intermediation is no exception to this rule. We will not repeat here the well-known conditions and limitations of this task. Let us focus on the specifics of the solution in the framework of the “collector task.”

Obviously, a closed version of the solution of the traveling salesman problem should be implemented, since after driving around all the scheduled CSS routes, the removed cassettes should be brought to the responsible service center.

The restrictions imposed on the solution:

The requirements of the physical security service for the repeatability of the previous route. That is, if during the calculation of the route a solution similar to the previous one is obtained, then it is discarded and another one closest to the result is accepted for implementation.
The choice of a solution is determined not so much by the accuracy of the result, but by the speed of the algorithm in "field" conditions on hardware available to the bank in terms of price and quality.

Also popular now: