On Multi-Level Network Facility Location Problem

Abstract

The article is intended to ll the recent review of OrtizAstorquiza, C. at al. (2017) on multi-level facility location problem (MLFLP). The article presents the results of some publications, information about which is missing in this review. We are talking about the construction of polynomial exact algorithms for solving some subclasses of the network MLFLP. Namely, the design of polynomial time algorithms for the multi-level FLP on a chain graph and the two-level FLP on a tree graph are discussed. We also show that the a known result of Trubin V. A. and Sharifov F.A. (1992) for the general multi-level FLP on a tree is incorrect.

Keywords

• Multi-level FLP
• Network
• Chain
• Tree
• Exact algorithm
• Polynomial time

-

In the multi-level network facility location problem (MLFLP) we are given a set of customers that have some product demands and a set of potential facilities partitioned into p levels. The problem is to open a collection of facilities, such that the customers are assigned to one or multiple sequences of opened facilities, one from each level p; p 1; : : : ; 1, while minimizing the total transportation cost and the cost of opening the chosen facilities.

The most common application of the MLFLP is the design of a productiondistribution system, where the distribution of a product is for example handled through the system of production plants, warehouses, and retailers [ 7 ]. Another popular application eld refers to the telecommunication systems and network design, where it is required to e ectively connect the terminals into a network building a system of routers and multiplexers [ 9 ].

The MLFLP in general is NP-hard even in the case of the one-level setting [ 1 ]. In 1977 Kaufman, Eede, and Hansen in [ 7 ] rst introduced the two-level FLP 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 as a warehouse and plant location problem. Since then, the generalizations and modi cations of the problem have been extensively studied, various heuristics and approximation algorithms are designed as well as the exact approaches such as branch-and-bound [ 7, 10, 12 ] and branch-and-cut [ 8 ] methods. We refer the reader to the recent survey paper [ 9 ] for a detailed overview of this kind of algorithmic results for the MLFLP. The purpose of the article is to supplement this review with some of the results of earlier publications not mentioned therein. In addition, we recall the advisability of a more compact formulation of the MLFLP using the so-called assignment vectors as decision variables.

Let's give a mathematical formulation for the p-level Network MLFLP. In the network statement of the MLFLP it is assumed that we are given a weighted graph G(N; E), where the set of nodes N = f1; : : : ; ng represents the set of customers; Mr N is the set of possible r-th level facility location sites, mr = jMrj; 1 r p; and the set E of the weighed edges represents the transportation network. We assume that the beginning of the production process takes place at the level p, further a facility of the level r receives the product from one or multiple number of facilities of the level (r + 1), 1 r p 1, and nally the product is supplied to the customers on the level 0. Denote by gir the cost of opening an r-th level facility at node i; bj the demand at node j; dip;:::i1;j the total cost of the shortest path transportation of product unit from the facility of the level p located at node ip through the sequence of the facilities of the lower levels p 1; : : : ; 1 at nodes ip 1; : : : ; i1 to the customer at node j.

The MLFLP then can be formulated as: subject to

X bj j2N

X : : : X ip2Mp i12M1 xip:::i1j dip:::i1j +

p X X giryri ! min r=1 i2Mr X : : : X ip2Mp i12M1

xip:::i1j = 1; j 2 N; X : : :

X

X

: : : X ip2Mp ir 12Mr 1 ir+12Mr+1 i12M1 xip:::i1j

yrir ; j 2 N; 1 r

p; ir 2 Mr; 0 xip:::i1j

1; j 2 N; i1 2 M1; : : : ; ip 2 Mp; yir 2 f0; 1g; 2 Mr; 1 r p: (1) (2) (3) (4) (5)

Here variables xip:::i1j are the allocation variables that stand for the proportion of product transported to the customer at node j through the sequence of facilities of levels p : : : 1 at nodes ip; : : : i1. The variables yri are the location variables, where yir = 1, if a facility of level r is opened at node i, and yir = 0 otherwise. The rst sum in (1) corresponds to the total transportation costs, and the second sum is the total cost of opening the chosen facilities. Constrains (2) stand for each consumer's demand is satis ed, while constrains (3) make sure that the allocation to the facility of the level r at node ir is possible only if it is open. If the allocation variables satisfy (4), each customer can be served by multiple sequences of opened facilities, and the problem is called multiple allocation MLFLP. If the allocation variables xip:::i1j 2 f0; 1g, each customer can be served by one sequence of opened facilities, and the problem is called single allocation MLFLP.

For the single allocation MLFLP there is a more compact formulation that uses the assignment vectors as variables. The similar formulation was introduced for the one-level facility location problem [ 3 ]. Let's use the following notation: { r = ( 1r; : : : ; nr)T is the facilities assignment vector on the level r, where { jr 2 Mr is the node in which the facility of the level r serving customer j is placed. { = ( 1; 2; : : : ; r) is the feasible solution of the problem; { Ir( ) = Sj2N f jrg is the set of facilities of the level r opened in the solution ; { Yir( ) is the service area of the facility i of the level r, i.e., the union over all j such that jr = i, where i 2 Mr and 1 r p.

It is clear that Ir( ) i 2 Ir( ); 1 r p.

Thus, the single allocation MLFLP can be stated as follows:

Mr and S Yir( ) = N , where the union is taken over all p X

X r=1 i2Ir( ) gir +

p X bj X j2N r=1 d jr jr 1 ! m(ijrn); (6) where dij is the length of the shortest path between nodes i and j in G.

In the following sections we consider it appropriate to recall some of the results in [4{6] for the Network MLFLP on the line and the tree graphs, and give some comments on Trubin's article [ 13 ]. 2

Some Known Facts about the Polynomial Solvability of the Chain MLFLP

In this section we are going to recall some facts about a special case of the single allocation Network MLFLP, where the given network is a chain (path). The transposition cost dij of the product unit between nodes i and j is the sum of the lengths of the edges in the subchain connecting these nodes. The rst algorithm Ap for the Chain MLFLP is based on the dynamic programming scheme under consideretion the original problem as D(Mr); 1 r p; N E and the family of subproblems: nD (Mrir ); ir 2 Mr; [1; j]E ir 2 Mr; 1 r p; 1 j no; where Mrs = [1; s] \ Mr; s 2 Mr, and 1 r p.

Denote by Lj(u) the optimal value of the objective function (the optimum) of each de ned subproblem, where u = (i1; i2; : : : ; ip) , and let Fjs(u); 1 s p; be the optima of the subproblems D (Mrir ); r 2 [1; p]; [1; j] jr = ir; s r pE: p It is clear, that F1(u) = P (girr + b1 cirir 1 ), where i0 = j, where we set gir equal r=1 to 1 if i 2= Mr; 1 r p. It is easy to see that the optimum F of the original problem D Mr; 1 r p; N E is equal to

F = min nFn1(u) ir 2 Mr; 1 r po:

Statement 1 [ 5 ]. The Chain MLFLP can be solved in O(pnm1m2 : : : mp)time using the following recurrent relations:

Fjs+1(u) = min nFjs(u); Fjs+1(u

es)o; p Fj1(u) = X(girr + bj cirir 1 ) + r=1

min 1<s p+1 nFjs 1(u hs)

p X girr o; r=s where Fjp+1(u) = Lj(u), es is a p-dimensional s-th orth, hs = sP1 er; 1 s p: r=1

Thus, the algorithm has time complexity linear in the number of the customers n and exponential in the number of levels p. Moreover, the bounds on time and space complexities coincide. 2.2

A Polynomial-time Algorithm Aep for the Chain MLFLP Another exact Algorithm Aep for the Chain MLFLP makes essential use of the inclusion property of optimal solutions and of reduction to a special series of the Nearest Neighbor Problems (NNP).

In the NNP we are given an integer segment (0; n] and a the cost function f (x; y) of serving each segment [x; y], 0 x; y; n. The problem is: m X f (xs 1; xs) ! 0=x0<:::<xm=n

min s=1 subject to 1 m

Statement 2 [ 5 ]. The time complexity of Algorithm Aep for solving the Chain MLFLP is O n3 Prp=1 mr .

Comparing algorithm Ap with running-time O(nm1m2 : : : mp) and algorithm Aep with running-time O n3 Pp

r=1 mr , it follows that the algorithm Ap runs faster than Aep, if

pm1 : : : mp m1 + : : : + mp n2:

Let m = maxfmr j 1 r pg. Then for the time complexities of Ap and Aep we have the upper bounds O(pnmp) and O(p m n3), respectively. It is clear that in the case of two- and three-level FLPs, the algorithm Ap is more e cient than Ap, but for the problem with the number of levels p > 3 the algorithm Aep is preferable. Also note, that the space complexity of the algorithm Ap is exponential in the number of levels, while the space complexity of the algorithm Aep stays polynomial. 3 3.1

Multi-level FLP on a Tree

An Exact Algorithm for the Tree 2-Level FLP

The question on existence of exact polynomial time algorithms for solving the Tree p-level FLP for p 3 remains open. Nevertheless, paper [ 6 ] gives an exact polynomial-time algorithm solving the Tree 2-level FLP based on the dynamic programming procedure. Let G = (N; E) be a tree network with the set N of nodes and the set E of edges, j E j = n 1: Let the node 1 be the root of this tree. For all j 2 N , let : Pj be a simple path from the root 1 to the node j; Nj = fj0 j j 2 Pj0 ; j0 2 N g; Ijr( ) = Sf jr0 j j0 2 Nj g; 1 r p; j ( ) = arg minfckj j k 2 I2( )g.

Statement 3 [ 6 ]. There exists an optimal solution of the 2-level FLP on a tree, such that for all j 2 N , the following inclusions

Ij1( )

Nj [ f j1g; Ij2( )

2

Nj [ f j g [ f j ( )g hold.

Let hM1; M2; N i be the original 2-level FLP on a tree. Consider the family of the following subproblems: h M1; M2; Nj i j j1 = i; j2 = k; j ( ) = k0; i 2 M1; k; k0 2 M2; 1 j n :

Denote by Fj (i; k; k0) the optimal value of the objective function of each de ned subproblem.

Statement 4 [ 6 ]. The Two-level FLP on a tree can be solved in O(nm1m22)time using for all j 2 N; i 2 M1 and k; k0 2 M2 , the following recurrent relations:

Fj (i; k; k0) = gi1 + gk2k0 + bj (cki + cij )+ + X minfFl; Fl(k0) l2Sj gk20 ; Fl(k; k0) gk2k0 ; Fl(i; k; k0) gi1

2 gkk0 g; where Fj (k; k0) = min Fj (i; k; k0); Fj (k0) = min Fj (k; k0); Fj = min Fj (k0), i2M1 k2M2 k02M2 gk2k = gk2 and gk2k0 = gk2 + gk20 for k 6= k0. Note that F = F1. 3.2

On Trubin's Result for the Tree MLFLP

In paper [ 13 ] the multiple allocation MLFLP with p levels on a tree network was studied. The authors claimed that the MLFLP on an n-vertex tree T1 can be reduced to a Simple Facility Location Problem (SFLP) on an np-vertex tree T2. Since the latter problem can be solved in polynomial time, the authors claimed that the MLFLP on a tree with a xed number of levels p possesses a polynomial time algorithm as well. Thus, for example, using an O(n log n) algorithm [ 11 ] for the SFLP, one can obtain an O(np log n) algorithm for the MLFLP on a tree.

The aim of this section is to prove that the reduction from the MLFLP to the SFLP presented in [ 13 ] is incorrect.

The reduction proposed in [ 13 ] maps the MLFLP on tree T1 to the following FLP on T2, which consists of several connected copies of the initial tree T1 (Fig. 1). The tree T2 is built in p steps. At the st step T2 = T1. After k 1 steps T2 consists of vertices vi numbered as (i1; : : : ; ik 1). At step k to each vertex vi = (i1; : : : ; ik 1) of T2 we attach the initial tree T1 rooted at vertex ik 1. Each new vertex j from the attached tree T1 is numbered as (i1; : : : ; ik 1; j) in the constructed tree T2. Opening a facility in the p-vector numerated vertex (i1; : : : ; ip) of T2 in the FLP corresponds to opening a facility of the level 1 at the vertex i1, a facility of the level 2 at the vertex i2 and so on in the tree T1 of the initial 2-level FLP. Thus the vertices of T2 enumerates all possible sequences of opened facilities on the p levels in the original problem. The customers of the FLP on tree T2 having their original demand are located in vertices (i; i; : : : ; i), 1 i n, in the Fig. 1 these vertices are (1; 1), (2; 2) and (3; 3). The cost gi1;:::;ip of opening a facility a vertex in T2 is said to be equal to the sum gi1;:::;ip = gi11 + gi22 + : : : + gipp (7) where gir is the cost of opening an r-th level facility, at vertex i in the original problem on thetree T1.

Let's introduce variables zi1;:::;ip equal to 1, if we open a facility at vertex (i1; : : : ; ip) 2 T2, and 0, otherwise. The authors [ 13 ] claim that the SFLP on T2, where the total cost of opening facilities calculates as

X : : : X ip2Mp gi1;:::;ip zi1;:::;ip is equivalent to the problem (1)-(5) on T1. The incorrectness of this claim follows from the

Counterexample. Consider the following 2-level FLP (1)-(5) on the tree T1 in the form of a line (path) with the set of vertices f1; 2; 3g and the set of edges ff1; 2g; f2; 3gg (Fig. 1). Let a1 = 2 and a2 = 3 be the cost of transportation of a product unit along the edges f1; 2g and f2; 3g, respectively. Let dij be the total cost of transportation of a product unit along the simple path between vertices i and j in T1, i; j = 1; 2; 3. Set the demand b1 = b2 = b3 = 1, and the following costs: | of opening second-level facilities: g12 = 1; g22 = 5; g32 = 1; | of opening rst-level facilities: g11 = 1; g22 = 1; g32 = 1.

The location variables yri in the optimal solution for (1)-(5) on the tree T1 obviously satisfy: y21 = y23 = y12 = 0; y22 = 1; y11; y13 2 f0; 1g. Let S(y11; y13) be the total cost of a feasible solution for our the example of MLFLP on T1. Then

S(1; 0) = a1b1 + 2a1b2 + (2a1 + a2)b3 + g22 + g11 = 19: Similarly, it is easy to see that S(1; 1) = 16; S(0; 1) = 23. Thus the optimal solution is opening a second level facility at vertex 2 and rst level facilities at vertices 1 and 3. The optimal value S of the objective function is 16.

Now let's consider the SFLP on tree T2 obtained from the two-level FLP on T1. It is clear that z12; z32 2 f0; 1g and zij = 0 for all other vertices (i; j) 2 T2. Let Q(z12; z32) be the total transportation and facility opening cost for a solution of the considered example on T2. Thus:

Q(1; 0) = g12 + a1b1 + 2a1b2 + (a2 + 2a1)b3 = 19;

Q(0; 1) = g23 + (a1 + a2)b1 + a2b2 + 2a2b3 = 23; Q(1; 1) = g12 + g23 + a1b1 + b2 minf2a1; a2g + b3 minf2a1 + a2; 2a2g = 21: Thus the optimum Q of the problem on T2 is equal to 19, which is larger then S . The obtained optimal solution for the problem consists in opening a facility at vertex (1; 2) 2 T2 which corresponds to opening a second level facility at vertex 2 and a rst level facility at vertex 1 in the original problem on T1.

The mistake in [ 13 ] obviously consists in setting the costs of opening the facilities for the problem on T2 as (7), since in this case the costs of opening the facilities on higher levels of the initial problem may be summed up several times. This leads to di erent costs of the optimal solutions in these two problems. The mistake can be xed as follows. Set for all r = 1; : : : ; p

Pr(z) = firjzi1;:::;ip = 1; (i1; : : : ; ip) 2 T2g , and set the costs of opening a facility at vertex (i1; : : : ; ip) 2 T2 as p X

X r=1 i2Pr(z) gir:

This way the initial problem (1)-(5) on the tree T1 indeed is equivalent to the location problem on the tree T2, but the latter one is not the Simple Facility Location Problem. 4

Conclusion

The purpose of this article was, in the rst place, to recall some of the results of constructing exact algorithms for solving the Network MLFLP on the chain and the tree graphs that were missed in the recent large review of OrtizAstorquiza, C. at al. (2017) [ 9 ].

Secondly, it was important to show that the polynomial-time algorithm presented by Trubin and Sharifov [ 13 ] for solving the Tree MLFLP is incorrect even in the particular case of the line graph.

Thus, we can state that at the present time the question of the complexity status of the Tree MLFLP (for the number of levels greater than 2) remains open and is waiting for its solution.

Acknowledgement. This research was supported by Russian Science Foundation (project 16-11-10041)

References

1. Garey , M.R. , Johnson, D.S.: Computers and Intractability. Freeman, San Francisco ( 1979 )

2. Gimadi , E.Kh.: Choice of optimal scales in a class of location, uni cation, and standardization problems . Upravlyaemye Sistemy 6 , 57 { 70 . Novosibirsk ( 1970 ), (in Russian)

3. Gimadi , E. Kh.: The problem of distribution on a network with centrally connected service areas . Upravlyaemye Sistemy 25 , 38 { 47 . Novosibirsk ( 1984 ), (in Russian)

4. Gimadi , E.Kh.: Exact algorithm for some multi-level location problems on a chain and a tree . In: Oper. Research Proceedings . pp. 72 { 77 . Springer-Verlag, Berlin ( 1997 )

5. Gimadi , E.Kh.: E ective algorithms for solving the multi-level plant location problem . In: Operations Research and Discrete Analysis. Mathematics and Its Applications . vol. 391 , pp. 51 { 69 . Kluwer Academic Publishers, Springer, Dordrecht ( 1997 )

6. Gimadi , E.Kh. , Kurochkin , A.A. : An e ective algorithm for the two-stage location problem on a tree-like network . Journal of Applied and Industrial Mathematics 7 ( 2 ), 177 { 186 ( 2013 )

7. Kaufman , L., Eede , M.V. , Haunsen , P.A. : A plant and warehouse location problem . Oper. Res. Quart . 28 ( 3 ), 547 { 554 ( 1977 )

8. Landete , M. , Marin , A. : New facets for the two-stage uncapacitated facility location polytope . Computational Optimization and Applications 44 ( 3 ), 487 { 519 ( 2009 )

9. Ortiz-Astorquiza , C. , Contreras , I. , Laporte , G.: Multi-level facility location problems . European Journal of Operational Research , 1 { 15 ( 2017 )

10. Ro , H. , Tcha , D.: A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints . European J. Oper. Res . 18 ( 3 ), 349 { 358 ( 1984 )

11. Shah , R. , Farach-Colton , M. : Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees . In: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA) . pp. 108 - 115 ( 2002 )

12. Tcha , D.W. , Lee , B. : A branch and bound algorithm for the multi-level uncapacitated facility location problem . European J. Oper. Res . 18 ( 1 ), 35 { 43 ( 1984 )

13. Trubin , V.A. , Sharifov , F.A. : The simplest multi-level location problem on a treelike network . Kibernet. Sistem. Anal. 6 , 128 { 135 . Kiev ( 1992 ), (in Russian)