The Capacitated Location-Allocation Problem in the Presence of k Connections

Saber Shiripour, Mehdi Amiri-Aref, Iraj Mahdavi

.

DOI: 10.4236/am.2011.28130                

Abstract

We consider a capacitated location-allocation problem in the presence of k connections on the horizontal line barrier. The objective is to locate a set of new facilities among a set of existing facilities and to allocate an optimal number of existing facilities to each new facility in order to satisfy their demands such that the summation of the weighted rectilinear barrier distances from new facilities to existing facilities is minimized. The proposed problem is designed as a mixed-integer nonlinear programming model. To show the efficiency of the model, a numerical example is provided. It is worth noting that the global optimal solution is obtained.

Keywords

Capacitated Location-Allocation Problem, Line Barrier, Mixed Integer Nonlinear Programming

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	G. Cornuejols, G. L. Nemhauser and L. A. Wolsey, “The uncapacitated Facility Location Problem,” In: P. Mirchandani and R. Francis, Eds., Discrete Location Theory, John Wiley and Sons, New York, 1990, pp. 119-171.
[2]	D. Shmoys, “Approximation Algorithms for Facility Location Problems,” Proceedings of 3rd International Workshop of Approximation Algorithms for Combinatorial Optimization, Vol. 1913, No. 1, 2000, pp. 27-33.
[3]	A. Weber, “über den Standort der Industrien,” Tübingen Theory of the Location of Industries, University of Chicago Press, 1909.
[4]	L. Cooper, “Location-Allocation Problems,” Operations Research, Vol. 11, No. 3, 1963, pp. 331-343. doi:10.1287/opre.11.3.331
[5]	J. Zhou and B. Liu, “New Stochastic Models for Capacitated Location-Allocation Problem,” Computers & Industrial Engineering, Vol. 45, No. 1, 2003, pp. 111-125. doi:10.1016/S0360-8352(03)00021-4
[6]	H. W. Hamacher and S. Nickel, “Restricted Planar Location-Problems and Applications,” Naval Research Logistics, Vol. 42, No. 6, 1995, pp. 967-992. doi:10.1002/1520-6750(199509)42:6<967::AID-NAV3220420608>3.0.CO;2-X
[7]	I. N. Katz and L. Cooper, “Formulation and the Case of Euclidean Distance with One Forbidden Circle,” European Journal of Operational Research, Vol. 6, No. 1, 1981, pp. 166-173. doi:10.1016/0377-2217(81)90203-4
[8]	K. Klamroth, “Algebraic Properties of Location Problems with One Circular Barrier,” European Journal of Operational Research,” Vol. 154, No. 1, 2004, pp. 20-35. doi:10.1016/S0377-2217(02)00800-7
[9]	M. Bischoff and K. Klamroth, “An Efficient Solution Method for Weber Problems with Barriers Based on Genetic Algorithms,” European Journal of Operational Research, Vol. 177, No. 1, 2007, pp. 22-41. doi:10.1016/j.ejor.2005.10.061
[10]	K. Klamroth, “Planar Weber Location Problems with Line Barriers,” Optimization, Vol. 49, No. 5-6, 2001, pp. 517-527. doi:10.1080/02331930108844547
[11]	K. Klamroth and M. M. Wiecek, “A Bi-Objective Median Location Problem with a Line Barrier,” Operations Research, Vol. 50, No. 4, 2002, pp. 670-679. doi:10.1287/opre.50.4.670.2857
[12]	S. Huang, R. Batta, K. Klamroth and R. Nagi, “The K-Connection Location Problem in a Plane,” Annals of Operations Research, Vol. 136, No. 1, 2005, pp. 193-209. doi:10.1007/s10479-005-2045-1
[13]	S. Huang, R. Batta and R. Nagi, “Variable Capacity Sizing and Selection of Connections in a Facility Layout,” IIE Transactions, Vol. 35, No. 1, 2003, pp. 49-59. doi:10.1080/07408170304434
[14]	S. Huang, R. Batta and R. Nagi, “Distribution Network Design: Selection and Sizing of Congested Connections,” Naval Research Logistics, Vol. 52, No. 8, 2005, pp. 701-712. doi:10.1002/nav.20106
[15]	M. S. Canbolat and G. O. Wesolowsky, “The Rectilinear Distance Weber Problem in the Presence of a Probabilistic Line Barrier,” European Journal of Operational Research, Vol. 202, No. 1, 2010, pp. 114-121. doi:10.1016/j.ejor.2009.04.023
[16]	M. A. Badri, “Combining the Analytic Hierarchy Process and Goal Programming for Global Facility Location-Allocation Problem,” International Journal of Production Economic, Vol. 62, No. 1, 1999, pp. 237-248. doi:10.1016/S0925-5273(98)00249-7
[17]	S. D. Brady and R. E. Rosenthal, “Interactive Graphical Solutions of Constrained Minimax Location Problems,” IIE Transactions, Vol. 12, No, 1, 1980, pp. 241-248. doi:10.1080/05695558008974512
[18]	R. Batta and L. A. Leifer, “On the Accuracy of Demand Point Solutions to the Planar, Manhattan Metric, p-Median Problem, with and without Barrier to Travel,” Computers and Operations Research, Vol. 15, No. 1, 1988, pp. 253-262. doi:10.1016/0305-0548(88)90038-X
[19]	O. Berman and Z. Drezner, “Location of Congested Capacitated Facilities with Distance-Sensitive Demand,” IIE Transactions, Vol. 38, No. 3, 2006, pp. 213-221. doi:10.1080/07408170500288190
[20]	O. Berman, D. Krass and J. Wang, “Locating Service Facilities to Reduce Lost Demand,” IIE Transactions, Vol. 38, No. 11, 2006, pp. 933-946. doi:10.1080/07408170600856722
[21]	O. Berman, R. Huang, S. Kim and B. C. Menezes, “Locating Capacitated Facilities to Maximize Captured Demand,” IIE Transactions, Vol. 39, No. 11, 2007, pp. 1015-1029. doi:10.1080/07408170601142650
[22]	J. Zhou and B. Liu, “Modeling Capacitated Location-Allocation Problem with Fuzzy Demands,” Computers & Industrial Engineering, Vol. 53, No. 3, 2007, pp. 454-468. doi:10.1016/j.cie.2006.06.019
[23]	M. Bischoff, T. Fleischmann and K. Klamroth, “The Multi-Facility Location-Allocation Problem with Polyhedral Barriers,” Computers and Operations Research, Vol. 36, No. 5, 2009, pp. 1376-1392. doi:10.1016/j.cor.2008.02.014
[24]	C. Iyigun and A. Ben-Israel, “A Generalized Weiszfeld method for the Multi-Facility Location Problem,” Operations Research Letters, Vol. 38, No. 1, 2010, pp. 207-214. doi:10.1016/j.orl.2009.11.005
[25]	N. Megiddo and K. J. Supowit, “On the Complexity of Some Common Geometric Location Problems,” SIAM Journal on Computing, Vol. 13, No. 1, 1984, pp. 182-196. doi:10.1137/0213014