Consider a graph G = (V, E). At the vertices of G there are consumers of some product and the possible places of its production. For each vertex i in V the demand volume b(i), the cost f (i) for opening a facility and the restriction a(i) on the facility's capacity are given. For each edge e in E, there are given the cost of the transportation of the product unit ce and the maximum quantity qe of a product that can be transported along this edge. It is required to place the facilities in a way they satisfy all demand with minimal total cost of opening facilities and delivering the product to consumers. We propose a pseudo-polynomial time algorithm solving the problem with restrictions on facility and edge capacities on a tree graph, and discuss a polynomial time algorithm solving the problem with restrictions on edge capacities in the case of a line graph given.
Facility location problems are the core problems in the operations research. As the name suggests, these problems are to determining the best location for one or more facilities in such a way that a certain set of demand points, or customers, are serviced in a satisfactory way. In order to evaluate a certain constellation of facilities and determining the best one, we require objectives or criteria and constraints on the system to be modeled. Numerous models have been proposed for a variety of different problems in the literature. We refer the reader to the survey paper [Klose & Drexl, 2005] and the book [Laporte et al., 2015] for a detailed overview of the results for different facility location problems and their applications.
Perhaps the best known problem of this kind is the Uncapacitated Simple Plant Location Problem (USPLP) or the Uncapasitated Facility Location Problem (UFLP) [Krarup & Pruzan, 1983]. In this problem it is required to select the places to open the facilities from a finite feasible set of m elements so that the total cost of serving a finite number n of customers is minimized. One of the first surveys on the exact and approximation algorithms for solving such problems is [Cornuejols et al., 1990]. The UFLP is well-known to be NP-hard, since the Vertex Cover Problem reduces to it evidently. Nevertheless, in the case of a line and a tree graphs the problem is polynomially solvable with the following running-times: for the line graph – O(mn) [Beresnev et al., 1978], O(n2) [Cornuejols et al., 1990], for the tree graph – O(n3) [Trubin, 1976, Kolen, 1983], O(n2) [Kolen, 1983], O(mn) [Gimadi, 1983, Mirchandani & Francis, 1990, Billionet & Costa, 1994].
A more complicated problem is the Capacitated Facility Location Problem (CFLP) with restrictions on the facility capacities. More formally, in the CFLP each facility i has a capacity ai specifying the maximum amount of goods it can produce. There are two variants of this problem: CFLP with unsplittable demands (the demand of a client must be served by only one facility) or the single allocation CFLP [Laporte et al., 2015] and CFLP with splittable demands (the demand of a client can be split and assigned to multiple open facilities) or the multiple allocation CFLP[Laporte et al., 2015] .
When the capacities of all the facilities are identical, the problem is known as the Uniform Capacitated Facility Location Problem (UCFLP). When the facility capacities are different, the problem is called the Non-Uniform Capacitated Facility Location problem or just the Capacitated Facility Location Problem.
Let’s consider an even more hard case of the facility location problem the Restricted Capacitated Facility Location Problem (RCFLP) which has restrictions on the capacities of facilities and on the capacities of edges. Let G = (V, E) be a given graph, and let n = jV j. At each node of the graph there are consumers, and there is a set of nodes M V where a facility might be placed. For each edge e 2 E, the cost ce for the transportation of a unit of product along the edge is specified. The restrictions on the edge capacities mean that for each edge e 2 E there is a maximum quantity qe of a product which can be transported along this edge. The problem is to minimize the sum of facility opening costs, plus the consumer allocation costs, having restrictions on the consumer’s demand, capacities of the facilities, and edge transportation capacities: ∑ ∑ xipj = bj, j 2 V, jV j = n, i∈M p∈Pij i∈M,j∈V, p∈Pij: e∈p 0 ∑ p xij
p xij
p xij
qe, e 2 E, bjyi, i 2 M , j 2 V, where bj is a size of demand at site j 2 V ; ai is a capacity of the facility at site i 2 M ; fi is a fixed cost of opening a facility at site i 2 M ; Pij is a set of all paths from the facility at site i to customer at site j; ce is a transportation cost of a unit of product along the edge e; cipj = ∑ce is a transportation cost of a unit of product along the path p from site i to site j; e∈p qe is capacity of the edge e 2 E; yi are the variables of choosing whether to open a facility at site i or not, i 2 V ; xipj is the quantity of the product transported from the facility at site i to the customer at site j along the path p 2 Pij.
Constrains (3) stand for each consumer’s demand is satisfied, capacity constrains (2) make sure that the capacity of the open facility cannot be exceeded, and transportation capacity constrains (4) guarantee that the capacity of each edge e is not exceeded. Constrains (5) state that the allocation to the facility i is possible only if it is open.
The problem (1), (3), (5) – (6) (that is, without taking into account the restrictions on the facility and edge capacities) is called the Unbounded Facility Location Problem (UFLP or simply FLP) [Mirchandani & Francis, 1990].
The problem (1) – (3), (6) (that is, without taking into account the restictions on the edge capacities) is called the Capacitated Facility Location Problem (CFLP) [Mirchandani & Francis, 1990].
The problem (1), (3) – (6) (that is, without taking into account the restrictions on the facility capacities) is called the Restricted Facility Location Problem (RFLP) [Voznuk, 1999].
The RCFLP is known to be NP-hard on a graph of a general type. In [Ageev et al., 2009] the CFLP with uniform facility capacities on a line-graph is solved in time O(m4n2). In [Voznuk, 1999] the RFLP on a tree graph (1), (3)–(6) was solved in O(n3b2), where b = max bj . In this paper we consider a metric version of the j∈V RCFLP problem and show that it has a pseudo-polynomial algorithm if the input graph G is a tree. We also propose a polynomial dynamic programming algorithm for two statements of the RFLP on a line. 2
Assume that the graph G in the considered problem is a tree. Given that between any pair (i, j) of vertices of the tree there is a unique path Pij , the problem (1), (3)–(6) on an arbitrary tree graph can be stated as follows. ∑ xij = bj , j 2 V, i∈V ∑ ∑ i∈V j|e∈Pij xij
qe, e 2 E, xij where cij = ∑ ce for any i 2 V , and j 2 V . Here we consider a situation where a facility can be placed in e∈Pij any node of the graph G. If at site i 2 V a facility cannot be placed, we set the cost fi of opening a facility to be equal to infinity.
Statement 1 The RCFLP on a tree can be solved in O(nB2)-running time, where B = demand.
Let us describe the algorithm which consists of two preliminary stages and the dynamic programming.
Preliminary Stage 1. First, we are going to reduce the problem with facility capacity (8) and edge capacity (10) constrains to a problem with only edge capacity constrains (10) by transferring the possible places for facilities to the new dummy vertices and transforming the facility’s productive capacity into the transportation capacity of the edge that connects the dummy and the initial vertices.
For each vertex i 2 G such that the cost of opening a facility at i is fi < 1 we will add a dummy vertex i′ and an edge (i′, i). We are going to move the places where a facility might be opened from all such vertices i to the corresponding i′. Set the cost of opening a facility at i′ equal to fi′ = fi and then set fi = 1. The demand at i′ is bi′ = 0, the cost of transportation of a unit of product along the edge (i′, i) is c(i′,i) = 0. Finally, the transportation capacity of the edge (i′, i) is equal to the facility capacity at i in the graph G : q(i′,i) = ai. Denote this new graph by G′. The problem (7) on the graph G′ with constrains (9), (10), and (11) is equivalent to the problem on the graph G with constrains (8)–(11). While in the graph G a facility at site i cannot produce more ∑bj is the total j∈V then ai units of product, in the graph G′ a facility at site i′ produces any number of product, but the edge (i′, i) that connects the facility with the rest of the graph can transfer at most ai units. Note that G′ has at most 2n vertices.
Preliminary Stage 2. Next we are going to reduce a problem on an arbitrary tree to a problem on a binary tree, which is an oriented rooted tree and each node has at most two children. Choose a vertex r that will be a root of the tree graph. Starting from the root for each vertex v that has more than 2 sons do the following. Let u1, . . . , uk be the sons of v. Replace v by a path of k 1 vertices v1, . . . , vk−1, and add edges (v1, u1), (v2, u2) . . . , (vk−1, uk−1) and (vk−1, uk). Set the values of the demand bv1 = bv, bv2 = . . . = bvk−1 = 0, the costs of the facility opening fv1 = fv2 = . . . = fvk−1 = 1, since at Stage 1 we made the vertices with finite cost of the facility opening to have only one neighbor. Set the cost of transportation for each edge in the path (v1, . . . , vk−1) to be zero, and the edge capacities to be the highest possible, i.e. to be equal to ∑v∈V bv. For each edge (vi, ui), 1 i k 1, set c(vi,ui) = c(v,ui) and q(vi,ui) = q(v,ui).
Lemma 1 [Voznuk, 1999]. The problem (7), (9)–(11) on an arbitrary tree graph reduces to a problem on a binary tree graph with at most twice the number of vertices.
Stage 3. The dynamic programming. As a result of two previous stages we have a problem with no facility capacity constrains on a rooted binary tree graph G0 = (V0, E0) with a root r = 0 and the number of vertices V0 4n, where n is the number of vertices in the initial tree graph G.
Consider a subtree Gi rooted at i. Let j be the parent of i and let z be the total amount of product transported along the edge e = (j, i). Denote by Fi(z) the optimum of the subproblem on a subtree Gi, assuming z units of product are transported along the edge e.
Recall that in (6) yi 2 f0, 1g are the variables of choosing whether or not to open a facility at site i. So each time in the Bellman equations we decide whether to open a facility at site i and satisfy the consumer’s demand in a subtree using it’s productivity, or not to open a facility and thus use the flow z to satisfy the demand at i and to pass the rest of the flow to the subtree. Note that we can assume qe B for all e 2 E0, where B = ∑ bi i∈V0 is the total demand, since B is the largest possible amount of product we would ever need to transfer along an edge in solving this problem. Set qe = minfqe, Bg. For each z 2 [ qee, qee] and i 2 V0:
e 1. If the vertex i is a leaf of the tree:
Fi(z) = fi cez, cez, 1, if bi z if qee otherwise z qe, e
0, {
(1 { (1 bi ( Fi(z) = cejzj +
min yi∈{0,1} yi) z′∈[−qe(i,k),qe(i,k)] min fFk(z′) + Fk(z bi
z′)g + ( + yi fi +
min z′∈[0,qe(i,k)]
Fk(z′) + z′∈m[0,iqen(i,ℓ)] Fℓ(z′))} = cejzj + min {
min |z′|≤q(i,k) fFk(z′) + Fk(z z′)g; fi +
min z′∈[0,q(i,k)]
Fk(z′) + z′∈m[0,iqn(i,ℓ)] Fℓ(z′)}.
Calculating Fi(z), z 2 [ qee, qee], i 2 V0, takes O n(em∈aEx0 qee)2 and recovering of the solution (yi, xij ) takes O(n) time.
Corollary 1. In the case of unit demands, the proposed algorithm runs in O(n3) time. ) or O(n minfB2, qm2axg time, where qmax = max, e∈E0 2. If the vertex i has one son k:
Fi(z) = cejzj +
min yi∈{0,1} 3. If the vertex i has two sons k and ℓ:
{ = cejzj + min Fk(z bi); fi +
min z′∈[0,qi,k] yi)Fk(z
( bi) + yi fi +
Fk(z′))} = min z′∈[0,qe(i,k)] Fk(z′)}.
(12) (13) (14)
Corollary 2. In the case of line graph and a common statement of the problem with at most m possible sites for the facilities, the running-time of our algorithm is O(m minfB2, qm2axg). For vertices i 2/ M , in which facility cannot be placed, in the dynamic programming procedure for the line graph there are no recurrence relations of the third type (14) and the relations (13) turn into Fi(z) = cejzj + Fk(z bi).
Note, that for the CFLP (with no edge capacity restrictions) on a line graph there is an algorithm from [Mirchandani et al., 1996] that runs in O(mB minfamax, Bg), where m is the number of facilities that can be opened. In this case our algorithm will give almost the same time complexity O(m minfamax, B2g), since amax 2 transforms to qmax at the Preliminary Stage 1. 3
In this section we are going to discuss the metric RFLP (7), (9)–(11) on a line graph. Let the vertices of the line graph be numbered by 1, . . . , n in the order of its bypass. The cost cij of transportation of the unit of product from i to j is naturally defined as cij = ∑e∈Pij ce. These transportation costs satisfy the conditions of central-connectivity: for each i1, i2, v 2 V if ci1v < ci2v then ci1j < ci2j for all nodes j in the shortest path from i1 to v.
Statement 2. [Gimadi, 1984] For the unbounded FLP on a graph with centrally-connected transportation costs, there exists an optimal solution such that for each opened facility the service area is a connected subgraph. Solutions of this type will be referred to as centrally-connected.
Thus, for the RFLP on a line graph there exists an optimal solution, where the given line is broken into continuous segments and in each segment there is one open facility that fully serves the customers of this segment. For the RFLP we can also consider statements with single and multiple allocation conditions. In the case of single allocation each customer must be served by only one facility. Thus in the optimal centrallyconnected solution the neighbor segments do not intersect. In the multiple allocation statement of the RFLP each consumer demand can be satisfied by several facilities. This implies that the neighbor segments in the optimal centrally-connected solution may have one common vertex, if the edge capacity restrictions do not allow to cover full demand of this vertex by the corresponding facility with the cheapest transportation cost.
Both problems on a line can be solved in polynomial time by the dynamic programming in a similar way. 3.1
Add the dummy vertices 0, n + 1 and the edges e′ = (0, 1), e” = (n, n + 1) to the line. Set the following numerical characteristics for the new elements of the line: qe′ = qe" = 0, ce′ = ce" = 1, f0 = fn+1 = 0, b0 = bn+1 = 0.
Single allocation case. Consider the single allocation RFLP on a line. Denote by g(i, j) the minimum cost of serving the segment [i, j], assuming that there is one open facility k in the segment that satisfies full demand of [i, j].
Consider a matrix (bcxy), where bcxy is the total transportation cost necessary to satisfy the demand in all points of the path from x to y, if the product is supplied from the facility at site x.
bcxy = ∑ty=x+1 c(t,t+1)(bt+1 + bt+2 + . . . + by), if x y, and (15), ∑tx=y c(t,t+1)(bt + bt+1 + + bx−1), if y x, and (16), 1, otherwise, where we have the following system of restrictions due to the constraints on the capacity of edges. For x < y: (15) And for y < x:
Now, according to the Statement 2 and the reasoning above, our problem reduces to the problem of finding an optimal segment decomposition of the line graph: (20) (21) s.t.
The problem (17) – (18) can be solved by the following dynamic programming scheme
Multiple allocation case. Consider the multiple allocation RFLP on a line. The idea of the dynamic programming scheme for this case of the problem first appeared in [Voznuk, 1999] with no proof for the time complexity.
Denote by h(i, j) the minimum of the transportation costs necessary to satisfy the demand in points i, i + 1, . . . , j provided that the product is supplied from the facilities at sites i and j. In calculating values h(i, j) we are searching for the best point k between i and j which may be served by both i and j facilities and divides the rest of customers into continuous serving segments [i, k 1] and [k + 1, j].
Let Bt = ∑tℓ=1 bℓ, Ct = ∑tℓ=1 cℓ, 1 t n , Cbx,y = ∑ty=−x1 c(t,t+1)Bt, 1 x y n. Denote by hk(i, j) the optimal transportation costs for serving the [i, j], if k is the point served by both facilities at i and j. hk(i, j) = { Ck−1Bk−1
Cbi,k−1 + Cbk+1,j
CkBk + α(Ck
Ci)bk + (1 α)(Cj
Ck)bk, if (21), 1, otherwise, where we have the following system of restrictions due to the constraints on the capacity of edges: Bj−t
Bk−1
Bi + αbk Bk−1+t
Bi + αbk Bj
Bk + (1 Bk + (1
αbk α)bk q(i,i+1),
. . . q(i+t,i+t+1),
. . . q(k−1,k); q(j−1,j),
. . . α)bk (1 q(j−t−1,j−t),
. . . α)bk q(k,k+1).
Denote by Di = mini≤t≤k−1fq(i+t,i+t+1) (Bk−1+t Bi)g, which is the maximum additional amount of product we can pass from i to k after serving the segment [i, k 1]. Denote by Dj = maxk+1≤t≤jf(Bj−t) Bk) + bk q(j−t−1,j−t)g. For the system (21) to have a solution, it is necessary that Dj bkα Di. Finally, we set the value α in a way that the facility (at i or j), for which the total transportation cost to site k is cheaper, supplies the maximum possible amount of product to k: if Dj < Di and Cj < 2Ck if Dj < Di and Cj > 2Ck if Dj > Di.
Ci, Ci,
Calculating all Bt and Ct, 1 t n, takes O(n2) time, and calculating all Cbxy, 1 x y n, takes O(n3). Note that first k i inequalities in (21) do not depend on j, and the last j k inequalities do not depend on i. So for fixed i and k verifying the first part of the system (21) takes O(k i) time, similarly for fixed j and k verifying the second part of the system takes O(j k) time. So it takes O(n3) time to verify all such systems. Finally, we can calculate hk(i, j) in O(1), and find h(i, j) in O(j) time:
We introduce the notation g(i, j) = 12 (fi + fj ) + h(i, j). The problem the RFLP reduces to minimizing: h(i, j) = i<mki<nj hk(i, j).
0 = i0 < i1 < . . . < is < is+1 = n + 1, s = 1, . . . , n.
It can be solved by the same dynamic programming scheme (19). The total time complexity is O(n3).
Corollary 3. For the statement of the RFLP where the set of possible facility locations M the time complexity of the given algorithm is O(mn2).
V , jM j = m, 4
In this paper we have proposed a pseudo-polynomial time algorithm solving the FLP with restrictions on productive capacities of facilities and capacities of edges on a tree graph, and have discussed a polynomial time algorithm solving the single and multiple allocation FLPs with restrictions on edge capacities on a line graph.
The differentiation of the statements with single and multiple allocation requirements is well justified in practice. From the perspective of studying these two FLP statements there are the following results in this area for the line graphs. For the FLP on a line with no additional constraints there is an O(mn) algorithm [Gimadi, 1983] for the both cases of single and multiple allocation. For the RFLP on a line O(mn2) algorithms for both statements have been discussed in this paper. For the multiple allocation CFLP the best known is O(m4n2) algorithm [Ageev et al., 2009], and it is an open question in the case of single allocation. This paper provides a pseudo-polynomial algorithm for the multiple allocation RCFLP on a line graph, and the case of single allocation RCFLP on a line has not been considered yet.
So, for further research it would be interesting to study the single allocation RCFLP and CFLP on a line, and construct faster algorithms for the multiple allocation RCFLP and CFLP.
Authors are supported by the Russian Foundation for Basic Research grants 16-31-00389, 16-07-00168, and 15-0100976, Russian Ministry of Science and Education under 5-100 Excellence Program, and the grant of Presidium of RAS (program 8, project 227).