# zbMATH — the first resource for mathematics

Solving multiple facilities location problems with separated clusters. (English) Zbl 07165812
Summary: This paper examines a special case of multi-facility location problems where the set of demand points is partitioned into a given number of subsets or clusters that can be treated as smaller independent sub-problems once the number of facilities allocated to each cluster is determined. A dynamic programming approach is developed to determine the optimal allocation of facilities to clusters. The use of clusters is presented as a new idea for designing heuristics to solve general multi-facility location problems.
##### MSC:
 90 Operations research, mathematical programming
##### Keywords:
$$p$$-median; $$p$$-center; clusters; dynamic programming; heuristics
##### Software:
 [1] Alp, O.; Drezner, Z.; Erkut, E., An efficient genetic algorithm for the $$p$$-median problem, Ann. Oper. Res., 122, 21-42 (2003) · Zbl 1038.90046 [2] Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E., Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem, Oper. Res., 48, 444-460 (2000) [3] Brimberg, J.; Hansen, P.; Mladonovic, N.; Salhi, S., A survey of solution methods for the continuous location allocation problem, Int. J. Oper. Res., 5, 1-12 (2008) [4] Brimberg, J.; Love, R. F., Solving a class of two-dimensional uncapacitated location – allocation problems by dynamic programming, Oper. Res., 46, 702-709 (1998) · Zbl 0979.90120 [6] Calik, H.; Labbé, M.; Yaman, H., P-center problems, (Location Science (2015), Springer), 79-92 [7] Chen, D.; Chen, R., New relaxation-based algorithms for the optimal solution of the continuous and discrete $$p$$-center problems, Comput. Oper. Res., 36, 1646-1655 (2009) · Zbl 1177.90246 [8] Cooper, L., Location – allocation problems, Oper. Res., 11, 331-343 (1963) · Zbl 0113.14201 [9] Cooper, L., Heuristic methods for location – allocation problems, SIAM Rev., 6, 37-53 (1964) · Zbl 0956.90014 [10] Daskin, M. S., Network and Discrete Location: Models, Algorithms, and Applications (1995), John Wiley & Sons: John Wiley & Sons New York · Zbl 0870.90076 [11] Daskin, M. S.; Maass, K. L., The p-median problem, (Location Science (2015), Springer), 21-45 [12] Drezner, Z., The p-center problem - heuristic and optimal algorithms, J. Oper. Res. Soc., 35, 741-748 (1984) · Zbl 0544.90024 [13] Drezner, Z.; Brimberg, J.; Salhi, S.; Mladenović, N., New local searches for solving the multi-source Weber problem, Ann. Oper. Res., 246, 181-203 (2016) · Zbl 1357.90165 [14] Drezner, T.; Drezner, Z., The gravity $$p$$-median model, European J. Oper. Res., 179, 1239-1251 (2007) · Zbl 1127.90045 [15] Drezner, T.; Drezner, Z.; Kalczynski, P., The multiple markets competitive location problem, Kybernetes, 45, 854-865 (2016) [16] Drezner, Z.; Salhi, S., Incorporating neighborhood reduction for the solution of the planar $$p$$-median problem, Ann. Oper. Res., 258, 639-654 (2017) · Zbl 1381.90043 [17] Huff, D. L., Defining and estimating a trade area, J. Mark., 28, 34-38 (1964) [18] Huff, D. L., A programmed solution for approximating an optimum retail location, Land Econom., 42, 293-303 (1966) [19] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems. I: The $$p$$-centers, SIAM J. Appl. Math., 37, 513-538 (1979) · Zbl 0432.90074 [20] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems. II: The $$p$$-medians, SIAM J. Appl. Math., 37, 539-560 (1979) · Zbl 0432.90075 [21] Krau, S., Extensions du probleme de Weber (1997), École Polytechnique de Montréal, (Ph.D. thesis) [22] Kuenne, R. E.; Soland, R. M., Exact and approximate solutions to the multisource Weber problem, Math. Program., 3, 193-209 (1972) · Zbl 0245.90021 [23] Love, R. F., One dimensional facility location – allocation using dynamic programming, Manage. Sci., 22, 614-617 (1976) · Zbl 0318.90054 [24] Mladenović, N.; Brimberg, J.; Hansen, P.; Moreno-Pérez, J. A., The p-median problem: A survey of metaheuristic approaches, European J. Oper. Res., 179, 927-939 (2007) · Zbl 1163.90610 [25] Reilly, W. J., The Law of Retail Gravitation (1931), Knickerbocker Press: Knickerbocker Press New York, NY [26] Wendell, R. E.; Hurter, A. P., Location theory, dominance and convexity, Oper. Res., 21, 314-320 (1973) · Zbl 0265.90040