Discretization Based Heuristics for the Capacitated Multi-facility Weber Problem with Convex Polyhedral Barriers
DOI:
https://doi.org/10.11121/ijocta.01.2018.00388Abstract
The Capacitated Multi-facility Weber Problem addresses optimally locating I 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.
Downloads
References
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.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
