Discretization Based Heuristics for the Capacitated Multi-facility Weber Problem with Convex Polyhedral Barriers
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.
[1] Cooper, L. (1972). The transportation-location prob- lem. Oper. Res., 20, 94-108.
[2] Sherali, H.D. and Nordai, F.L. (1988). NP-hard, ca-pacitated, balanced p-median problems on a chain graph with a continuum of link demands. Math. Oper. Res., 13, 32-49.
[3] Meggido, N. and Supowit, K.J. (1984). On the com- plexity of some common geometric location problems. SIAM J. Comput., 13, 182-196.
[4] Alpaydln, E., Altlnel, I(˙).K. and Aras, N. (1996). Para-metric distance functions vs. nonparametric neural networks for estimating road travel distances. Eur. J. Oper. Res., 93, 230-243.
[5] Brimberg, J., Walker, J.H. and Love, R.F. (2007). Es- timation of travel distances with the weighted lp norm: some empirical results. J. Transp. Geogr., 15, 62-72.
[6] Klamroth, K. (2002). Single-facility location problems with barriers. Springer, Berlin.
[7] Cooper, L. (1964). Heuristic methods for location- allocation problems. SIAM Rev., 6, 37-53.
[8] Kuenne, R.E. and Soland, R.M. (1972). Exact and approximate solutions to the multisource Weber prob- lem. Math. Program., 3, 193-209.
[9] Rosing, K.E. (1992). An optimal method for solving the (generalized) multi-Weber problem. Eur. J. Oper. Res., 58, 414-426.
[10] Krau, S. (1997). Extensions du probl、eme de Weber. Thesis (PhD). University of Montr/eal.
[11] Righini, G. and Zaniboni, L. (2007). A branch-and- price algorithm for the multi-source Weber problem. Int. J. Oper. Res., 2, 188-207.
[12] Love, R.F. and Juel, H. (1982). Properties and solu- tion methods for large location-allocation problems. J. Oper. Res. Soc., 33, 443-452.
[13] Bongartz, I., Calamai, P.H. and Conn, A.R. (1994). A projection method for the ℓp norm location-allocation problems. Math. Program., 66, 283-312.
[14] 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.
[15] Gamal, M.D.H. and Salhi, S. (2003). A cellular heuris- tic for the multi-source Weber problem. Comput. Oper. Res., 30, 1609-1624.
[16] 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.
[17] 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.
[18] 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.
[19] Sherali, H.D., Al-Loughani, I. and Subramanian, S.(2002). Global optimization procedures for the capaci- tated Euclidean and Lp distance multifacility location- allocation problem. Oper. Res., 50, 433-448.
[20] Aky¨uz, M.H., Altlnel, I(˙).K. and O(¨)ncan, T. (2014). Lo-cation and allocation based branch and bound algo- rithms for the capacitated multi-facility Weber prob- lem. Ann. Oper. Res., 222, 45-71.
[21] Zainuddin, Z.M. and Salhi, S. (2007). A perturbation- based heuristic for the capacitated multisource Weber problem. Eur. J. Oper. Res., 179, 1194-1207.
[22] 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.
[23] Aras, N., Altlnel, I(˙).K. and Orbay, M. (2007). New heuristic methods for the capacitated multi-facility Weber problem. Nav. Res. Log., 54, 21-32.
[24] Boyacl, B., Altlnel, I(˙).K. and Aras, N. (2013). Ap-proximate solution methods for the capacitated multi- facility Weber problem. IIE Trans., 45, 97-120.
[25] Luis, M., Salhi, S. and Nagy, G. (2011). A guided re- active GRASP for the capacitated multi-source Weber problem. Comput. Oper. Res., 38, 1014-1024.
[26] Aky¨uz, M.H., O(¨)ncan, T. and Altlnel, I(˙).K. (2012). Ef-ficient approximate solution methods for the multi- commodity capacitated multi-facility Weber problem. Comput. Oper. Res., 39, 225-237.
[27] Aky¨uz, M.H., O(¨)ncan, T. and Altlnel, I(˙).K. (2013).Beam search heuristics for the single and multi- commodity capacitated Multi-facility Weber Prob- lems. Comput. Oper. Res., 40, 3056-3068.
[28] Brimberg, J., Hansen, P., Mladenovi/c, N. and Salhi, S. (2008). A survey of solution methods for the contin- uous location-allocation problem. Int. J. Oper. Res., 5, 1-12.
[29] 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 cir- cle. Eur. J. Oper. Res., 6, 166-173.
[30] 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.
[31] Batta, R., Ghose, A. and Palekar, U.S., (1989). Locat- ing Facilities on the Manhattan Metric with Arbitrar- ily Shaped Barriers and Convex Forbidden Regions. Transport. Sci., 23, 26-36.
[32] Aneja, Y.P. and Parlar, M. (1994). Technical Note– Algorithms for Weber Facility Location in the Pres- ence of Forbidden Regions and/or Barriers to Travel. Transport. Sci., 28, 70-76.
[33] Butt, S.E. and Cavalier, T.M. (1996). An e伍cient al- gorithm for facility location in the presence of forbid- den regions. Eur. J. Oper. Res., 90, 56-70.
[34] Klamroth, K. (2001). A reduction result for location problems with polyhedral barriers. Eur. J. Oper. Res., 130, 486-497.
[35] 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.
[36] Bischof, M. and Klamroth, K. (2007). An e伍cient so- lution method for Weber problems with barriers based on genetic algorithm. Eur. J. Oper. Res., 177, 22-41.
[37] Bischof, M., Fleischmann, T. and Klamroth, K.(2009). The multi-facility location-allocation problem with polyhedral barriers. Comput. Oper. Res., 36, 1376-1392.
[38] Wendell, R.E. and Hurter, A.P. (1973). Location the- ory, dominance and convexity. Oper. Res. 21, 314-320.
[39] Ghosh, S.K. (2007). Visibility algorithms in the plane. Cambridge University Press, New York.
[40] Dijkstra, E.W. (1959). A note on two problems in con- nexion with graphs. Numer. Math., 1, 269-271.
[41] Hansen, P., Perreur, J. and Thisse, F. (1980). Loca- tion theory, dominance and convexity: some further results. Oper. Res., 28, 1241-1250.
[42] 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.
[43] Brimberg, J. and Love, R.F. (1993). Global conver- gence of a generalized iterative procedure for the min- isum location problem with Lp distances. Oper. Res., 41, 1153-1163.
[44] Brimberg, J., Chen, R. and Chen, D. (1998). Acceler- ating convergence in the Fermat-Weber location prob- lem. Oper. Res., 22, 151-157
[45] Martello, S. and Toth P. (1990). Knapsack prob- lems: algorithms and computer implementations. Wi- ley, New York.
[46] Held, M., Wolfe, P. and , Crowder H.P. (1974). Val- idation of subgradient optimization. Math. Program., 6, 62-88.
[47] Glover, F.W. and Laguna, M. (1997). Tabu search. Kluwer academic publishers, Boston
[48] Boyacl, B. (2009). Solving the capacitated multifacility Weber problem approximately. Thesis (MSc). Bogazi>ci√ University.