 Intelligent Information Ma nagement, 2011, 3, 71-74 doi:10.4236/iim.2011.33009 Published Online May 2011 (http://www.SciRP.org/journal/iim) Copyright © 2011 SciRes. IIM Facility Location Problem with Different Type of Clients Lisheng Wang1, Rongheng Li1*, Jingui Huang2 1Department of Mat hem at i cs, Hunan Normal University , Changsha, China 2Department of Computer Education, Hunan Normal University, Changsh a, China E-mail: ldwls@126.com, {lirongheng, hjg}@hunnu.edu.cn Received December 25, 2010; revised January 5, 2011; accepted March 28, 2011 Abstract This paper proposes a new model of facility location problem referred to as k-product uncapacitated facility location problem with multi-type clients. The k-product uncapacitated facility location problem with multi- type clients consists of two set of sites, one is the set of demand points where clients are located and the other is the set of sites where facilities of unlimited capacities can be set up to serve the clients. Each facility can provide only one kind of products. Each client needs to be served by a set of facilities depending on which products it needs. Each facility can be set up only for one of the k products with a non-negative fixed cost determined by the product it is designated to provide. There is also a nonnegative cost of shipping goods between each pair of locations. The problem is to determine the set of facilities to be set up and to find an assignment of each client to a set of facilities so that the sum of the setup costs and the shipping costs is minimized. Under the assumption that the setting costs is zero and the shipping costs are in facilities centered metric space, it is shown that the problem with two kinds of clients is NP-complete. Furthermore a heuristic algorithm with worst case performance ratio not more than 2-1/k is presented for any integer k. Keywords: Heuristic Algorithm, Complexity, Facility Location 1. Introduction In the last few years, a number of constant factor ap- proximation algorithms have been proposed for facility location problem when the service cost is assumed to be in the metric space by Ageev [1], Chudak and Shmoys [2], Guha & Khuller [3], Mahdian et al. [4], Shmoys et al. [5] and Zhang [6]. That is, the service cost is assumed to be symmetric and satisfy the triangle inequality. The first heuristic algorithm with a performance guarantee of 3.157 was given by Shmoys et al. [5], which is based on a linear program rounding algorithm extended from the filter technique of Lin & Vitter [7]. In the classical simple uncapacitated facility location problem, each client only needs one kind of product. Recently k-product uncapacitated facility location prob- lem which is proposed by Huang and Li [8] can be de- scribed as follow: there is a set of demand points where clients are located and a set of potential sites where fa- cilities of unlimited capacities can be set up. There are k different kinds of products. Each client needs to be sup- plied with k kinds of products by a set of k different fa- cilities and each facility can be set up to supply only a distinct product with a non-negative fixed cost deter- mined by the product it intends to supply. But in practice, it is not the case th at all of the clients’ demands are the same. For example, let k = 2, some cli- ents may only need product p1, some clients may only need product p2 and some other clients need both product p1 and p2. More concisely, let D be the set of clients and F be the set of potential facilities. There are k kinds of products, 12 ,,, k Ppp p. For each , there is a set jD P of products demanded by client j. Certainly P is a subset of P which contains k products. Each fa- cility iF may be set up to provide at most one of th e products. The cost of setting up a facility i to supply product pl is l i , iF , . The cost of shipping between any two points is equal to ij c. Each client 1,ij jD lk FD must be supplied with all of the products in P by a set of facilities. In other words, split source is not allowed for a given product. 2. The Formulation of the Problem Let l ij be equal to 1 if facility i supplies client j with product , and 0 otherwise for any , l piFjD  72 L. S. WANG ET AL. and lP. Let l i be 1 if facility i is set up to supply product pl, and 0 otherwise. Then the problem described above can be formulated as the following integer pro- gram: 1 1m j kll l ii ijij liF jDiFlP Pfy in l ij iF cx (1) ..1, j tx ll i jDl P , (2) ,, ij j yiFjDlP F (3) 1 kl ii 1,y ,0 l (4) ,1, ,, ll ij ij yiFjDlP (5) In the above formulation, constraints (2) ensure that each client is supplied by precisely one facility for a product it demands. Constraints (3) ensure that facility i is set up to supply product l if client j receives product l from this facility. Constraints (4) ensure that each facility is set up to supply at most one kind of the k products. Now we consider a special case of integer program (P1) in which 1 k ; . j P for any , i.e., each client need only one products. But different clients may need different products. Under such an assumption, we can get a partition of client set 12 such that all of the clients in Dl only need produ ct pl, . This special case can be formulated as the following in- teger program: jD Dk DD D 1,2,,l 2m .. k l ij st 1 1 in 1,,1,2, ,; ,,,1,2,, 1, ; ,0,1,, ,1,2,, j kll l iiijij liF jDiFlP l ij l iF ll ij il l i ll i l Pfycx xjD lk yiFjDl k yiF yiFjDl k Theorem 1. To solve any instance of (P1) is equiva- lent to solve an in stance of (P2). Proof. For any ins tance of (P1), let . If jDj P1 , then we use P copies of client j to replace client j such that each copy need only one different product of Pj, respectively. Then the instance of (P1) is equivalently transformed into an instance of (P2). Because of Theorem 1, we only consider (P2) in the following of this paper and refer to (P2) as k-product uncapacitated facility location problem with multi-type clients. When all of the setting up costs are zero, then all facilities can be set up. We use P-k-N to denot e k-product uncapacitated facility location problem with multi-type clients when the setting up costs are zero: 1 1 min ..1,,1,2, ,; ,,,1,2, 1, ; ,0,1,, ,1,2,, l kl ij ij liFjD l ij l iF ll ij il kl i l ll ij il PkN cx stxjD lk ,; . yiFjDl yiF k yiFjDl k D Throughout this paper, we make the following as- sumptions on cost s unl ess speciall y me nt i oned: (1)0,,1, 2,,; (2)0, ,; (3), ,, (4),,,, (5)min,, ,, l i ij ij ji ijih hj ijih hj fiFlk cijFD ccijFD ccc ijhFD cccijFh Conditions (2)- (4) mean that the ship costs are in met- ric space and condition (5) means that we only consider the problem with centered facilities. In the following of this paper we say the ship costs are in facilities centered metric space if they satisfy conditions (2)-(5) mentioned above. 3. The Complexity of the P-2-N Theorem 2. The P-2-N is NP-complete even under the assumption that the ship costs are in facilities centered metric space. Proof. We will establish the proof by reducing the max-cut problem, which is an NP-complete problem in Garey and Johnson [9], to the P-2-N. Consider the max-cut problem defined on an undirected graph G = (V, E) with node set V and arc set E. Suppose 12 ,,, . n vv vV and 12 ,, . m ee eE Let 12 SS V be a partition of V. The set of the total edges be tween S1 and S2 is defined as a cut of graph G. Let CUT (S1,S2) denote the set of such edges. The max-cut problem is to find a partition of V, 12 , such that SVS 12 CUT ,SS is maximal. By graph G, we construct an instance of the P-2-N with the set of facilities F = V and the set of clients D = EE, where 12 E,,, m ee e is a copy of the edge set E. We define the serving costs as follows: 1 is incident to , :, 2otherwise. :, ; i iji j iji jij ev ccve ccvec Copyright © 2011 SciRes. IIM  L. S. WANG ET AL. 73 12 12 1212 12121 212 ,,,, ,, ,,,. ii jj jj jj iiiijjjj cvvcee cee cee vv Vvveeee E 1, It is easy to show that the ship costs are in facilities centered metric space. Let F = V = 12 be a parti- tion of V. S1 and S2 are set up to supply products p1 and p2, respectively. Let C (S1,S2) denote the cost of the P-k-N under the ordered partition F = V = . Now we consider the servicing cost of each SS e 1 SS E j 2 and E j e under this partition of F and let Cj (S1,S2) denote the total servicing cost of ej and e. Let and be the two end points of ej, i.e. ej = (,). 1 i v 2 i v2 i v 1 i v Case 1. ej CUT (S1,S2). In this case, the two end points of ej fall into S1 and S2, respectively. Without loss of generality, suppose 1 i is in S1 and 2 i is in S2. We assign 1 i to supply ej with product p1 and 2 i to supply v v v v e with product p2, re- spectively. It is easy to see that Cj (S1,S2) = 2. Case 2. ej CUT (S1,S2). In this case, both 1 iand 2 i belong to either S 1 or S2. Without loss of generality, suppose both 1 i and 2 ibelong to S1. We set 1 i to supply ej with products p1. Because 1 by our definition, the servicing cost of ej for p1 is 1. Furthermore we must select a i v vv v v 1 ij cv S2 to supply e with p2. For any vi S2, 2 ij c because ej is not incident to vi. Thus we have Cj (S1, S2) = 3. Because there are exactly 12 CUTS ,Sm edges which are not in CUT (S1,S2), from Case 1 and Case 2 discussed above, we can conclude that 12 12 12 12 12 12 CUT,CUT, 12 S,S S,S S,S S,S 3CUTS,S. j jj j eD jj eSS eSS CC C m C Because m, the number of edges in E, is fixed, C (S1,S2) gets its minimal value when 12 CUTS,S reaches its maximal value, and vice versa. This means an optimal solution of the P-2-N provides an answer to the max-cut problem. Thus we have proved that the P-2-N is NP-complete. 4. Heuristic algorithm for P-k-N If we remove the conditions that each facility can only supply one product, then (P-k-N) becomes the following problem (P-k-N)': 1 PN min ..1,,1,2, ,; 0,1 ,,,1,2,,. l kl ij ij liFjD l ij l iF l ij l kcx stxjD lk iFjDl k In the following we refer to the optimal solution of (P-k-N)' as the overlap optimal solution of (P-k-N). It is obvious that the value of overlap optimal solution is a lower bound of the value of the optimal solution for (P-k-N). It is easy to get an overlap optimal solution by letting each client be supplied by its closest facility. Now we give an approximation algorithm for (P-k-N): Algorithm A. Step 1. Find an overlap optimal solution by letting each client be supplied by its closest facility. Set Si: = , =1, 2,···, k and F: = F. Step 2. Fi , let is supplied byinthe overlap optimalsolution; ,1,2,,; max1,2, , . Let0if.Set S:S,S:S,,F:F l i l il l iij jB sl ii ll ii ss ll BjDj i aclk aa k aB ilsi We iterate this process until F. Step 3. We use the facilities in Sl to supply products pl and for each client 1 jD , we select its closest facility in Sl as its supplier, l = 1,2, ···, k. Theorem 3. For the P-k-N with the assumption that the ship costs are in facilities centered metric space, the algorithm A has worst case performance ratio not more than 1 2 k . Proof. ,1,2, 1 jDl k, let il(j) is the closest facility of j in Sl. For each facility Fi , let 1 ii l be the set of the clients which use facility i as its supplier in overlap optimal solution. Now we con- sider the total costs Ai produced by the clients of Bi in the algorithm A. Suppose . The n we have k Bl B 0 Sl i 0max1,2,,. ll ii aalk Therefore we get 0 0 0 0 0 0 0 0 11, 1, 1, 1, 1 2 2 1 2, ll ll ii l l i l i kk l ii ijj ijj llll jB jB k l ii iji lll jB k l iij lll jB k ll ii lll kl i l Aca c acc ac aa a k j Copyright © 2011 SciRes. IIM  L. S. WANG ET AL. Copyright © 2011 SciRes. IIM 74 where the first inequality follows from the triangle ine- quality, the second follows from (5) of the assumption on ship costs and the last follows from 0max1,2,,. ll ii aalk 5. Discussion In this paper we consider the k-product uncapacitated facility location problem with multi-type clients and suggest an approximation algorithm for P-k-N under the assumption that the ship costs are in facilities centered metric space. One interesting question that remains open is whether there exist approximation algorithms with constant worst case performance ratio for the P-k-N when we only suppose that the ship costs are in metric space. 6. Acknowledgements The authors would like to express their thanks to the Na- tional Natural Science Foundation of China for finan- cially supporting under Grant No. 10771060 and No. 60872039. 7. References [1] A. A. Ageev, “Improved Approximation Algorithms for Multilevel Facility Location Problems,” Operations Re- search Letters, Vol. 30, No. 5, 2002, pp. 327-332. doi:10.1016/S0167-6377(02)00162-1 [2] F. A. Chudak and D. B. Shmoys, “Improved Approxima- tion Algorithms for the Uncapacitated Facility Location Problem,” SIAM Journal on Computing, Vol. 33, No. 1, 2003, pp. 1-25. doi:10.1137/S0097539703405754 [3] S. Guha and S. Khuller, “Greedy Strikes Back: Improved Facility Location Algorithms,” Journal of algorithm, Vol. 31, 1999, pp. 228-248. [4] M. Mahdian, Y. Y. Ye and J. W. Zhang, “Approximation Algorithms for Metric Facility Location Problems,” SIAM Journal on Computing, Vol. 36, No. 2, 2006, pp. 411- 432. doi:10.1137/S0097539703435716 [5] D. B. Shmoys, E. Tardos and K. I. Aardal, “Approxima- tion Algorithms for Facility Location Problems,” In the Proceedings of the 29th Annual ACM Symposium on The- ory of Computing, 1997, pp. 265-274. [6] J. W. Zhang, “Approximating the Two-Level Facility Location Problem via a Quasi-Greedy Approach,” The 15th ACM-SIAM Symposium on Discrete Algorithms SODA, 2004, pp. 808-817. [7] J. H. Lin and J. S. Vitter, “Approximation Algorithms for Geometric Median Problems,” Information Processing Letters, Vol. 44, No. 5, 1992, pp. 643-666. [8] H. C. Huang and R. H. Li, “A $k$-Product Uncapacitated Facility Location Problem,” European Journal of Opera- tions Research, Vol. 185, No. 2, 2008, pp. 552-562. doi:10.1016/j.ejor.2007.01.010 [9] M. R. Garey and D. S. Johnson (eds.), “Computers and Intractability - a Guide to the Theory of NP-Complete- ness,” W. H. Freeman and Company, San Francisco, 1979.
|
