COMPLEX NETWORK-BASED ASSOCIATED ARTICLE STORAGE LOCATION OPTIMIZATION METHOD

Abstract

A slotting optimization method of associated articles based on a complex network, mainly comprising the following steps: 1) constructing a weighted article association network using warehoused articles as network nodes, and joint retrieval frequencies of pairs of articles as edges; 2) performing sorting on the importance of an article node and determining a community initial node; 3) determining a community structure of the article association network; 4) determining whether a community peripheral node is an overlapping node according to the strength of an association relationship of said node with another community; and 5) determining a best slot for each article. The present method applies the complex network theory to the problem of slot allocation for associated article retrieval, overall distance and time for retrieving articles is reduced, and article retrieval efficiency is improved.

(FIG. 1)

Claims

1. A slotting optimization method of associated articles based on a complex network, comprising following steps: Step 1, constructing a weighted article association network G = (V, E, W) using warehoused articles as network nodes, and joint retrieval frequencies of pairs of articles as edges, where V is a node set, which is a set of articles to be stored in a warehouse; E is a set of edges e.sub.ij, where i, j ∈ V, e.sub.ij ∈ E, namely a set of strong and weak associations between articles; W is a weight matrix, w.sub.ij corresponds to a weight of e.sub.ij, with a value equal to a frequency of retrieving articles i,j at the same time, which reflects a strength of the association between articles nodes; wherein independent nodes are deleted them from the association network when the independent nodes exist; Step 2, performing sorting on an importance C.sub.i (i) of an article node i by comprehensively taking into account a closeness centrality C.sub.c(i) of each article node and an importance level contribution value $\frac{w_{ij}{s}_i}{{.Math.s.Math.}^2}$ to each article node of a neighboring node thereof, where s.sub.i is a strength of the node i, .Math.s.Math. is an average strength of all nodes, and determining a core node as a community expansion starting point; Step 3, determining a community structure of an article association network using the capacity of each storage rack as a community volume limit and using weighted modularity Q.sup.w and weighted dependency D.sub.i,cʹ as expansion criteria; Step 4, determining whether a community peripheral node is an overlapping node according to a strength of an association relationship of the community peripheral node with another community; and Step 5, determining a slot allocation for each article by comprehensively taking into account the community structure of the article association network and a retrieval frequency of the article itself.

2. The slotting optimization method of associated articles based on a complex network according to claim 1, wherein Step 2 comprises: (a) analyzing a basic structure of the weighted article association network, and the closeness centrality of each article node is calculated; wherein in the weighted article association network, the strength s.sub.i of the node i is equal to a sum of the weights of the edges connected thereto: $s_i={\displaystyle \underset{j\in N_i}{.Math.}{w}_{ij}}$ where N.sub.i represents a set of neighboring node set of the node i, that is, a set of all the nodes associated with the node i; a shortest path between any two nodes in the weighted network is a most vulnerable branch, that is: ${{\displaystyle d}}_{ij}^w=\min \left[\left(M-w_{i{h}_1}\right)+\mathrm{...}\left(M-w_{h_{n}j}\right)\right]$ where h.sub.n is a midway node of each branch of i, j and M is a large number; at this time, the closeness centrality of each node is equal to the reciprocal of a sum of the shortest paths from the node to all other nodes multiplied by a number of other nodes, that is: $C_c\left(i\right)=\frac{n-1}{{\displaystyle \underset{i\ne j}{.Math.}{d}_{ij}^w}}$ where n is a total number of the nodes in the network; (b) sorting the importance of an article node according to the closeness centrality of the article node and an importance level contribution value to the article node of a neighboring node thereof; wherein in an article association weighted network with the number of nodes being n and the average strength being (s), the node i contributes $\frac{w_{ij}{s}_i}{{.Math.s.Math.}^2}$ of the importance level thereof to a neighboring node j thereof; when an edge weight between the node j and the node i is greater or the strength of the node .sup.f is greater, the importance level contribution of the node i to the node j is greater; the importance level C.sub.i(i) of the node is obtained by comprehensively taking into account the closeness centrality of the node and importance level contribution values to the node of all neighboring nodes: $C_i\left(i\right)=C_C\left(i\right)\times {\displaystyle \underset{j=1,j\ne i}{\overset{n}{.Math.}}{C}_C\left(j\right){\delta }_{ij}{w}_{ij}{s}_j/{.Math.s.Math.}^2}$ where δ.sub.ij represents the connectivity between two nodes, which is 1 in case of connection, or 0 in case of non-connection; (c) determining the volumes of communities and the number of communities according to the total number of storage racks in the warehouse, the capacities of the storage racks and the number of nodes in the article association network, and then determining the composition of the core node and the community expansion starting point according to the number of the communities and the sorting of the importance of the article node, wherein a community is a group of nodes in the complex network that are closely connected with each other but sparsely connected with other nodes.

3. The slotting optimization method of associated articles based on a complex network according to claim 1, wherein the Step 3 comprises: (a) adding the neighboring nodes of each core node into a set of expanded candidate nodes of each community, and calculating a modularity increment ΔQ.sup.w of each node in the set of candidate nodes to join the corresponding community: $\Delta Q^w=\left[\frac{{\displaystyle .Math.w_{C_j}^{in}+{\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}}}{2w}{\left(\frac{{\displaystyle .Math.w_{C_j}+s_i}}{2w}\right)}^2\right]-\left[\frac{{\displaystyle .Math.w_{C_j}^{in}}}{2w}-{\left(\frac{{\displaystyle .Math.w_{C_j}}}{2w}\right)}^2-{\left(\frac{S_i}{2w}\right)}^2\right]$ $w=\frac{{\displaystyle \underset{i=1}{\overset{n}{.Math.}}{\displaystyle \underset{j=1}{\overset{n}{.Math.}}{w}_{ij}}}}{2}$ where w represents a total weight value of the edges in the weighted network, ${\displaystyle .Math.w_{C_j}^{in}}$ represents a sum of the edge weights in the community, ${\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}$ represents a sum of weights of all edges connecting the node i and the nodes in the community C.sub.j, and ${\displaystyle .Math.w_{C_j}}$ represents a sum of weights of all edges associated with the nodes in the community; (b) selecting a node with the largest modularity increment to join the community; in case the node has joined other communities, comparing the modularity changes of the node when the node belongs to two communities; in case the modularity increment caused by the node joining a new community is greater than the modularity increment that keeps the node in an original community, deleting the node from the original community and join the new community; iterating this process until the community structure no longer changes and meets the requirements or ΔQ.sup.w is less than 0; in case an independent node exists at this time, calculating the dependency D.sub.i,Cʹ of the node on a neighboring community C, selecting a neighboring community that has not reached the community volume according to dependency sorting, and adding the node to the neighboring community, $D_{i,C}\text{'}=\frac{{\displaystyle \underset{j\in C}{.Math.}{w}_{i,j}}}{s_i}$ .

4. The slotting optimization method of associated articles based on a complex network according to claim 1, wherein the Step 4 comprises: (a) adding a node on the edge of the community and connected with other communities to a set U of potential overlapping nodes, and calculating the modularity increment $\Delta Q_{jn}^w\text{'}$ of each potential overlapping node joining other communities; (b) calculating the modularity increment $\Delta Q_j^w\text{'}$ that keeps the node in the original community, and when a difference between $\Delta Q_{jn}^w\text{'}$ and $\Delta Q_j^w\text{'}$ is less than $\frac{5}{2w},$ affirming that the potential overlapping node has overlap with other communities; (c) calculating a number of truly overlapping nodes between two communities, and determining a degree of overlap between communities by dividing the number by a sum of the nodes of the two communities.

5. The slotting optimization method of associated articles based on a complex network according to claim 1, wherein the Step 5 comprises: formulating a slot allocation strategy according to a layout of the warehouse and the divided community structure; firstly, sorting the retrieval frequency of each divided community, and allocating the community to each roadway of the warehouse one by one according to the ranking of the community; in case free storage racks still exists in the roadway after a community is allocated, taking into account the overlapping degree among various communities and placing high overlapping communities with an overlapping degree higher than 10% on other storage racks in the same roadway; when the number of the high overlapping communities is greater than the number of remaining storage racks, determining which high overlapping community the remaining storage racks belong to according to the community retrieval frequency; when no high overlapping community with an overlapping degree higher than 10% exists, allocating the remaining storage racks according to the retrieval frequency of each community; then allocating the slots in the rack wherein retrieval across the roadway must be performed via a roadway entrance under a single-channel layout, as a result, no matter which roadway the overlapping community of an overlapping articles is located in, the distance between the overlapping community and the article is capable of being reduced by placing the article closer to the roadway entrance in the original community, and thereby adopting an evaluation function S.sub.i to determine the slot arrangement of the article in the community: ${}_{S_i=\alpha {\frac{CO{I}_i}{\max COI}}_{C_j}+\beta {\delta }_i\frac{{\displaystyle \underset{jn=1}{\overset{JN}{.Math.}}{\displaystyle \underset{j\ast \in C_{jn}}{.Math.}{w}_{i,j\ast }}}}{{\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}}}$ where COI.sub.i represents a retrieval frequency of the article i; $\max CO{I}_{C_j}$ represents a maximum retrieval frequency of the articles in the community; ${\displaystyle \underset{j*\in C_{jn}}{.Math.}{w}_{i,j*}}$ represents a sum of the weights of the connecting edges of an overlapping article i and an overlapping community C.sub.jn ; when there is more than one overlapping community of i, for example, there are JN overlapping communities, ${\displaystyle \underset{jn=1}{\overset{JN}{.Math.}}{\displaystyle \underset{j*\in C_{jn}}{.Math.}{w}_{i,j*}}},$ which represents a sum of weights of the connecting edges of the overlapping article i and all the external overlapping communities to which the overlapping article belongs; ${\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}$ represents a sum of weights of the connecting edges of the overlapping article i and the community C.sub.j to which the overlapping article really belongs; δ.sub.i is a variable of 0-1; if i is an overlapping article, then δ.sub.i=1, and if i is not an overlapping article δ.sub.i =0; α, β represent the weights of the two major components of the evaluation function, α + β = 1, and then the arrival time of each slot in the rack is calculated, wherein t = t.sub.walk + t.sub.retrieval in a manual picking warehouse, namely a sum of a walking time and a vertical pick-up time after standing; the matching between articles and slots is completed according to the scoring and sorting of the evaluation function of the article and the sorting of the slot arrival time; finally, allocating possible independent nodes to spare slots according to the retrieval frequency.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0022] FIG. 1 shows the overall process of the slotting optimization method of associated articles based on a complex network;

[0023] FIG. 2 is a schematic diagram of a double-zone single-channel warehouse;

[0024] FIG. 3 is a schematic diagram of the slot allocation process based on the community structure and retrieval frequency of article (taking the double-zone single-channel warehouse in FIG. 2 as an example);

[0025] FIG. 4 is a schematic diagram of the construction of article association network;

[0026] FIG. 5 shows the community allocation result and the overlapping node distribution diagram in the articles association network.

DESCRIPTION OF EMBODIMENTS

[0027] The technical solution of the present disclosure will be further explained with reference to the accompanying drawings.

[0028] A slotting optimization method of associated articles based on a complex network, as shown in FIG. 1, includes the following steps:

[0029] Step (1): constructing a weighted article association network.

[0030] In the present disclosure, a weighted article association network G = (V, E, W) is constructed using warehoused articles as network nodes, and joint retrieval frequencies of pairs of articles as edge, where V is a node set, i.e., a set of articles to be stored in a warehouse; E is a set of edges e.sub.ij, where i, j ∈ V, e.sub.ij ∈ E , that is, a set of strong and weak associations between articles; W is a weight matrix, w.sub.ij corresponds to the weight of e.sub.ij, the value of which is equal to a frequency of retrieving articles i,j at the same time, which reflects a strength of the association between the articles nodes; if there are independent nodes, the independent nodes are deleted them from the association network.

[0031] Step (2): performing sorting on the importance of an article node by comprehensively taking into account the closeness centrality of each article node and an importance level contribution value to each article node of a neighboring node thereof, and determining a core node, i.e., a community expansion starting point.

[0032] First, the node strength and the shortest path between two nodes are determined. In the weighted article association network, the strength s.sub.i of the node i is equal to a sum of the weights of the edges connected thereto:

$S_i={\displaystyle \underset{j\in N_i}{\overset{}{.Math.}}{w}_{ij}}$

where N.sub.i represents a set of neighboring node set of the node i, that is, a set of all the nodes associated with the node i.

[0033] The shortest path between any two nodes in the weighted network is the most vulnerable branch, that is:

$d_{ij}^w=\min \left[\left(M-w_{i{h}_1}\right)+\mathrm{...}\left(m-w_{h_{n}j}\right)\right]$

where h.sub.n is a midway node of each branch of i, j and M is a large number.

[0034] Then, the closeness centrality of the node is calculated according to the shortest path. The closeness centrality of each node is equal to the reciprocal of a sum of the shortest paths from the node to all other nodes multiplied by the number of other nodes, that is:

$C_c\left(i\right)=\frac{n-1}{{\displaystyle \underset{i\ne j}{\overset{}{.Math.}}{d}_{ij}^w}}$

where n is a total number of the nodes in the network.

[0035] Next, the importance of an article node is sorted according to the closeness centrality of the article node and an importance level contribution value to the article node of a neighboring node thereof. For an article association weighted network with the number of nodes being n and the average strength being .Math.s.Math., the node i will contribute

$\frac{w_{ij}{s}_i}{{.Math.s.Math.}^2}$

of the importance level thereof to a neighboring node j thereof; if an edge weight between the node j and the node i is greater or the strength of the node is greater, then the importance level contribution of the node i to the node j will be greater; the importance level C.sub.i(i) of the node is obtained by comprehensively taking into account the closeness centrality of the node and importance level contribution values to the node of all neighboring nodes:

$C_i\left(i\right)=C_c\left(i\right)\times {\displaystyle \underset{j=1,j\ne i}{\overset{n}{.Math.}}{C}_c\left(j\right){\delta }_{ij}{w}_{ij}{s}_j\text{}/\text{}{.Math.s.Math.}^2}$

where δ.sub.ij represents the connectivity between two nodes, which is 1 in case of connection, and otherwise 0. Then the volumes of communities and the number of communities are determined according to the total number of storage racks in the warehouse, the capacities of the storage racks and the number of nodes in the article association network, and finally the core node, i.e., the community expansion starting point, is determined according to the number of the communities and the sorting of the importance of the article node.

[0036] Step (3): determining the community structure of the article association network by taking into account the capacity of the rack.

[0037] Firstly, the neighboring nodes of each core node are added into a set of expanded candidate nodes of each community, and a modularity increment ΔQ.sup.w of each node in the set of candidate nodes to join the corresponding community is calculated:

$\begin{array}{l}\Delta Q_w=\left[\frac{{\displaystyle .Math.w_{C_j}^{in}+{\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}}}{2w}-{\left(\frac{{\displaystyle .Math.w_{C_j+S_i}}}{2w}\right)}^2\right]-\\ \left[\frac{{\displaystyle .Math.w_{C_j}^{in}}}{2w}-{\left(\frac{{\displaystyle .Math.w_{C_j}}}{2w}\right)}^2-{\left(\frac{S_i}{2w}\right)}^2\right]\end{array}$

$w=\frac{{\displaystyle \underset{i=1}{\overset{n}{.Math.}}{\displaystyle \underset{j=1}{\overset{n}{.Math.}}{w}_{ij}}}}{2}$

where w represents a total weight value of the edges in the weighted network,

${\displaystyle .Math.w_{C_j}^{in}}$

represents a sum of the edge weights in the community,

${\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}$

represents a sum of weights of all edges connecting the node i and the nodes in the community C.sub.j, and

${\displaystyle .Math.w_{C_j}}$

represents a sum of weights of all edges associated with the nodes in the community; then a node with the largest modularity increment is selected to join the community; if the node has joined other communities, the modularity changes of the node when the node belongs to two communities are compared; if the modularity increment caused by the node joining a new community is greater than the modularity increment that keeps the node in an original community, the node is deleted from the original community and join the new community; this process is iterated until the community structure no longer changes and meets the requirements or ΔQ.sup.w is less than 0; if there is still an independent node at this time, the dependency D.sub.i,.sub.c′ of the node on a neighboring community C is calculated, a neighboring community that has not reached the community volume is selected according to dependency sorting, and the node is added to the neighboring community,

$D_{i,C}\text{'}=\frac{{\displaystyle \underset{j\in C}{.Math.}{w}_{i,j}}}{S_i}$

[0038] Step (4): determining overlapping nodes with strong association with other communities.

[0039] Firstly, a node on the edge of the community and connected with other communities is added to a set U of potential overlapping nodes, and the modularity increment

$\Delta {\text{Q}}_{jn}^w\text{'}$

of each potential overlapping node joining other communities is calculated; then the modularity increment

$\Delta {\text{Q}}_j^w\text{'}$

that keeps the node in the original community is calculated, and if a difference between

$\Delta {\text{Q}}_{jn}^w\text{'}$

and

$\Delta {\text{Q}}_j^w\text{'}$

is less than

$\frac{5}{2w},$

it is considered that the potential overlapping node has overlap with other communities; finally a number of truly overlapping nodes between two communities is calculated, and a degree of overlap between communities is determined by dividing the number by a sum of the nodes of the two communities.

[0040] Step (5): determining the slot allocation for each article by comprehensively taking into account the community structure of the article association network as well as a retrieval frequency of the article itself.

[0041] The core of this step is to formulate a slot allocation strategy that matches the current situation of the warehouse according to the warehouse layout and the community structure divided in step (4).

[0042] Taking the double-zone single-channel warehouse (shown in FIG. 2) as an example, first, the retrieval frequency of each divided community in step (4) is sorted, and the community is allocated to each roadway one by one according to the ranking of the community; if there are still free storage racks in the roadway after a community is allocated, the overlapping degree among various communities is taken into account, and high overlapping communities with an overlapping degree higher than 10% are placed on other storage racks in the same roadway; if the number of the high overlapping communities is greater than the number of remaining storage racks, it is determined which high overlapping community the remaining storage racks belong to according to the community retrieval frequency; if there is no high overlapping community with an overlapping degree higher than 10%, the remaining storage racks are allocated according to the retrieval frequency of each community; then the slots in the rack are allocated. Since retrieval across the roadway must be performed via a roadway entrance under such a layout, no matter which roadway the overlapping community of an overlapping articles is located in, the distance between the overlapping community and the article can be reduced by placing the article closer to the roadway entrance in the original community. Accordingly in the present disclosure, an evaluation function S.sub.i is adopted to determine the slot arrangement of the article in the community:

$S_i=a\frac{CO{I}_i}{\max CO{I}_{C_j}}+\beta {\delta }_{\text{i}}\frac{{\displaystyle \underset{jn=1}{\overset{JN}{.Math.}}{\displaystyle \underset{j*\in C_{jn}}{.Math.}{w}_{i,j*}}}}{{\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}}$

where COI.sub.i represents a retrieval frequency of the article i; maxCOI.sub.cj represents a maximum retrieval frequency of the articles in the community;

${\displaystyle \underset{j*\in C_{jn}}{.Math.}{w}_{i,j*}}$

represents a sum of the weights of the connecting edges of an overlapping article i and an overlapping community C.sub.jn; when there is more than one overlapping community of i, for example, there are JN overlapping communities, which represents a sum of weights of the connecting edges of the overlapping article i and all the external overlapping communities to which the overlapping article belongs;

${\displaystyle \underset{j\in C_j}{.Math.}{w}_{i,j}}$

represents a sum of weights of the connecting edges of the overlapping article i and the community C.sub.J to which the overlapping article really belongs; δ.sub.i is a variable of 0-1; if i is an overlapping article, then δ.sub.i=1, otherwise 0; a, β represent the weights of the two major components of the evaluation function, a + β = 1; because the strength of the internal relationship between the overlapping article and the community to which it belongs is close to that between the overlapping article and external overlapping community, a, β can both be 0.5, and α can be moderately higher than β if the warehouse pays more attention to the retrieval frequency of the article itself; then the arrival time of each slot in the rack is calculated. t = t.sub.walk + t.sub.retrieval in a manual picking warehouse, that is, a sum of a walking time and a vertical pick-up time after standing; the matching between articles and slots is completed according to the scoring and sorting of the evaluation function of the article and the sorting of the slot arrival time; if there are independent nodes, they are allocated to spare slots according to the retrieval frequency.

[0043] The method in this embodiment is further explained by a specific example below.

[0044] The layout of a two-zone single-channel warehouse has 402 kinds of materials stored in 7 storage racks with 11 columns and 6 floors. Through the analysis of more than 500 past retrieval and delivery documents, the material association network can be drawn as shown in FIG. 4. Then the importance of each material is calculated according to formula (1)-(4) as shown in the following table 1.

TABLE-US-00001 Sorting of material importance degree Stock number Importance degree Importance degree ranking 101111 0.0183 1 105403 0.0174 2 101910 0.0157 3 103179 0.0154 4 101512 0.0151 5 107778 0.0149 6 101142 0.0135 7 102489 0.0131 8 102497 0.0126 9

[0045] According to the rack capacity and the number of material types, the number of core nodes is set to 7, and the volume of communities is set to 66. Then, according to formulas (5)- (7), community expansion and overlapping node discovery are carried out. The expanded community structure and overlapping node distribution are shown in FIG. 5, and the volumes of the communities are 66, 65, 63, 58, 57, 54 and 39, which meet the rack capacity limit. According to the last step (5), slots are allocated for each material. The comparison between the slotting optimization method of associated articles based on a complex network proposed by the present disclosure and the common slot allocation methods is shown in the following table 2.

TABLE-US-00002 Comparison of various slot allocation methods Slot allocation method Average pick-up time per order (s) Average number of times of cross-roadway retrievals per order Random allocation strategy 250.04 3.87 Retrieval frequency allocation 226.78 2.89 Association rule allocation 220.05 2.35 Method of the present disclosure 205.41 2.02

[0046] The above data show that compared with other common methods, the slotting optimization method of associated articles based on a complex network provided by the present disclosure has obvious effects in shortening the pick-up time and reducing the times of cross-roadway retrievals, and can better solve the slot allocation optimization problem of associated articles.

[0047] The above is only a preferred embodiment of the present disclosure, which is only used to help understand the present disclosure, and is not intended to limit the present disclosure. According to the concept of the present disclosure, those skilled in the technical field of the present disclosure can also make some simple deduction and deformation, such as designing corresponding slot allocation strategies according to other warehouse layout modes.