About Local Optimum of the Weber Problem on Line with Forbidden Gaps

Abstract

The location problem of interconnected facilities on the line with forbidden gaps is considered. The located facilities are connected among themselves and with gaps. Location in forbidden gaps is not allowed. It is need to minimize the total cost of connections between facilities and between facilities and gaps. It is known that the initial continuous problem is reduced to series discrete subproblems of smaller dimension. In this paper the de nition of the local optimum of the problem is introduced. In order that to obtain the local optimum it is necessary to solve some subproblems. The variants of lower bounds of the goal function of the subproblems are proposed. The bounds can be used in the branch and bounds algorithm for solving the subproblems.

Keywords

• forbidden gaps
• local optimum
• lower bounds
• Weber problem

Introduction

The analysis and decision of location problems are intensively developing directions in

operations research [2, 4, 5, 17, 18]. Problems of such class have important applications and arise in various elds of activity: at designing of master plans of the enterprisers, arrangement of processing equipment in shops, de nition of the locations of the service stations, etc. The various statements of such problems are de ned by size of facilities, area in which they are located, various restrictions and types of criteria and so on.

An important subclass of the location problems of the interconnected facilities is the

Weber problem with criterion of minimum of total cost of connections [8, 12, 17, 18].

The Weber problem is an adequate model of many practical applications. For example, in automation of design of the complex systems can be the problem of placement of structural elements in the area with implementation of certain requirements [7, 16]. At designing of the plan of the petrochemical enterprise the facilities are the equipment [7, 16]. The equipment can be connected among themselves by various communications, for example, systems of the pipelines. Regularity of location often is required to ensure the straightforward paths and convenient maintenance along so-called \red" lines [15]. ⋆ This work was supported by grant 16{01{00740 from the Russian Foundation for Basic

Research.

Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org

The Weber problem with restrictions on facility location and/or traveling has been

considered widely in recent years [4, 6]. Depending on the type of restrictions, such problems are divided into three categories. The category considers planar facility location problems in which restrictions come from existence of forbidden regions (gaps). Forbidden gaps refer to prohibition of facility placement but allowance of free traveling. Moreover, some forbidden gaps may contain the equipment, for example, during modernization of the enterprise. In the second category, restrictions are imposed by barriers. Barriers are de ned as regions where neither locating a facility on not passing through is allowed. The last category considers restricted planar location problems with congested regions. Congested regions are bounded areas in the plane that forbid facility location however passing through their interior is possible at some extra traveling cost.

A broad overview on facility location problems with forbidden gaps is provided in [6].

If the facilities are commensurable to the area of location then they often are ap

proximated by the rectangles; otherwise, we may consider them as material points.

Various approaches to the problem of optimal location of the rectangles are developed

[1, 8{10, 13, 15]. In case the rectangles are unconnected, the two{dimensional problem of packing of the rectangles into the strip of the minimal length is considered in [9]. The problem is formulated as a mixed integer nonlinear programming problem. For solving this problem the probabilistic tabu search algorithm is developed. In [15] the location problem of the rectangles on the parallel lines is considered. For constructing a set of

Pareto{optimal solutions, integer optimization and dynamic programming are applied.

In [8, 10], the algorithms of local optimization on the plane and dynamic programming

on the line without forbidden gaps are described. For the problem in which the rectangles can be rotated and it is possible to create routes for establishing connections, the heuristic algorithm is proposed [1]. An important subclass of problems of optimal location of rectangles is the VLSI chip design problems. The wide review of practical applications and various approaches for solving such problems is provided in [13].

In this paper, we study the Weber problem on the line with forbidden gaps. The located facilities are segments, for example, projection of the rectangles onto the line. It is known that the initial continuous problem is reduced to series discrete subproblems of smaller dimension. All subproblems have identical structure. The local optimum of the problem is obtained by solving some subproblems. The variants of lower bounds of the goal function of the subproblems are proposed. The bounds can be used in algorithms for solving of the subproblems, for example, in the branch and bounds algorithm. 2

Problem Formulation and Basic Properties

The Weber problem on the line with forbidden gaps is formulated as follows. Consider

a straight{line segment of length LS containing some xed rectilinear areas (forbidden gaps). It is necessary to locate on this line facilities which are the segments, whose centers are connected with each other and with the forbidden gaps. Location in forbidden gaps is not allowed. The problem is to locate facilities on the segment of length

LS outside the forbidden gaps so that they do not intersect each other and, moreover, the total cost of connections between the facilities and between facilities and gaps is

minimized [17]. Without loss of generality, we can assume that the left border of the segment of length LS is the origin.

Let Xi and Fj denote the facilities and gaps with the centers at xi and bj and lengths of li and pj , where i 2 I = f1; : : : ; ng and j 2 J = f1; : : : ; mg; while wij 0, uik 0 are the speci c costs of connections between Xi and Fj , Xi and Xk for i, k 2 I, j 2 J , and i < k. The target is to locate the facilities X1; : : : ; Xn on the segment outside gaps F1; : : : ; Fm and so that they do not intersect with each other and the total cost of the connections between the facilities and between facilities and gaps is minimized.

The mathematical model under consideration is as follows:

n m G(x) = ∑ ∑ wij jxi i=1 j=1 n 1 n bj j + ∑ ∑ i=1 k=i+1 uikjxi xkj ! min; jxi

bj j jxi xkj li 2 li + pj

2

The rst component in (1) de nes the total cost of connections between facilities and gaps; the second part de nes the total cost of connections between the facilities themselves; and (2) and (3) are the conditions of disjointness.

The feasible area B is disconnected and consists of the set of r disjoint segments

(blocks) Bk of length Lk that contain the facilities Xi, i 2 I, B = ∪k=1;r Bk. The problem ( 1 ){( 4 ) is NP-hard; a feasible solution to the problem can be found by construction of a one{dimensional packing into containers [3]. In this case, the facilities with lengths of li, i 2 I, are packed into containers with sizes Lk, k = 1; r. Moreover, if there are no gaps then ( 1 ){( 4 ) is an optimal linear ordering problem [11] which is

NP-hard for an arbitrary set of connections between the facilities.

In [17] the algorithm for obtaining an approximate decision in two phases is offered. In the rst phase, we nd an feasible partition of the facilities into blocks, and in the second phase, the facilities in the blocks are interchanged for the purpose of minimization of total cost of connections. A computational experiment with this algorithm and solving of the problem using IBM ILOG CPLEX and a mixed-integer linear programming model is considered. This work is continuation of researches of the problem ( 1 ){( 4 ).

Given a feasible location, a remainder in the block Bk is a segment between two

adjacent facilities that do not have a common border or between the border of Bk and an adjacent block. A block without facilities is called a block with remainder. Two elements (facilities, gaps, remainders) are called glued if they have a common border.

Let JL(Bk) and JR(Bk) denote the set of gaps to the left and to the right of the block Bk, let IL(A) and IR(A) denote the set of facilities to the left and to the right of

the block (gap) A correspondingly. Given an facility Xi in Bk, let Lwi and Rwi denote the total cost of connections for Xi de ned as

Lwi =

∑ Let x = (x1; : : : ; xn) be a feasible solution of ( 1 ){( 4 ) that uniquely de nes the partition of X1; : : : ; Xn into blocks. Let Ik(x) denote the set of the facility's numbers in Bk, I = ∪k=1;r Ik(x), and let Hk(x) denote the set of remainders in Bk for x. Let nk denote the size of set Ik(x), then jHk(x)j nk + 1. Note that x can be represented as x = (x1; : : : ; xr), where xk is the coordinates of the centers of the facilities that are located in Bk and have numbers from Ik(x).

Proposition 1. (see [17]) Given a feasible solution x of ( 1 ){( 4 ), we can nd a feasible solution x′ such that jHk(x′)j 1; k = 1; : : : ; r;

G(x′)

G(x):

Thus in each block Bk it is possible to consider no more than one remainder, length of which we denote by ∆k.

Let LBk and RBk denote the coordinates of the left and right borders of Bk. Then,

for a xed partition of facilities into blocks, the goal function G(x) can be presented as r G(x) = ∑ Gk(xk) + C; k=1 ( 5 ) where

C is some constant.

The rst component of Gk(xk) is the sum of costs of connections between the

facilities in Bk, the second is the total cost of connections between the facilities from

Bk and LBk, and the third component is the total cost of connections between the

facilities from Bk and RBk. In the case when the area of location on the segment is bounded on the left and on the right by gaps, we have

Introduce the following de nition.

De nition 1. An admissible decision x of the problem ( 1 ){( 4 ) is called a local minimum if G(x) G(x′) for all x′ : Ik(x) = Ik(x′), k = 1; : : : ; r.

Let the partition of the facilities into blocks is xed. Then in each block Bk it is possible

to consider the subproblem of location nk + 2 facilities. In Bk the subproblem contains two xed facilities and nk located facilities. Denote by FL and FR the xed facilities.

The facilities are located in the points with coordinates LBk and RBk respectively.

Denote by wiL and wiR the cost of connections between located facilities in Bk and xed facilities LBk and RBk respectively for each i 2 Ik(x) and then wiL = wiR = ( ( s2JL(Bk) ∑ ∑ s2JR(Bk) wis + wis + t2IL(Bk) ∑ ∑ t2IR(Bk)

) uit ;

) uit :

With the preceding designations the subproblem for Bk can be presented as

LBk + l2i xi RBk l2i ; i 2 Ik(x): ( 8 )

It is need to nd coordinates xk of the centers facilities in Bk, so that the total cost

of connections between located facilities among themselves and with FL and FR is minimized.

As Ik(x) ∩ Il(x) = ∅ for all k; l = 1; : : : ; r, then to nd a local optimum for some xed partition of the facilities into blocks, it is sufficiently to nd the minimum in r independent subproblems ( 6 ){( 8 ). These subproblems have identical structure. Proposition 2. For search of the local minimum of the problem ( 1 ){( 4 ) it is sufficiently to solve r subproblems ( 6 ){( 8 ).

The proof of proposition 2 follows from representation of the goal function (5).

Note that the process of search of the local minimum can be parallelized as solving r independent subproblems (6){(8).

The properties stated above allowed to reduce the initial continuous problem to series of discrete subproblems of smaller dimension. For nding of the local optimum of the problem it is need to solve r subproblems. (6)

( 7 )

Solving of the problem ( 1 ){( 4 ) is sequential performance of two phases. In the rst phase, we nd feasible partition of the facilities into blocks by means of the algorithm [17]. In the second phase, for obtained partition the series of the subproblems of smaller dimension are solved. Thus we ned the local optimum of the problem ( 1 ){( 4 ). The local optimum with minimal value of the goal function is the exact decision of the problem ( 1 ){( 4 ). For the search of approximate decision of the problem ( 1 ){( 4 ) the stopping criteria of the algorithm may be running time, number of iterations, nding of the exact decision or given estimate of accuracy. Note that the number of possible partitions Xi, i 2 I into the blocks B1; : : : ; Br is at most rn. The remainder in Bk can be considered as the additional located facility Xnk+1, for which lnk+1 = ∆k and Lwnk+1 = Rwnk+1 = 0.

Note that if ust = 0; 8s; t 2 Ik(x); s < t, then in the second phase the exact decision for the subproblem ( 6 ){( 8 ) is found by the polynomial algorithm [17]. In this case the graph, whose tops are the left and the right borders of the block Bk and the facilities in Bk, has a series{parallel type with one top on each chain between the source and the sink. For such structure of the graph the effective algorithm is offered in [14].

Generally, if 9s; t 2 Ik(x) : ust > 0, then for solving the subproblem (6){(8) for

small value nk, it is possible to use nk! permutations of the facilities into block. In general case it is possible to apply, for example, the branch and bounds algorithm. In the algorithm calculation of the lower bounds of the goal function is important. 3

Lower Bounds

Let some located facilities in Bk are glued to the left border of Bk, some located facilities

are glued to the right border of Bk, and some facilities aren't located yet. Denote by N Fl, N Fr the sets of the located facility's numbers in Bk, then Ik(x)nfN Fl ∪ N Frg is the set of the unlocated facility's numbers. Without loss of generality, we shall consider that the facilities in the set N Fl have numbers from 1 to s, and in the set N Fr the facility's numbers are from t + 1 to nk. Denote by D the set of the admissible locations of the facilities in Bk when N Fl and N Fr are de ned (partial location). Let (D) be the lower bound of function Gk(xk) for the set D. Then (D) can be presented as the sum of three components. The rst component 1(D) is the total cost of connections between the located facilities themselves and with FL and FR. The second component

2(D) is lower bound of total cost of connections the unlocated facilities with FL, FR

and with the located facilities in Bk. The third component 3(D) is lower bound of total cost of connections between the unlocated facilities themselves. Thus (D) can be presented as

(D) = 1(D) + 2(D) + 3(D):

The coordinates of the centers of the located facilities are known and 1(D) can be calculated as follows

∑ ∑ ∑ 1(D) = (

∑

Further two variants of calculation 2(D) are offered.

The rst variant. For each i 2 Ik(x)nfN Fl ∪ N Frg the total cost of connections between the located facilities themselves and with FL and FR is determined as follows ∑ k2NFl SL(i) = Lwi + uik;

SR(i) = Rwi +

∑ k2NFr uik:

Further location of the unlocated facilities in Bk is de ned in two ways. In the rst

way, the facilities are ordered by not increase of the relations SL(i)=li. The facilities consistently are pasted together in that order with the most left located facility in Bk.

Let, for simplicity of designations, the glued unlocated facilities have numbers from s + 1 to t.

In the second way, the unlocated facilities are ordered by not increase of the relations

SR(i)=li. The facilities consistently are pasted together in that order with the most right located facility in Bk. Let the glued unlocated facilities have numbers from t to s + 1. Then

2(D) = 2L(D) + 2R(D); where 2L(D) and 2R(D) are the lower bounds of total cost of the connections unlocated facilities with FL, FR respectively and with the located facilities in Bk.

In both cases we receive some permutation of facilities in the block Bk. Consider

the permutation and two distinct facilities Xi and Xj in Bk. The distance between

Xi and Xj with respect to this permutation, assumed to be taken their centers, is equal

to the half-length of Xi, plus the lengths lk of all facilities which are between Xi and

Xj in , plus the half-length of Xj . The half-length of Xi plus the half-length of Xj is

the constant. Thus, at the calculation of the distance between the facilities Xi and Xj it is sufficient to consider only the lengths lk of all facilities which are between Xi and

Xj in . Then 2L(D) and 2R(D) can be calculated as follows: 2L(D) =

∑t ( q=s+1 q 1 Lwq ∑ lg + g=1 ∑s uqi ∑q1 lk); i=1 k=i+1 2R(D) = ∑t ( nk Rwq ∑ lg + nk ∑ uqi ∑i1 lk): q=s+1 g=q+1 i=t+1 k=q+1

The proof that 2L(D) and 2R(D) are the lower bounds of the total cost of connections

unlocated facilities with FL, FR and with the located facilities in Bk is similar to the proof in [10].

The second variant. The set Ik(x)nfN Fl ∪ N Frg can be presented as union of non{ crossing sets NL ∪ NC ∪ NR, where by NL, NC , NR are denoted the sets of facility's numbers for which SL(i) > SR(i), SL(i) = SR(i), SL(i) < SR(i) respectively.

Further facilities with numbers from NL are ordered by not increase of the relations

(SL(i) SR(i))=li. The facilities consistently are pasted together in that order with the most left located facility in Bk. The facilities with numbers from NR are ordered by not increase of the relations (SR(i) SL(i))=li, and they consistently are pasted together in that order with the most right located facility. The facilities with numbers from NC are located between sets of the facilities with numbers from NL and from NR in any order.

Thus, for each i 2 Ik(x)nfN Fl ∪ N Frg coordinate of the center is determined. Let Ik(x)nfN Fl ∪ N Frg = fs + 1; : : : ; tg as well as earlier. Determine the following value Z as

Z = ∑t ( q=s+1

q 1 s q 1 nk nk Lwq ∑ lg + ∑ uqi ∑ lk + Rwq ∑ lh + ∑ uqj g=1 i=1 k=i+1 h=q+1 j=t+1 ∑j1 lv): v=q+1 ( 9 ) Proposition 3. The value Z is the lower bound of the total cost of connections the unlocated facilities with FL, FR and with the located facilities in Bk.

Proof. Let NL ̸= ∅ and NR = ∅ and NC = ∅. Without loss of generality, we consider the case when N Fl = ∅ and N Fr = ∅. Otherwise it is possible to rede ne the cost of connections the unlocated facilities with FL, FR and with the located facilities. Then the set of the unlocated facility's numbers is Ik(x) and Lwi > Rwi for each i 2 Ik(x).

Let (Lw1 Rw1)=l1 > : : : > (Lwnk Rwnk )=lnk , then the facilities are located in order X1; : : : ; Xnk according to the second variant of the calculation 2(D). Denote by = (1; : : : ; nk) the permutation of numbers facilities corresponding to order

X1; : : : ; Xnk and denote by Z( ) the value Z for . On the formula (9) we receive

Z(

) = Lw2l1 + : : : + Lwt(l1 + : : : + lt 1) + Lwt+1(l1 + : : : + lt) + + : : : + Lwnk (l1 + : : : + lnk 1) + Rw1(l2 + : : : + lnk ) + : : : + +Rwt(lt+1 + : : : + lnk ) + Rwt+1(lt+2 + : : : + lnk ) + : : : + Rwnk 1lnk :

To prove that Z( ) is the lower bound for Z( ), where is any permutation of

numbers facilities from Ik(x). Assume, that Z( ) is not minimum. Then there is other permutation , such that Z( ) > Z( ). Any permutation can be received by series of transposition of adjacent numbers, then it is sufficiently to consider the proof for change the position of two adjacent facilities. Denote by = (1; : : : t 1; t + 1; t; t + 2; : : : ; nk), then on the formula ( 9 ) we receive

Z( ) = Lw2l1 + : : : + Lwt+1(l1 + : : : + lt 1) + Lwt(l1 + : : : + lt 1 + lt+1) + + : : : + Lwnk (l1 + : : : + lnk 1) + Rw1(l2 + : : : + lnk ) + : : : + +Rwt+1(lt + lt+2 + : : : + lnk ) + Rwt(lt+2 + : : : + lnk ) + : : : + Rwnk 1lnk :

By assumption Z(

)

Z( ) > 0, then Z( )

Z( ) = Lw2l1 + : : : + Lwt(l1 + : : : + lt 1) + Lwt+1(l1 + : : : + lt) + + : : : + Lwnk (l1 + : : : + lnk 1) + Rw1(l2 + : : : + lnk ) + : : : + +Rwt(lt+1 + : : : + lnk ) + Rwt+1(lt+2 + : : : + lnk ) + : : : + Rwnk 1lnk Lw2l1 : : :

Lwt+1(l1 + : : : + lt 1)

Lwt(l1 + : : : + lt 1 + lt+1) : : : Lwnk (l1 + : : : + lnk 1)

Rw1(l2 + : : : + lnk ) : : :

Hence

Rwt+1(lt + lt+2 + : : : + lnk )

Rwt(lt+2 + : : : + lnk ) : : :

Rwnk 1lnk = = (Lwt+1

Rwt+1)lt (Lwt

Rwt)lt+1 > 0: lt+1 Lwt+1

Rwt+1 > Lwt lt

Rwt : It is the contradiction with inequalities (Lw1 Rw1)=l1 > : : : > (Lwt Rwt)=lt > (Lwt+1 Rwt+1)=lt+1 > : : : > (Lwnk Rwnk )=lnk .

The proof for the subset NR ̸= ∅ is similarly. Note that facilities with numbers from

NC can be located in arbitrary order.

Proposition is proved.

Therefore, in the capacity of 2(D) it is possible to use the value Z.

Following way may be use for the calculation of 3(D). Let for the facilities Xs; Xt; Xq, s; t; q 2 Ik(x)nfN Fl ∪ N Frg take place inequalities ust > 0, usq > 0, utq > 0. Considering any three of the interconnected facilities, value of 3(D) can be calculated, for example, as follows 3(D) =

∑ s;t;q2Ik(x)nfNFl ∪ NFrg minfustlq; usqlt; utqlsg: 4

Conclusion

The NP{hard location problem of interconnected facilities on the line with forbidden gaps is considered. It is need to minimize the total cost of connections between the facilities and between the facilities and gaps. It is known that the initial continuous problem is reduced to series discrete subproblems of smaller dimension. For nding of the local optimum of the problem it is need to solve some subproblems. Two variants of lower bounds of the goal function of the subproblems are proposed. The bounds can be used in the branch and bounds algorithm for solving the subproblems.

References

1. Erzin , A. , I. , Cho , J., D. : Concurrent Placement and Routing in the Design of Integrated Circuits . Avtomat. i Telemekh . No. 12 , 177 { 190 ( 2003 ) [Automat . Remote Control 64 ( 12 ), 1988 { 1999 ( 2003 )]

2. Farahani , R., Z. , Hekmatfar , M. : Facility location: Concepts, models, algorithms and case studies . Heidelberg: Physica-Verlag, ( 2009 )

3. Garey , M. , R. , Johnson ,D., S. : Computers and Intractability: A Guide to the Theory of NP{Completeness . (Freeman, San Francisco, 1979 ; Mir, Moscow, 1982 )

4. Klamroth , K. : Single-Facility Location Problems with Barriers. Springer Series in Operations Research, ( 2002 )

5. Kochetov , Yu., A. , Panin , A. , A. , Plyasunov , A. , V. : Comparison of metaheuristics for the bilevel facility location and mill pricing problem . Diskret. Anal. Issled. Oper . 22 ( 3 ), 36 - 54 ( 2015 ) DOI: 10 .17377/daio. 2015 . 22 .465

6. Nickel , S. , Puerto , J.: Location theory. A uni ed approach . Berlin: Springer, ( 2005 )

7. Legkih , S. , A. , Nagornay , Z. , E. , Zabudsky , G., G.: Automation of design of plans of production sites and shops of the sewing enterprises (in Russian) . Nat. Tech. Scien. No. 4 , pp. 261 { 266 ( 2005 )

8. Panyukov , A. , V. : The problem of locating rectangular plants with minimal cost for the connecting network . Diskret. Anal. Issled. Oper. Ser. 2 , 8 ( 1 ), 70 { 87 ( 2001 )

9. Rudnev , A., S. : Probabilistic tabu search algorithm for the packing circles and rectangles into the strip . Diskret. Anal. Issled. Oper . 16 ( 4 ), 61 { 86 ( 2009 )

10. Simmons , D. , M. : One-dimensional space allocation: an ordering algorithm . Oper. Res . 17 ( 5 ), 812 { 826 ( 1969 )

11. Suresh , G. , Sahu , S. : Multiobjective Facility Layout Using Simulated Annealing . Int. J. Prod. Econom . 32 ( 2 ), 239 { 254 ( 1993 )

12. Trubin , V. , A. : Effective algorithm for Weber problem with a rectangular metrics . Kibernet. No. 6 , 67 { 70 ( 1978 ) [Cybernetics 14(6 ), 874 { 878 ( 1978 )]

13. Wai{Kai, Chen: The VLSI Handbook . CRC Press. ( 2000 )

14. Zabudsky , G., G.: On the problem of the linear ordering of vertices of parallel-sequential graphs . Diskret. Anal. Issled. Oper . 7 ( 1 ), 61 - 64 ( 2000 )

15. Zabudskii , G. , G. , Amzin , I. , V. : Algorithms of compact location for technological equipment on parallel lines (in Russian) . Sib. Zh. Ind. Mat . 16 ( 3 ), 86 { 94 ( 2013 )

16. Zabudsky , G. , G. , Legkih , S. , A. : Mathematical model of optimization of exible modules of processing equipment (in Russian) . Appl. Math. Inf. Technol. Omsk: Publishing House of OMGTU , pp. 20 { 28 ( 2005 )

17. Zabudskii , G. , G. , Veremchuk , N., S.: An Algorithm for Finding an Approximate Solution to the Weber Problem on a Line with Forbidden Gaps . Diskret. Anal. Issled. Oper . 23 ( 1 ), 82 - 96 ( 2016 ) [ J. Appl. Ind. Math. 10 ( 1 ), 136 { 144 ( 2016 ) DOI: 10 .1134/S1990478916010154]

18. Zabudsky , G. , G. , Veremchuk , N., S. : Solving Weber problem on plane with minimax criterion and forbidden gaps (in Russian) . IIGU Ser. Matematika , Vol. 9 , pp. 10 { 25 ( 2014 )