Problem of Distribution of Goods by Logistics Centers

Abstract

E ective 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 e ective operational management of a network marketing organization. In the paper, algorithms for analyzing and solving the problem of distribution of goods by logistics centers, including decision support system in case of incorrectness of the arising problem are proposed: (1) the method of regularization of the decomposable distribution problem; (2) an e ective algorithm for approximating an indecomposable problem by a decomposable problem. The software implementation of the proposed algorithms is easily encapsulated in the MS O ce system.

Keywords

• Logistics center
• Transport problem
• Operational manage- ment
• Distribution task
• Regularization
• Decomposition
• Algorithm

-

A enterprise is a complex and dynamic system actively interacting with the external environment. Currently, e ective 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 marketing 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 e ective 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 are proposed in the paper. Software implementation of these algorithms is easily encapsulated in the MS O ce system [5, 6].

In the rst 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 decomposable case of a problem reducible to the transport problem with matrix formulation. In the third section we propose a method for regularizing a decomposable 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 2 I distributed to the center j 2 J . Let pij be the marginal pro t from the sale of a unit of commodity i 2 I at the center j 2 J . Let ij be the cost of distribution of a unit of commodity i 2 I by the center j 2 J . Let di be the e ective demand for the commodity i 2 I. Let bj be the resource for the maintenance of the center j 2 J . The formal formulation of the problem consists in nding the distribution of goods i 2 I at the centers j 2 J , for which the marginal pro t is maximal all goods are satis ed with the e ective demand resource constraints have been met for all centres xo = arg max X X pij xij ;

x2D j2J i2I X xij = di; j2J 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 speci city, 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. ( 1 ) ( 2 ) ( 3 ) ( 4 )

The Decomposable Case of Task ( 1 )-( 4 ) For some cases, the parameter ij can be represented as the product ij = i j ; i 2 I; j 2 J ( 5 ) where i is the resource intensity of the commodity i 2 I in conventional units, j is the cost of servicing the conventional unit at the center j 2 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 2 J we have

X i2I ,

X i2I i j xij

X

, ixij here yij = i xij for all i 2 I; j 2 J . Passing to the variables yij = all i 2 I; j 2 J in problem ( 1 )-( 4 ) get bj ! j

X yij i2I bj ! j

; i xij for 0

X

X yij = j2J di i 1 A ; Thus, the problem ( 1 )-( 4 ) is equivalent to the following one yo = arg max X X pij yij ;

x2D j2J i2I i X yij = j2J X yij i2I yij 0; di i ; bj ; j

i 2 I j 2 J ; The problem ( 6 )-( 9 ) is open matrix transportation problem [7, 8]. The encapsulated in the MS O ce system software to solve such problems of large dimension is known [6].

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.

S =

X di i

X bj j2J j 0: 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 nd a suitable solution. Possible ways to adjust the conditions of these tasks are: 1. To allow the supply of all goods below the e ective demand 2. To develop the infrastructure of all routes in order to e ectively support the e ective demand where y0j is the amount of investment (in conventional units) in the development of the route j 2 J .

Let ki be the allowed fraction of the unsatis ed demand for the commodity i 2 I (i.e. yi0 kidi). Let p0j be the amount of investment required to expand the resources of the center j 2 J by one conditional unit.

Let us consider the corrected problem taking into account the variables and restrictions introduced in this section.

yo = arg max X y2D j2J

X pij yij i2I

i X yij + yi0 = j2J X yij i2I

yi0 yij ; yi0; y0j y0j = kidi; 0; di i ; bj ; j

! p0j y0j

; The problem ( 10 )-(14) is closed matrix transportation problem [7]. The encapsulated in the MS O ce system software to solve such problems of large dimension is known [6].

Obviously, problem ( 10 )-(14) has an optimal solution. The regularization is carried out by introducing additional endogenous variables yi0; y0j 0; i 2 I; j 2 J , exogenous variables ki; i 2 I, and constants p0j ; j 2 J .

It is evident from the constructed model that at xed prices maintaining e ective demand leads to a decrease in marginal pro t. Preservation of marginal pro t requires an increase in the selling price of goods, which can lead to an irreversible decrease in demand and a decrease in marginal pro t. 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 2 I.

Let us use the marginal pro t 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 xed values of the exogenous variables ki; i 2 I. The problem of choosing speci c values of these variables is di cult 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 2 I by the center j 2 J , and its value can be determined using statistical measurements. On the contrary, the parameters f i > 0 : i 2 Ig, f j > 0 : j 2 J g 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 f i > 0 : i 2 Ig, f j > 0 : j 2 J g. It is clear that for arbitrary values ij the system of equations ( 5 ) may be inconsistent.

Let us introduce the function

F ( ; ) =

X 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 in mum is reached, and the optimal approximate solution of the system ( 5 ) with a minimal degree of incompatibility ( o; o) = arg

2 min 4 f j>0: j2Jg i2I; j2J f i:>0: i2Ig

X log i j ij 3 5 can be considered.

It is easy to see that the optimality of the solution ( o; o) implies the optimality of the solution set D = f( o c; o=c) : c > 0g. We shall assume that the solution of the approximating problem is ( ; ) = arg ( m;i)n2D k( ; )k1 : (15) Note that if ( ; ) 2 D then

( = ak s maxj2J j

) maxi2I i k2I ; = k r maxi2I i maxj2J j k2J : Thus, the correct formulation of the approximating problem is two-level, but for its solution it is su cient to nd 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;

Output:

= f ij gi2I; j2J ; = f igi2I ; = f j gj2J ; F ( ; ); Step 1. (Construct matrix ^ ). For each line i 2 I of the matrix 1.1, 1.2 and 1.3, then go to step 2.

Step 1.1. Build sorted line i 2 I [i] = n (k)

ij(k) : ^ [ ] [j] = n^(k)

i(k)j : k = 1; 2; : : : ; jJ j ; j(k) 2 J; i(j1()1) ( 2 ) ij( 2 ) : : :

Step 1.2. Let k

= j jJj+1 k ; k+ = l jJj+1 m ; i = 2 2 r (k+)

ij(k+) = j jIj+1 k ; k+ = l jIj+1 m ; 2 2 j = r^(k+) i(k+)j ^i((kk ))j . execute steps i(jjJ(jjj)j) ; (k ) . ij(k ) o :

^(k) (k) Step 2.3. For k = 1; 2; : : : ; jIj let eli(k)j = i(k)j : j Step 3. (Normalization). Follow steps 3.1, 3.2, and 3.3, and then go to step 4.

Step 3.1. Let c = r maxi2I i : Step 4. Let F ( ; ) = Pi2I; j2J Step 5. Return n

maxj2J j Step 3.2. For all i 2 I let i = i=c.

Step 3.3. For all j 2 J let j = j c.

log i j .

ij = f igi2I ; End.

= f j gj2J ; F ( ; )o.

Theorem 1. Decomposition algorithm correctly solves problem (15). Its algebraic computational complexity does not exceed the value O (jIj jJ j log (jIj jJ j)). Proof. Monotony of the logarithmic function implies log i j = 0 ij

, ( log ij + log i + log j = 0) , lij + xi

yj = 0; lij = log ij ; xi = log i; yj = log j ; i 2 I; j 2 J; Therefore problem (15) is equivalent to problem (xo; yo) = arg min x2RjIj i2I; j2J y2RjJj

X j lij + xi yj 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 Making the change of variables gij = fij fji; i 2 I; j 2 J in problem (19)-(22) we get the problem of maximum weight circulation

X gij

X 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 = fwij = tij + tji : i 2 I; j 2 J g) 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 = flij i 2 I; j 2 J g; Output: x = fxi i 2 Ig ; y = fyj j 2 J g ; FL(x; y); Step 1. (Construct matrix L^). For each line i 2 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 2 I

L [i] = nl(k) ij(k) : k = 1; 2; : : : ; jJ j ; j(k) 2 J; li(j1()1) ( 2 ) lij( 2 ) : : : li(jjJ(jjj)j) ; o :

Step 1.2. Let k

(k+) +lij(k )

(k ) = j jJj+1 k ; k+ = l jJj+1 m ; ri = lijk+) 2 2 2 .

Step 1.3. For k = 1; 2; : : : ; jJ j let ^li(jk()k) = li(jk()k) ri: Step 2. (Construct matrix L~ ). For each column j 2 J of the matrix L^ execute steps 2.1, 2.2 and 2.3, then go to step AUX. Step 2.1. Build sorted column j 2 J

L^ [ ] [j] = n^li((kk))j : k = 1; 2; : : : ; jJ j ; j(k) 2 J; ^li((11))j ^( 2 ) li( 2 )j : : : ^li((jjIIjj))j o :

Step 2.2. Let k

Step 2.3. For k = 1; 2; : : : ; jIj let eli(k)j = ^li((kk))j (k)

sj : = j jIj+1 k ; k+ = l jIj+1 m ; sj = li(k+)j+^li((kk ))j .

^(k+) 2 2 2 Step AUX. (Construct matrix T) For all i 2 I; j 2 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

End.

Here an auxiliary step AUX is introduced to prove the e ectiveness of the algorithms. The optimal values of the variables tij ; tji; i 2 I; j 2 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 2 I; j 2 J there is an inclusion gij 2 f 1; 0; 1g. Let us to construct the solution fgij i 2 I; j 2 J g 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 2 I; j 2 J such that tij = 0; tji > 0; ( 2 ) gij = 1 for all i 2 I; j 2 J such that tij > 0; tji = 0; ( 3 ) gij = 0 for all i 2 I; j 2 J such that tij = tji = 0.

It is easy to see that the constructed solution fgij i 2 I; j 2 J g is an admissible solution of problem (23)-(26). It follows form the second duality theorem in linear programming that (r; s; t) and fgij i 2 I; j 2 J g are optimal solutions of the problems (23)-(26) and (27)-(28) correspondingly. The e ectiveness 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(jJ j log jJ j)) and recalculation of its elements (computational complexity O(jJ j)). Consequently, computational complexity of Step 1 does not exceed values O(jIjjJ j log (jJ j) ). Analogous arguments for Step 2 lead to the validity of the assertion that computational complexity of Step 2 does not exceed O(jIjjJ j log (jIj) ). Therefore, the total computational complexity of Steps 1 and 2 will not exceed the values O(jIjjJ j log (jIjjJ j) ). Step 3 consists of computation of value c and recalculation of values = f i i 2 Ig ; = f j j 2 J g , its computational complexity does not exceed O(jIjjJ j). Step 4 consists of summing the O(jIjjJ j) elements, its computational complexity does not exceed O(jIjjJ j) as well. Thus, computational complexity of the algorithm does not exceed O(jIjjJ j log (jIjjJ 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 incorrectness of the task. Software implementation of these algorithms is easily encapsulated in the MS O ce system.

References

1. Bayev , I.A. , Drozin , D.A. : Dinamika pokupatel'skogo sprosa innovatsionnogo tovara (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 proyektnoissledovatel'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 ows and stocks at enterprise 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. : Klassi katsiya predpriyatiy roznichnoy torgovli s uchetom priznakov logisticheskoy integratsii (Classi cation 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 )

6. Panyukov , A. , Telegin , V. : Tekhnika programmnoy realizatsii potokovykh algoritmov (Engineering software implementation ow algorithms) . Vestnik YuzhnoUral'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 Programmirovaniya (Multi-index Problems of Linear Programming) . Radio i svyaz' , Moscow ( 1989 ), (in Russian)

8. Sira , O.V. : Raspredelitel'naya zadacha lineynogo programmirovaniya (Distribution 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 Optimization. Cambridge University Press, New York ( 1986 )