A Survey of Discrete Facility Location Problems

Authors: Z. Ulukan, E. Demircioğlu

Abstract:

Facility location is a complex real-world problem which needs a strategic management decision. This paper provides a general review on studies, efforts and developments in Facility Location Problems which are classical optimization problems having a wide-spread applications in various areas such as transportation, distribution, production, supply chain decisions and telecommunication. Our goal is not to review all variants of different studies in FLPs or to describe very detailed computational techniques and solution approaches, but rather to provide a broad overview of major location problems that have been studied, indicating how they are formulated and what are proposed by researchers to tackle the problem. A brief, elucidative table based on a grouping according to “General Problem Type” and “Methods Proposed” used in the studies is also presented at the end of the work.

Keywords: Discrete location problems, exact methods, heuristic algorithms, single source capacitated facility location problems.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1108652

References:

[1] A. A. Kuehn, and M. J. Hamburger, “A heuristic program for locating warehouses” Management Science, vol. 9, pp. 643-666, 1963.
[2] M. L. Balinski, “Integer programming: methods, uses, computation.” Management Science, vol. 12, pp. 253-313, 1965.
[3] S. L. Hakimi, “Optimum locations of switching centers and the absolute centers and medians of a graph” Operations Research, vol. 12, pp. 450- 459, 1964.
[4] S. L. Hakimi, “Optimum distribution of switching centers in a communication network and some related graph theoretic problems” Operations Research, vol. 13, pp. 462-475, 1965.
[5] G. Cornuejols, M. L. Fisher, and G. L. Nemhauser, “Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms” Management Science, vol. 23, pp. 789-810, 1977.
[6] R. D. Galvão, and L. A. Raggi, “A method for solving to optimality uncapacitated location problems” Annals of Operations Research, vol. 18, pp. 225-244, 1989.
[7] D. Erlenkotter, “A dual-based procedure for uncapacitated facility location”, Operation Research, vol. 26, no.6, pp. 992–1009, 1978.
[8] M. Guignard, “A Lagrangean dual ascent algorithm for plant location problems”, European Journal of Operational Research, vol. 35, pp. 193–200, 1988.
[9] B. Goldengorin, D. Ghosh, and G. Sierksma, “Branch and peg algorithms for the simple plant location problem”, Computational Operations Research, vol. 31, pp. 241–255, 2004.
[10] M. Sun, “Solving the uncapacitated facility location problem using tabu search”, Computers & Operations Research, vol. 33, pp. 2563–2589, 2006.
[11] P. Hansen, J. Brimberg, D. Uroševic´, and N. Mladenovic´, “Primal-dual variable neighborhood search for the simple plant-location problem”, INFORMS Journal on Computing, vol. 19, no. 4, pp. 552–564, 2007.
[12] A. M. Nezhad, H. Manzour, and S. Salhi, “Lagrangian relaxation heuristics for the uncapacitated single-source multi-product facility location problem”, Int. J. Prod. Economics, vol. 145, pp. 713–723, 2013.
[13] J. Kratica, D. Dugošija, and A. Savic´, “A new mixed integer linear programming model for the multi level uncapacitated facility location problem”, Applied Mathematical Modelling, vol. 38, pp. 2118–2129, 2014.
[14] E. Ardjmand, N. Park, G. Weckman, and M. R. Amin-Naseri, “The discrete unconscious search and its application to uncapacitated facility location problem”, Computers & Industrial Engineering, vol. 73, pp. 32–40, 2014.
[15] A. N. Letchford, and S. J. Miller, “An aggressive reduction scheme for the simple plant location problem”, European Journal of Operational Research, vol. 234, no. 3, pp. 674–682, 2014.
[16] E. Monabbati, and H. T. Kakhki, “On a class of subadditive duals for the uncapacitated facility location problem”, Applied Mathematics and Computation, vol. 251, pp. 118–131, 2015.
[17] B. M. Khumawala, “An efficient heuristic procedure for the capacitated warehouse location problem”, Naval Research Logistics Quarterly, vol. 21, pp. 609–623, 1974.
[18] A. M. Geoffrion, and R. McBride, “Lagrangean relaxation to capacitated facility location problems”, AIIE Transactions, 10, pp. 40–47, 1978.
[19] Nauss, R.M., “An improved algorithm for the capacitated facility location problem”, The Journal of the Operational Research Society, vol. 29, pp. 1195–1201, 1978.
[20] N. Christofides, and J. E. Beasley, “Extensions to a lagrangean relaxation approach for the capacitated warehouse location problem”, European Journal of Operational Research, vol. 12, pp. 19–28, 1983.
[21] H. Pirkul, “Efficient algorithms for the capacitated concentrator location problem”, Computers & Operations Research, vol. 14, pp. 197–208, 1987.
[22] B. Shetty, “Approximate solutions to large scale capacitated facility location problems”, Applied Mathematics and Computation, vol. 39, pp. 159–175, 1990.
[23] T. L. Magnanti, and R. T. Wong, “Accelerating benders decomposition: Algorithmic enhancement and model selection criteria”, Operations Research, vol. 29, pp. 464–484, 1981.
[24] S. K. Jacobsen, “Heuristics for the capacitated plant location model” European Journal of Operational Research, vol. 12, pp. 253–261, 1983.
[25] W. Domschke, and A. Drexl, “ADD-heuristics’ starting procedures for capacitated plant location models”, European Journal of Operational Research, vol. 21, pp. 47–53, 1985.
[26] T. J. Van Roy, “A cross decomposition algorithm for capacitated facility location”, Operations Research, vol. 34, pp. 145–163, 1986.
[27] J. M. Y. Leung, and T. L. Magnanti, “Valid inequalities and facets of the capacitated plant location problem”, Mathematical Programming, vol. 44, pp. 271–291, 1989.
[28] G. R. Mateus, and C. T. Bornstein, “Dominance criteria for the capacitated warehouse location problem”, The Journal of the Operational Research Society, vol. 42, 145–149, 1991.
[29] K. Aardal, Y. Pochet, and L. A. Wolsey, “Capacitated facility location: Valid inequalities and facets”, Mathematics of Operations Research, vol. 20, pp. 552–582, 1995.
[30] E. Rolland, D. A. Schilling, and J. R. Current, “An efficient tabu search procedure for the p-median problem”, European Journal of Operational Research, 96, pp. 329–342, 1996.
[31] C. T. Bornstein, and H. B. Azlan, “The use of reduction tests and simulated annealing for the capacitated location problem”, Location Science, vol. 6, pp. 67–81, 1998.
[32] G. Ghiani, F. Guerriero, and R. Musmanno, “The capacitated plant location problem with multiple facilities in the same time”, Computers and Operations Research, vol. 50, pp. 268–274, 1999.
[33] L. A. N. Lorena, and E. L. F. Senne, “A column generation approach to capacitated p-median”, Computers & Operations Research, vol. 31, pp. 863–876, 2004.
[34] S. H. Doong, C. C. Lai, and C. H. Wu, “Genetic subgradient method for solving location-allocation problems”, Applied Soft Computing, 7 (1), pp. 373-386, 2007.
[35] A. Klose, and S. Görtz, “A branch-and-price algorithm for the capacitated facility location problem”, European Journal of Operational Research, vol. 179, pp. 1109–1125, 2007.
[36] M. A. Sambola, E. Fernandez, and F. S. Gama, "The facility location problem with Bernoulli demands", Omega, vol. 39, pp. 335–345, 2011.
[37] T. Küçükdeniz, A. Baray, K. Ecerkale, and Ş. Esnaf, “Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem”, Expert Systems with Applications, vol. 39, pp. 4306– 4314, 2012.
[38] A. Rahmani, and M. A. MirHassani, “A hybrid firefly-genetic algorithm for the capacitated facility location problem”, Information Sciences, vol. 283, 70–78, 2014.
[39] I. Harris, C. L. Mumford, and M. M. Naim, “A hybrid multi-objective approach to capacitated facility location with flexible store allocation for green logistics modeling”, Transportation Research, E 66, pp. 1–22, 2014.
[40] D. Ozgen, and B. Gulsun, “Combining possibilistic linear programming and fuzzy AHP for solving the multi-objective capacitated multi-facility location problem”, Information Sciences, vol. 268, pp. 185–201 2014.
[41] J. Li, F. Chu, C. Prins, and Z. Zhu, “Lower and upper bounds for a twostage capacitated facility location problem with handling costs”, European Journal of Operational Research, vol. 236, pp. 957–967, 2014.
[42] K. Aardal, P. L. V. D. Berf, D. Gijswijt, and S. Li, “Approximation algorithms for hard capacitated k-facility location problems”, European Journal of Operational Research, vol. 242, pp. 358–368, 2015.
[43] R. V. Nagelhout, and G. L. Thompson, “A single source transportation algorithm”, Computers & Operations Research, vol. 7, no. 3, pp. 185- 198, 1980.
[44] A. W. Neebe, and M. R. Rao, “An algorithm for the fixed-charge assigning users to sources problem”, The Journal of the Operational Research Society, vol. 34, pp. 1107–1113, 1983.
[45] J. G. Klincewicz, and H. Luss, “A lagrangian relaxation heuristic for capacitated facility location with single-source constraints”, Journal of the Operational Research Society, vol. 37, no. 5, pp. 495–500, 1986.
[46] K. Darby-Dowman, and H. S. Lewis, “Lagrangian relaxation and the single source capacitated facility location problem”, Journal of the Operational Research Society, vol. 39, pp. 1035–1040, 1988.
[47] R. Sridharan, “A Lagrangian heuristic for the capacitated plant location problem with single source constraints”, European Journal of Operational Research, vol. 66, pp. 305–312, 1993.
[48] S. Tragantalerngsak, J. Holt, and M. Rönnqvist, “Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem”, European Journal of Operational Research, vol. 102, pp. 611–625, 1997.
[49] M. Rönnqvist, S. Tragantalerngsak, and J. Holt, "A repeated matching heuristic for the single-source capacitated facility location problem", European Journal of Operational Research, vol. 116, pp. 51-68, 1999.
[50] H. Delmaire, J. A. Dı´az, and E. Ferna´ndez, “Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem” INFOR, Canadian Journal of Operational Research and Information Processing, vol. 37, pp. 194–225, 1999.
[51] K. Holmberg, M. Ronnqvist, and D. Yuan, “An exact algorithm for the capacitated facility location problems with single sourcing”, European Journal of Operational Research, vol. 113, pp. 544-559, 1999.
[52] H. Hindi, and K. Pienkosz, “Efficient solution of large scale, singlesource, capacitated plant location problem”, Journal of the Operational Research Society, vol. 50, 268–274, 1999.
[53] S. Tragantalerngsak, J. Holt, and M. Rönnqvist, “An exact method for the two-echelon, single source, capacitated facility location problem”, European Journal of Operational Research, vol. 123, no. 3, pp. 473– 489, 2000.
[54] M. J. Cortinhal, and M. E. Captivo, “Upper and lower bounds for the single source capacitated location problem”, European Journal of Operational Research, vol. 151, no. 2, pp. 333–351, 2003.
[55] R. K. Ahuja, J. B. Orlin, S. Pallottino, M. P. Scaparra, and M. G. Scutellá, “A multi-exchange heuristic for the single-source capacitated facility location problem”, Management Science, vol. 50, no. 6, pp. 749- 760, 2004.
[56] C. H. Chen, and C. J. Ting, “Applying multiple ant colony system to solve the single source capacitated facility location problem”, Lecture Notes in Computer Science, vol. 4150, pp. 508–509, 2006.
[57] C. H. Chen, and C. J. Ting, “Combining lagrangian heuristic and ant colony system to solve the single source capacitated facility location problem”, Transportation Research Part E, vol. 44, no. 1, pp. 1099– 1122, 2008.
[58] I. Correia, and M. E. Captivo, “Bounds for the single source modular capacitated plant location problem”, Computers & Operations Research, vol. 33, pp. 2991–3003, 2006.
[59] C. K. Y. Lin, “Stochastic single-source capacitated facility location model with service level requirements”, International Journal of Production Economics, 117, pp. 439–451, 2009.
[60] Z. Yang, F. Chu, and H. Chen, “A cut-and-solve based algorithm for the single-source capacitated facility”, European Journal of Operational Research, vol. 221, pp. 521–532, 2012.
[61] B. Addis, G. Carello, and A. Ceselli, “Combining very large scale and ILP based neighborhoods for a two-level location problem”, European Journal of Operational Research, vol. 231, pp. 535–546, 2013.
[62] G. Guastaroba, and M. G. Speranza, “A heuristic for BILP problems: The single source capacitated facility location problem”, European Journal of Operational Research, vol. 238, pp. 438–450 2014.
[63] S. Dantrakul, C. Likasiri, and R. Pongvuthithum, “Applied p-median and p-center algorithms for facility location problems”, Expert Systems with Applications, vol. 41, pp. 3596–3604, 2014.
[64] M. Bieniek, “A note on the facility location problem with stochastic demands”, Omega, vol. 55, pp. 53–60, 2015.