M. Hakan AKYÜZ

Discretization based heuristics for the capacitated multi-facility Weber problem with convex polyhedral barriers

The Capacitated Multi-facility Weber Problem (CMWP) tries to determinethe location of I capacitated facilities in the plane and to satisfy demand of Jcustomers so as to minimize the total transportation cost. The CMWP assumesthat the facilities can be located anywhere on the plane and customers aredirectly connected to them. This study considers an extension of the CMWPwhere there exist convex polyhedral barriers blocking passage and locatingfacilities inside. As a result, the distances between facilities and customershave to be measured by taking into account the polyhedral barriers. TheCMWP with convex polyhedral barriers (CMWP-B) is a non-convex problemthat is difficult to solve. We propose specially tailored discretization basedheuristic procedures. Since CMWP-B is novel to the literature, a new set oftest problems is randomly generated. Then, the performance of the suggestedmethods are tested on the test instances. Our results imply that the suggestedheuristics yield quite accurate and efficient solutions for the CMWP-B.

PDF

___

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, İ.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 locationallocation 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-andprice 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 ℓp 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 multisourceWeber 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 locationallocation problem. Oper. Res., 50, 433-448.
Akyüz, M.H., Altınel, İ.K. and Ö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 perturbationbased heuristic for the capacitated multisource Weber problem. Eur. J. Oper. Res., 179, 1194-1207.
Luis, M., Salhi, S. and Nagy, G. (2009). Regionrejection based heuristics for the capacitated multisource Weber problem. Comput. Oper. Res., 36, 2007- 2017.
Aras, N., Altınel, İ.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, İ.K. and Aras, N. (2013). Approximate solution methods for the capacitated multifacility Weber problem. IIE Trans., 45, 97-120.
Luis, M., Salhi, S. and Nagy, G. (2011). A guided reactive GRASP for the capacitated multi-sourceWeber problem. Comput. Oper. Res., 38, 1014-1024.
Akyüz, M.H., ¨Oncan, T. and Altınel, ˙I.K. (2012). Efficient approximate solution methods for the multicommodity capacitated multi-facility Weber problem. Comput. Oper. Res., 39, 225-237.
Akyüz, M.H., Öncan, T. and Altınel, İ.K. (2013). Beam search heuristics for the single and multicommodity 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 forWeber 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 prob- lems: 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.