Facility Location Problem with Different Type of Clients

Lisheng Wang, Rongheng Li, Jingui Huang

.

DOI: 10.4236/iim.2011.33009                

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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. A. Ageev, “Improved Approximation Algorithms for Multi-level Facility Location Problems,” Operations Research 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 Approximation Algorithms for the Un-capacitated 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 Algo-rithms,” Journal of algorithm, Vol. 31, 1999, pp. 228-248.
[4]	M. Mahdian, Y. Y. Ye and J. W. Zhang, “Ap-proximation Algorithms for Metric Facility Location Prob-lems,” 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, “Approximation Algo-rithms for Facility Location Problems,” In the Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 265-274.
[6]	J. W. Zhang, “Approximating the Two-Level Facility Location Problem via a Quasi-Greedy Ap-proach,” The 15th ACM-SIAM Symposium on Discrete Algo-rithms SODA, 2004, pp. 808-817.
[7]	J. H. Lin and J. S. Vit-ter, “Approximation Algorithms for Geometric Median Prob-lems,” Information Processing Letters, Vol. 44, No. 5, 1992, pp. 643-666.
[8]	H. C. Huang and R. H. Li, “A $k$-Product Un-capacitated Facility Location Problem,” European Journal of Operations 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-Completeness,” W. H. Freeman and Company, San Francisco, 1979.