We developed two alternate location and allocation heuristics for multi-facility location–allocation problems with
barriers. Both solution methods iteratively decompose the (MWPB) into single-facility problems and a set partitioning
problem. While in the allocation step of one method only optimal assignments are specified, in the other additionally
the paths taken around the barriers are optimized. A numerical comparison shows the superiority in efficiency and
effectiveness of a joint treatment of all discrete variables in the allocation step.
The numerical results show that the developed algorithms are suitable for the solution of reasonably sized multifacility
location–allocation problems with barriers, both with regard to computation time and solution quality. This
makes this non-convex and numerically difficult, NP-hard problem class accessible for an efficient heuristic solution.
Future research should focus on alternative solution methods, including the development of exact algorithms, for
example, based on branch and bound. Moreover, the bi-convex structure of the problem as discussed in Sections 2.1
and 2.2 could be exploited further, for example, using ideas from Gorski et al. . Another interesting extension of
the problem is a bicriteria analysis of the trade-off between the number of new facilities and the transportation cost as
mentioned in Section 4.
 Cooper L. Location–allocation problems. Operations Research 1963;11:331–43.
 Eilon S, Watson-Gandy CDT, Christofides N. Distribution management, mathematical modelling and practical analysis. New York: Hofner;
 Megiddo N, Supowit KJ. On the complexity of some common geometric location problems. SIAM Journal on Computing 1984;13:182–96.
 Cooper L. Heuristic methods for location–allocation problems. SIAM Review 1964;6:37–53.
 Brimberg J, Hansen P, Mladenovic N, Taillard ED. Improvements and comparison of heuristics for solving the uncapacitated multisourceWeber
problem. Operations Research 2000;48:444–60.
 Brimberg J, Hansen P, Mladenovic N. Decomposition strategies for large-scale continuous location–allocation problems. IMA Journal of
Management Mathematics 2006;17:307–16.
 Katz IN, Cooper L. Facility location in the presence of forbidden regions, I: formulation and the case of Euclidean distance with one forbidden
circle. European Journal of Operational Research 1981;6:166–73.
 Aneja YP, Parlar M. Algorithms forWeber facility location in the presence of forbidden regions and/or barriers to travel. Transportation Science
 Butt SE, Cavalier TM. An efficient algorithm for facility location in the presence of forbidden regions. European Journal of Operational Research
 McGarvey RG, Cavalier TM. A global optimal approach to facility location in the presence of forbidden regions. Computers & Industrial
 Klamroth K. Single-facility location problems with barriers. Springer series in operations research. Berlin: Springer; 2002.
 Brimberg J, Salhi S. A continuous location–allocation problem with zone-dependent fixed cost. Annals of Operations Research 2005;136:
 Durier R, Michelot C. On the set of optimal points to the Weber problem: further results. Transportation Science 1994;28:141–9.
 Klamroth K. A reduction result for location problems with polyhedral barriers. European Journal of Operational Research 2001;130:486–97.
 Bischoff M, Klamroth K. An efficient solution method for Weber problems with barriers based on genetic algorithms. European Journal of
Operational Research 2007;177:22–41.
 Floudas C, Visweswaran V. A global optimization algorithm (GOP) for certain classes of nonconvex NLPs—i: theory. Computers and Chemical
 Gorski J, Pfeuffer F, Klamroth K. Biconvex sets and optimization with biconvex functions—a survey and extensions. Mathematical Methods
of Operations Research 2007;66:373–407.
 Rosing KE. An optimal method for solving the (generalized) multi-Weber problem. European Journal of Operational Research 1992;58:
 Okabe A, Boots B, Sugihara K. Spatial tesselations—concepts and applications of Voronoi diagrams. Chichester, England: Wiley; 1992.
 Harris B. Two algorithms for the multi-Weber problem. Annals of Operations Research 2003;123:37–52.
 Weiszfeld EV. Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Mathematical Journal 1937;43:
 Hakimi S. Optimum location of switching centers and the absolute centers and medians of a graph. Operations Research 1964;12:450–9.
 Hakimi S. Optimum location of switching centers in a communications network and some related graph theoretic problems. Operations Research
 Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. New York: W. H. Freeman and Co.; 1979.
 Rolland E, Schilling DA, Current JR. An efficient tabu search procedure for the p-median problem. European Journal of Operational Research