Discretization Based Heuristics for the Capacitated Multi-facility Weber Problem with Convex Polyhedral Barriers

M. Hakan Akyüz


The Capacitated Multi-facility Weber Problem addresses optimally locating capacitated facilities in the plane and satisfying demand of J customers so as to minimize the total transportation cost. It assumes that facilities can be located anywhere on the plane and customers are directly connected to them. This study considers the case where there exist convex polyhedral barriers blocking passage and locating facilities inside. Then, the distances between facilities and customers have to be measured by taking into account the polyhedral barriers. The resulting problem is non-convex and difficult to solve. We propose several discretization based heuristic procedures which are especially designed for the problem. The performance of the suggested methods are tested on an extensive set of randomly generated test instances which are derived from standard test instances. Our results imply that the suggested heuristics yield very accurate and efficient solutions for this problem.

Full Text:



Cooper, L. (1972). The transportation-location problem. Oper. Res., 20, 94-108.

Sherali, H.D. and Nordai, F.L. (1988). NP-hard, capacitated, balanced p-median problems on a chain graph with a continuum of link demands. Math. Oper. Res., 13, 32-49.

Meggido, N. and Supowit, K.J. (1984). On the complexity of some common geometric location problems. SIAM J. Comput., 13, 182-196.

Alpaydın, E., Altınel, I˙.K. and Aras, N. (1996). Parametric distance functions vs. nonparametric neural networks for estimating road travel distances. Eur. J. Oper. Res., 93, 230-243.

Brimberg, J., Walker, J.H. and Love, R.F. (2007). Estimation of travel distances with the weighted lp norm: some empirical results. J. Transp. Geogr., 15, 62-72.

Klamroth, K. (2002). Single-facility location problems with barriers.

Springer, Berlin.

Cooper, L. (1964). Heuristic methods for location-allocation problems.

SIAM Rev., 6, 37-53.

Kuenne, R.E. and Soland, R.M. (1972). Exact and approximate solutions to the multisource Weber problem. Math. Program., 3, 193- 209.

Rosing, K.E. (1992). An optimal method for solving the (generalized) multi-Weber problem. Eur. J. Oper. Res., 58, 414-426.

Krau, S. (1997). Extensions du probl`eme de Weber. Thesis (PhD).

University of Montr´eal.

Righini, G. and Zaniboni, L. (2007). A branch-and-price algorithm for the multi-source Weber problem. Int. J. Oper. Res., 2, 188-207.

Love, R.F. and Juel, H. (1982). Properties and solution methods for large location-allocation problems. J. Oper. Res. Soc., 33, 443-452.

Bongartz, I., Calamai, P.H. and Conn, A.R. (1994). A projection method for the Rp norm location-allocation problems. Math. Program., 66, 283- 312.

Hansen, P., Mladenovi´c, N. and Taillard, E´ . (1998). Heuristic solution of the multisource Weber problem as a p-median problem. Oper. Res. Lett., 22, 55-62.

Gamal, M.D.H. and Salhi, S. (2003). A cellular heuristic for the multi- source Weber problem. Comput. Oper. Res., 30, 1609-1624.

Brimberg, J., Hansen, P. and Mladenovi´c, N. (2006). Decomposition strategies for large-scale continuous location-allocation problems. IMA J. Manag Math., 17, 307-316.

Brimberg, J., Drezner, Z., Mladenovi´c, N. and Salhi, S. (2014). A new local search for continuous location problems. Eur. J. Oper. Res., 232, 256-265.

Drezner, Z., Brimberg, J., Mladenovi´c, N. and Salhi, S. (2016). New local searches for solving the multi-source Weber problem. Ann. Oper. Res., 246, 181-203.

Sherali, H.D., Al-Loughani, I. and Subramanian, S. (2002). Global optimization procedures for the capacitated Euclidean and Lp distance multifacility location-allocation problem. Oper. Res., 50, 433-448.

Akyu¨z, M.H., Altınel,I˙.K. andO¨ ncan, T. (2014). Location and allocation based branch and bound algorithms for the capacitated multi- facility Weber problem. Ann. Oper. Res., 222, 45-71.

Zainuddin, Z.M. and Salhi, S. (2007). A perturbation-based heuristic for the capacitated multisource Weber problem. Eur. J. Oper. Res., 179, 1194-1207.

Luis, M., Salhi, S. and Nagy, G. (2009). Region-rejection based heuristics for the capacitated multi-source Weber problem. Comput. Oper. Res., 36, 2007-2017.

Aras, N., Altınel, I˙.K. and Orbay, M. (2007). New heuristic methods for the capacitated multi-facility Weber problem. Nav. Res. Log., 54, 21-32.

Boyacı, B., Altınel, I˙.K. and Aras, N. (2013). Approximate solutionmethods for the capacitated multi-facility Weber problem. IIE Trans., 45, 97-120.

Luis, M., Salhi, S. and Nagy, G. (2011). A guided reactive GRASP for the capacitated multi-source Weber problem. Comput. Oper. Res., 38, 1014-1024.

Akyu¨z, M.H., O¨ ncan, T. and Altınel, I˙.K. (2012). Efficient approximate solution methods for the multi-commodity capacitated multi-facility Weber problem. Comput. Oper. Res., 39, 225-237.

Akyu¨z, M.H., O¨ ncan, T. and Altınel, I˙.K. (2013). Beam search heuristics for the single and multi-commodity capacitated Multi-facility Weber Problems. Comput. Oper. Res., 40, 3056-3068.

Brimberg, J., Hansen, P., Mladenovi´c, N. and Salhi, S. (2008). A survey of solution methods for the continuous location-allocation problem. Int. J. Oper. Res., 5, 1-12.

Katz, I.N. and Cooper, L. (1981). Facility location in the presence of forbidden regions, I: formulation and the case of Euclidean distance with one forbidden circle. Eur. J. Oper. Res., 6, 166-173.

Larson, R.C. and Sadiq, G. (1983). Facility Locations with the Manhattan Metric in the Presence of Barriers to Travel. Oper. Res., 31, 652-669.

Batta, R., Ghose, A. and Palekar, U.S., (1989). Locating Facilities on the Manhattan Metric with Arbitrarily Shaped Barriers and Convex Forbidden Regions. Transport. Sci., 23, 26-36.

Aneja, Y.P. and Parlar, M. (1994). Technical Note–Algorithms for Weber Facility Location in the Presence of Forbidden Regions and/or Barriers to Travel. Transport. Sci., 28, 70-76.

Butt, S.E. and Cavalier, T.M. (1996). An efficient algorithm for facility location in the presence of forbidden regions. Eur. J. Oper. Res., 90, 56-70.

Klamroth, K. (2001). A reduction result for location problems with polyhedral barriers. Eur. J. Oper. Res., 130, 486-497.

McGarvey, R.G. and Cavalier, T.M. (2003). A global optimal approach to facility location in the presence of forbidden regions. Comput. Ind. Eng., 45, 1-15.

Bischoff M. and Klamroth, K. (2007). An efficient solution method for Weber problems with barriers based on genetic algorithm. Eur. J. Oper. Res., 177, 22-41.

Bischoff M., Fleischmann, T. and Klamroth, K. (2009). The multi- facility location-allocation problem with polyhedral barriers. Comput. Oper. Res., 36, 1376-1392.

Wendell, R.E. and Hurter, A.P. (1973). Location theory, dominance and convexity. Oper. Res. 21, 314-320.

Ghosh, S.K. (2007). Visibility algorithms in the plane. Cambridge University Press, New York.

Dijkstra, E.W. (1959). A note on two problems in connexion with graphs.

Numer. Math., 1, 269-271.

Hansen, P., Perreur, J. and Thisse, F. (1980). Location theory, dominance and convexity: some further results. Oper. Res., 28, 1241- 1250.

Weiszfeld, E. (1937). Sur le point lequel la somme des distances de n points donn´e est minimum. Tˆohoku Math. J., 43, 355-386.

Brimberg, J. and Love, R.F. (1993). Global convergence of a generalized iterative procedure for the minisum location problem with Lp distances. Oper. Res., 41, 1153-1163.

Brimberg, J., Chen, R. and Chen, D. (1998). Accelerating convergence in the Fermat-Weber location problem. Oper. Res., 22, 151-157

Martello, S. and Toth P. (1990). Knapsack problems: algorithms and computer implementations. Wiley, New York.

Held, M., Wolfe, P. and , Crowder H.P. (1974). Validation of subgradient optimization. Math. Program., 6, 62-88.

Glover, F.W. and Laguna, M. (1997). Tabu search. Kluwer academic publishers, Boston

Boyacı, B. (2009). Solving the capacitated multifacility Weber problem approximately. Thesis (MSc). Boğaziçi University.

DOI: http://dx.doi.org/10.11121/ijocta.01.2018.00388


  • There are currently no refbacks.

Copyright (c) 2017 M. Hakan Akyüz

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.


   ithe_170     crossref_284         ind_131_43_x_117_117  logo_ehost_120    ulakbim_140   proquest_256_x_97_256   zbmath_251_x_86_251 more...