=Paper=
{{Paper
|id=Vol-2098/paper26
|storemode=property
|title=Problem of Distribution of Goods
by Logistics Centers
|pdfUrl=https://ceur-ws.org/Vol-2098/paper26.pdf
|volume=Vol-2098
|authors=Anatoly Panyukov,Khalid Z. Chaloob
}}
==Problem of Distribution of Goods
by Logistics Centers==
https://ceur-ws.org/Vol-2098/paper26.pdf
Problem of Distribution of Goods
by Logistics Centers
Anatoly Panyukov and Khalid Z. Chaloob
South Ural State University,
76 Lenina Ave., 454080, Chelyabinsk, Russia
paniukovav@susu.ru
khalid.e@mail.ru
Abstract. Effective logistics management is recognized as a key factor
in improving the performance of companies and their competitiveness.
The econometric methods used in practice do not provide the means
for promptly solving a multitude of emerging problems, in particular
for effective operational management of a network marketing organiza-
tion. In the paper, algorithms for analyzing and solving the problem of
distribution of goods by logistics centers, including decision support sys-
tem in case of incorrectness of the arising problem are proposed: (1) the
method of regularization of the decomposable distribution problem; (2)
an effective algorithm for approximating an indecomposable problem by
a decomposable problem. The software implementation of the proposed
algorithms is easily encapsulated in the MS Office system.
Keywords: Logistics center · Transport problem · Operational manage-
ment · Distribution task · Regularization · Decomposition · Algorithm
1 Introduction
A enterprise is a complex and dynamic system actively interacting with the exter-
nal environment. Currently, effective logistics management is recognized as a key
factor in improving the performance of companies and their competitiveness [9,
3]. Budashevsky, and Pastukhova [2] propose constructive comparative analysis
of methods and models for estimating demand used in economics and market-
ing and system technology for analyzing and forecasting consumer preferences.
Bayev and Drozin [1] consider questions of the dynamics of consumer demand.
Levin notes [4] that these methods do not provide the means to quickly solve a
lot of emerging problems, in particular for effective operational management of
the network marketing organization.
Algorithms for analyzing and solving the problem of the distribution of goods
by logistics centers, including a decision support system in case of illposed arising
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
Problem of Distribution of Goods 305
problem are proposed in the paper. Software implementation of these algorithms
is easily encapsulated in the MS Office system [5, 6].
In the first section we give a formal statement of the problem and introduce
the main notation used of this paper. In the second section we consider the de-
composable case of a problem reducible to the transport problem with matrix
formulation. In the third section we propose a method for regularizing a decom-
posable problem in the case of its illposed formulation. In the fourth section we
propose a method for approximating the problem of the original problem with
a decomposable problem.
2 Statement of the Problem
The problem of distributing a set I of goods over a set J of logistics centers is
considered. Let xij be the volume of the commodity i ∈ I distributed to the
center j ∈ J. Let pij be the marginal profit from the sale of a unit of commodity
i ∈ I at the center j ∈ J. Let λij be the cost of distribution of a unit of
commodity i ∈ I by the center j ∈ J. Let di be the effective demand for the
commodity i ∈ I. Let bj be the resource for the maintenance of the center j ∈ J.
The formal formulation of the problem consists in finding the distribution of
goods i ∈ I at the centers j ∈ J, for which the marginal profit is maximal
XX
xo = arg max pij xij , (1)
x∈D
j∈J i∈I
all goods are satisfied with the effective demand
X
xij = di , i ∈ I, (2)
j∈J
resource constraints have been met for all centres
X
λij xij ≤ bj , j ∈ J, (3)
i∈I
the condition of non-negativity is fulfilled
xij ≥ 0, i ∈ I, j ∈ J. (4)
The problem (1)-(4) is the known distribution task of linear programming [7,
8]. In general, for this task is not known methods that take into account its
specificity, so to solve it apply universal methods of linear programming. For
large-scale tasks, this approach requires commercial software. In addition, if
problem (1)-(4) has no solution, the principle of making an acceptable decision
is not clear in this statement.
306 A. Panyukov, K. Z. Chaloob
3 The Decomposable Case of Task (1)-(4)
For some cases, the parameter λij can be represented as the product
λij = αi · βj , i ∈ I, j ∈ J (5)
where αi is the resource intensity of the commodity i ∈ I in conventional units,
βj is the cost of servicing the conventional unit at the center j ∈ J. This case of
the problem (1)-(4) is called as decomposable problem. It is possible decomposable
problem (1)-(4) reducing to the matrix transportation problem. Indeed, for all
j ∈ J we have
! !
X X
λij xij ≤ bj ⇔ αi βj xij ≤ bj ⇔
i∈I i∈I
! !
X bj X bj
αi xij ≤ ⇔ yij ≤ ,
βj βj
i∈I i∈I
here yij = αi · xij for all i ∈ I, j ∈ J. Passing to the variables yij = αi · xij for
all i ∈ I, j ∈ J in problem (1)-(4) get
X X di
xij = di ⇔ yij = , i ∈ I,
αi
j∈J j∈J
XX X X pij y ij
pij xij = .
αi
j∈J i∈I j∈J i∈I
Thus, the problem (1)-(4) is equivalent to the following one
X X pij y ij
y o = arg max , (6)
x∈D αi
j∈J i∈I
X di
yij = , i∈I (7)
αi
j∈J
X bj
yij ≤ , j∈J , (8)
βj
i∈I
yij ≥ 0, i ∈ I, j ∈ J. (9)
The problem (6)-(9) is open matrix transportation problem [7, 8]. The encapsu-
lated in the MS Office system software to solve such problems of large dimension
is known [6].
Problem of Distribution of Goods 307
4 Regularization of Problems (1)-(4) and (6)-(9)
Problem (6)-(9) (hence and (1)-(4)) has a solution when demand does not exceed
the supply, i.e.
X di X bj
S= − ≤ 0.
αi βj
i∈I j∈J
Otherwise (that is, if S > 0), the problems (1)-(4) and (6)-(9) do not have
admissible solutions, and it is required to correct the original problem to find a
suitable solution. Possible ways to adjust the conditions of these tasks are:
1. To allow the supply of all goods below the effective demand
X di
yij = − yi0 , yi0 ≥ 0, i ∈ I;
αi
j∈J
2. To develop the infrastructure of all routes in order to effectively support the
effective demand
X bj
yij = + y0j , y0j ≥ 0, j ∈ J,
βj
i∈I
where y0j is the amount of investment (in conventional units) in the devel-
opment of the route j ∈ J.
Let ki be the allowed fraction of the unsatisfied demand for the commodity i ∈ I
(i.e. yi0 ≤ ki di ). Let p0j be the amount of investment required to expand the
resources of the center j ∈ J by one conditional unit.
Let us consider the corrected problem taking into account the variables and
restrictions introduced in this section.
!
X X pij y ij
o
y = arg max − p0j y0j , (10)
y∈D αi
j∈J i∈I
X di
yij + yi0 = , i ∈ I, (11)
αi
j∈J
X bj
yij − y0j = , j ∈ J, (12)
βj
i∈I
yi0 ≤ ki di , i ∈ I, (13)
yij , yi0 , y0j ≥ 0, i ∈ I, j ∈ J. (14)
The problem (10)-(14) is closed matrix transportation problem [7]. The encapsu-
lated in the MS Office system software to solve such problems of large dimension
is known [6].
308 A. Panyukov, K. Z. Chaloob
Obviously, problem (10)-(14) has an optimal solution. The regularization is
carried out by introducing additional endogenous variables yi0 , y0j ≥ 0, i ∈
I, j ∈ J, exogenous variables ki , i ∈ I, and constants p0j , j ∈ J.
It is evident from the constructed model that at fixed prices maintaining
effective demand leads to a decrease in marginal profit. Preservation of marginal
profit requires an increase in the selling price of goods, which can lead to an
irreversible decrease in demand and a decrease in marginal profit. Thus, the task
of decision-making in conditions of risk and uncertainty arises. The controlled
parameters in this case are the exogenous variables ki , i ∈ I.
Let us use the marginal profit M and the amount of unmet demand S as
criteria in the decision-making model. It is obvious that all solutions of problem
(10)-(14) are Pareto optimal ones for fixed values of the exogenous variables
ki , i ∈ I. The problem of choosing specific values of these variables is difficult
to formalize and requires the participation of the decision-maker (DM).
5 Approximation of the Problem (1)-(4) by the
Decomposable Problem
As was noted above, problem (1)-(4) is decomposable if the equalities (5) hold.
The value of the parameter λij is interpreted as the cost of distributing a unit
of commodity i ∈ I by the center j ∈ J, and its value can be determined us-
ing statistical measurements. On the contrary, the parameters {αi > 0 : i ∈ I},
{βj > 0 : j ∈ J} are interpreted using the term ”conventional unit”, therefore
their direct statistical measurement is impossible. Therefore, we consider the
equalities (5) as a system of algebraic equations with unknowns {αi > 0 : i ∈ I},
{βj > 0 : j ∈ J}. It is clear that for arbitrary values λij the system of equations
(5) may be inconsistent.
Let us introduce the function
X αi βj
Fλ (α, β) = log .
λij
i∈I, j∈J
Obviously, inf Fλ = 0 if and only if the system of equations (5) is consistent.
It follows from the nonnegativity of the function Fλ () that the value of inf Fλ
can be considered as the degree of incompatibility of the system (5). Function
Fλ (), λ > 0 is continuous in the neighborhood of any minimum, so the infimum is
reached, and the optimal approximate solution of the system (5) with a minimal
degree of incompatibility
X α β
i j
(αo , β o ) = arg min log
{βj >0: j∈J} λij
i∈I, j∈J
{αi :>0: i∈I}
can be considered.
Problem of Distribution of Goods 309
It is easy to see that the optimality of the solution (αo , β o ) implies the op-
timality of the solution set D = {(αo · c, β o /c) : c > 0}. We shall assume that
the solution of the approximating problem is
(α∗ , β ∗ ) = arg min k(α, β)k∞ . (15)
(α,β)∈D
Note that if (α, β) ∈ D then
( s )
max β maxi∈I αi
r
j∈J j
α∗ = ak · , ∗
β = βk · .
maxi∈I αi maxj∈J βj k∈J
k∈I
Thus, the correct formulation of the approximating problem is two-level, but for
its solution it is sufficient to find any solution of the problem (1) of the lower
level.
6 Algorithm to Solve Problem (15)
The following algorithm allows us to solve the problem (15).
Decomposition algorithm
Input: I, J, Λ = {λij }i∈I, j∈J ;
Output: α = {αi }i∈I , β = {βj }j∈J , FΛ (α, β);
Step 1. (Construct matrix Λ̂). For each line i ∈ I of the matrix Λ execute steps
1.1, 1.2 and 1.3, then go to step 2.
Step 1.1. Build sorted line i ∈ I
n
(k)
Λ [i] = λij (k) :
o
(1) (2) (|J|)
k = 1, 2, . . . , |J| , j (k) ∈ J, λij (1) ≤ λij (2) ≤ . . . ≤ λij (|j|) , .
j k l m r
|J|+1 |J|+1 (k ) (k )
Step 1.2. Let k− = 2 , k+ = 2 , αi = λ (+k+ ) · λ (−k− ) .
ij ij
(k)
(k) λ (k)
ij
Step 1.3. For k = 1, 2, . . . , |J| let λ̂ij (k) = αi .
Step 2. (Construct matrix Λ̃). For each column j ∈ J of the matrix Λ̂ execute
steps 2.1, 2.2 and 2.3, then go to step 3.
Step 2.1. Build sorted column j ∈ J
n
(k)
Λ̂ [∗] [j] = λ̂i(k) j :
o
(1) (2) (|I|)
k = 1, 2, . . . , |J| , j (k) ∈ J, λ̂i(1) j ≤ λ̂i(2) j ≤ . . . ≤ λ̂i(|I|) j .
j k l m r
|I|+1 |I|+1 (k ) (k )
Step 2.2. Let k− = 2 , k+ = 2 , βj = λ̂ (k++ ) · λ̂ (k−− ) .
i j i j
310 A. Panyukov, K. Z. Chaloob
(k)
(k) λ̂ (k)
li(k) j = iβj j .
Step 2.3. For k = 1, 2, . . . , |I| let e
Step 3. (Normalization).
r Follow steps 3.1, 3.2, and 3.3, and then go to step 4.
maxi∈I αi
Step 3.1. Let c = .
maxj∈J βj
Step 3.2. For all i ∈ I let αi = αi /c.
Step 3.3. For all j ∈ J let βj = βj · c.
P α β
Step 4. Let FΛ (α, β) = i∈I, j∈J log λi ij j .
n o
Step 5. Return α = {αi }i∈I , β = {βj }j∈J , FΛ (α, β) .
End.
Theorem 1. Decomposition algorithm correctly solves problem (15). Its alge-
braic computational complexity does not exceed the value O (|I| · |J| · log (|I| · |J|)).
Proof. Monotony of the logarithmic function implies
αi βj
log = 0 ⇔ (− log λij + log αi + log βj = 0)
λij
⇔ −lij + xi − yj = 0, lij = log λij , xi = log αi , y j = log βj , i ∈ I, j ∈ J,
Therefore problem (15) is equivalent to problem
X
(xo , y o ) = arg min |−lij + xi − yj | (16)
x∈R|I| i∈I, j∈J
y∈R|J|
and there is the one-to-one correspondence between the optimal solutions of
these problems.
Problem (16) is equivalent to linear programming problem
X
wij → min , (17)
x,y,w
i∈I, j∈J
−wij ≤ −lij + xi + yj ≤ wij , wij ≥ 0, i ∈ I, j ∈ J. (18)
Dual problem (17)-(18) is the problem
X
lij (fij − fji ) → max , (19)
f
i∈I, j∈J
X
(fij − fji ) = 0, i ∈ I, (20)
j∈J
X
(fij − fji ) = 0, j ∈ J, (21)
i∈I
fij + fji ≤ 1, fij , fji ≥ 0, i ∈ I, j ∈ J. (22)
Problem of Distribution of Goods 311
Making the change of variables gij = fij − fji , i ∈ I, j ∈ J in problem (19)-(22)
we get the problem of maximum weight circulation
X
lij gij → max , (23)
g
i∈I, j∈J
X
gij = 0, i ∈ I, (24)
j∈J
X
gij = 0, j ∈ J, (25)
i∈I
−1 ≤ gij ≤ 1, i ∈ I, j ∈ J. (26)
Dual problem (23)-(26) is the problem
X
TΛ (r, s, t) = (tij + tji ) → min , (27)
r,s,t
i∈I, j∈J
ri + sj + tij − tji = lij , tij , tji ≥ 0, i ∈ I, j ∈ J. (28)
Let us compare problem (17)-(18) constraints system and problem (27)-(28)
constraints system. It is easy to see that the admissibility of the basic solution
(r, s, t) of problem (27)-(28) implies the admissibility of solution
R = (x = r, y = s, w = {wij = tij + tji : i ∈ I, j ∈ J})
of problem (17)-(18). Moreover, if (r, s, t) is an optimal solution of problem (27)-
(28), then R is an optimal solution of problem (17)-(18), since dual problems
(19)-(22) and (23)-(26) have corresponding optimal solutions.
The one-to-one compilation of algorithm Decomposition in terms of values
(x, y, l)) can be represented as following algorithm.
Log Decomposition algorithm
Input: I, J, L = {lij i ∈ I, j ∈ J};
Output: x = {xi i ∈ I} , y = {yj j ∈ J} , FL (x, y);
Step 1. (Construct matrix L̂). For each line i ∈ I of the matrix L execute steps
1.1, 1.2 and 1.3, then go to step 2.
Step 1.1. Build sorted line i ∈ I
n
(k)
L [i] = lij (k) :
o
(1) (2) (|J|)
k = 1, 2, . . . , |J| , j (k) ∈ J, lij (1) ≤ lij (2) ≤ . . . ≤ lij (|j|) , .
(k+ ) (k− )
j k l m l k )
+l (k )
|J|+1 |J|+1 ij + ij −
Step 1.2. Let k− = 2 , k+ = 2 , ri = 2 .
(k) (k)
Step 1.3. For k = 1, 2, . . . , |J| let ˆlij (k) = lij (k) − ri .
Step 2. (Construct matrix L̃). For each column j ∈ J of the matrix L̂ execute
steps 2.1, 2.2 and 2.3, then go to step AUX.
312 A. Panyukov, K. Z. Chaloob
Step 2.1. Build sorted column j ∈ J
n
(k)
L̂ [∗] [j] = ˆli(k) j :
o
(1) (2) (|I|)
k = 1, 2, . . . , |J| , j (k) ∈ J, ˆli(1) j ≤ ˆli(2) j ≤ . . . ≤ ˆli(|I|) j .
(k ) (k )
j k l m l̂ (k+ ) +l̂ (k− )
|I|+1 |I|+1 + j − j
Step 2.2. Let k− = 2 , k+ = 2 , sj = i 2
i
.
(k) (k)
li(k) j = ˆli(k) j − sj .
Step 2.3. For k = 1, 2, . . . , |I| let e
Step AUX. (Construct matrix T) For all i ∈ I, j ∈ J execute steps AUX.1
and AUX.2 then go to step 3.
Step AUX.1 If ˜lij > 0, then put tij = ˜lij , tji = 0,
otherwise put tji = −˜lij , tij = 0.
Step AUX.2 Calculate
X
TΛ (r, s, t) = (tij + tji ) .
i∈I, j∈J
Step 3. (Normalization). Follow steps 3.1, 3.2, and 3.3, and then go to step 4.
Step 3.1. Let
maxi∈I xi − maxj∈J yj
c= .
2
Step 3.2. For all i ∈ I let ri = ri − c.
n all j ∈ J let sj = sj + c.
Step 3.3. For o
Step 4. Return x = {ri }i∈I , y = {sj }j∈J , TΛ (r, s, t) .
End.
Here an auxiliary step AUX is introduced to prove the effectiveness of the
algorithms. The optimal values of the variables tij , tji , i ∈ I, j ∈ J and the
optimal value TΛ (r, s, t) for the problem (27)-(28) are calculated at step AUX.
It is obvious that the solution (r, s, t), constructed by Log Decomposition
algorithm, meets all constraints of the problem (27)-(28). On the other hand
problem (23)-(26) has an integral-valued optimal solution [10], i.. in the optimal
solution g for all i ∈ I, j ∈ J there is an inclusion gij ∈ {−1, 0, 1}. Let us
to construct the solution {gi j i ∈ I, j ∈ J} of problem (23)-(26) using the
conditions of complimentary with respect to solutions (r,s,t) of the dual problem
(27)-(28), i.e. put
(1) gij = −1 for all i ∈ I, j ∈ J such that tij = 0, tji > 0;
(2) gij = 1 for all i ∈ I, j ∈ J such that tij > 0, tji = 0;
(3) gij = 0 for all i ∈ I, j ∈ J such that tij = tji = 0.
It is easy to see that the constructed solution {gij i ∈ I, j ∈ J} is an admissible
solution of problem (23)-(26). It follows form the second duality theorem in
linear programming that (r, s, t) and {gij i ∈ I, j ∈ J} are optimal solutions
Problem of Distribution of Goods 313
of the problems (23)-(26) and (27)-(28) correspondingly. The effectiveness of
Log Decomposition algorithm, hence Decomposition algorithm, is proved.
Let us to turn to the estimation of Decomposition algorithm computational
complexity. The body of Step 1 contains the sorting of the elements of the
row (computational complexity O(|J| log |J|)) and recalculation of its elements
(computational complexity O(|J|)). Consequently, computational complexity of
Step 1 does not exceed values O(|I||J| log (|J|) ). Analogous arguments for Step 2
lead to the validity of the assertion that computational complexity of Step 2 does
not exceed O(|I||J| log (|I|) ). Therefore, the total computational complexity of
Steps 1 and 2 will not exceed the values O(|I||J| log (|I||J|) ). Step 3 consists
of computation of value c and recalculation of values α = {αi i ∈ I} , β =
{βj j ∈ J} , its computational complexity does not exceed O(|I||J|). Step 4
consists of summing the O(|I||J|) elements, its computational complexity does
not exceed O(|I||J|) as well. Thus, computational complexity of the algorithm
does not exceed O(|I||J| log (|I||J|) ). The theorem is proved.
7 Conclusion
The proposed algorithms solve the problems of analyzing the distribution of
goods by logistics centers, including a decision support system in case of in-
correctness of the task. Software implementation of these algorithms is easily
encapsulated in the MS Office system.
References
1. Bayev, I.A., Drozin, D.A.: Dinamika pokupatel’skogo sprosa innovatsionnogo to-
vara (Dynamics of consumer demand for innovative goods). Bulletin of the South
Ural State University. Ser. Economics and Management 8(2), 80–85 (2014), (in
Russian)
2. Budashevsky, V.G., Pastukhova, O.N.: Tekhnologiya adaptivnogo upravleniya
sinergeticheskim vzaimodeystviyem sprosa i predlozheniya na osnove proyektno-
issledovatel’skogo kompleksnogo marketingovogo eksperimenta (Technology of
adaptive management of the synergistic interaction of supply and demand on the
basis of a project-research complex marketing experiment). Bulletin of the South
Ural State University. Ser. Economics and Management 10(4), 60–65 (2016), (in
Russian)
3. Galyautdinov, R.R.: The mechanisms of interaction of flows and stocks at enter-
prise from the perspective of logistics. Bulletin of the South Ural State University.
Ser. Economics and Management 10(1), 157–163 (2016)
4. Levina, A.L.: Klassifikatsiya predpriyatiy roznichnoy torgovli s uchetom priznakov
logisticheskoy integratsii (Classification of retail enterprises taking into account the
signs of logistical integration). Bulletin of the South Ural State University. Ser.
Economics and Management 10(4), 170–175 (2016), (in Russian)
5. Panyukov, A., Teleghin, V.: Forming of discrete mechanical assembly production
program. Journal of Computational and Engineering Mathematics 2(1), 57–64
(2015)
314 A. Panyukov, K. Z. Chaloob
6. Panyukov, A., Telegin, V.: Tekhnika programmnoy realizatsii potokovykh algo-
ritmov (Engineering software implementation flow algorithms). Vestnik Yuzhno-
Ural’skogo gosudarstvennogo universiteta. Seriya: Matematicheskoe modelirovanie
i programmirovanie (Bulletin of South Ural State University. Series: Mathematical
modeling and programming) 27(127), 78–99 (2008), (in Russian)
7. Raskin, L., Kirichenko, I.: Mnogoindeksnyye Zadachi Lineynogo Program-
mirovaniya (Multi-index Problems of Linear Programming). Radio i svyaz’,
Moscow (1989), (in Russian)
8. Sira, O.V.: Raspredelitel’naya zadacha lineynogo programmirovaniya (Distribu-
tion linear programming problem). Systemy obrobky informatsiyi (Information
Processing Systems) 2(109), 168–170 (2013), (in Russian)
9. Stok, J.R., Lambert, D.M.: Strategic Logistics Management. McGraw-Hill/Irwin
(2000)
10. Yemelichev, V.A., Kovalev, M.M., Kravtsov, M.K.: Polytopes, Graphs and Opti-
mization. Cambridge University Press, New York (1986)