×

zbMATH — the first resource for mathematics

On the Weber facility location problem with limited distances and side constraints. (English) Zbl 1294.90033
Summary: The objective in the continuous facility location problem with limited distances is to minimize the sum of distance functions from the facility to the customers, but with a limit on each of the distances, after which the corresponding function becomes constant. The problem has applications in situations where the service provided by the facility is insensitive after a given threshold distance. In this paper, we propose a global optimization algorithm for the case in which there are in addition lower and upper bounds on the numbers of customers served.

MSC:
90B85 Continuous location
90C35 Programming involving graphs or networks
Software:
Bonmin; NEOS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aloise D., Hansen P., Liberti L.: An improved column generation algorithm for minimum sum-of-squares clustering. Math. Program. 131, 195–220 (2012) · Zbl 1236.90095 · doi:10.1007/s10107-010-0349-7
[2] Belotti P., Lee J., Liberti L., Margot F., Wächter A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24, 597–634 (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124
[3] Berman O., Drezner Z., Krass D.: Generalized coverage: new developments in covering location models. Comput. Oper. Res. 37, 1675–1687 (2010) · Zbl 1188.90147 · doi:10.1016/j.cor.2009.11.003
[4] Brimberg J., Chen R., Chen D.: Accelerating convergence in the Fermat–Weber location problem. Oper. Res. Lett. 22, 151–157 (1998) · Zbl 0911.90239 · doi:10.1016/S0167-6377(98)00016-9
[5] Bonami, P., Lee J.: BONMIN user’s manual. Technical report, IBM Corporation (2007)
[6] Bonami P., Biegler L., Conn A.R., Cornuéjols G., Grossmann I.E., Laird C.D., Lee J., Lodi A., Margot F., Sawaya N., Wächter A.: An algorithmic framework for convex mixed integer nonlinear programs. Discret. Optim. 5, 186–204 (2008) · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[7] Boyd S., Vandenberghe L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[8] Church R., ReVelle C.: The maximal covering location problem. Pap. Reg. Sci. Assoc. 32, 101–118 (1974) · doi:10.1007/BF01942293
[9] Church R., Roberts K.L.: Generalized coverage models and public facility location. Pap. Reg. Sci. Assoc. 53, 117–135 (1983) · doi:10.1007/BF01939922
[10] Czyzyk J., Mesnier M., Moré J.: The NEOS Server. IEEE J. Comput. Sci. Eng. 5, 68–75 (1998) · Zbl 05092192 · doi:10.1109/99.714603
[11] Berg M., Krefeld M., Overmars M., Schwarzkopf O.: Computational Geometry: Algorithms and Applications. Springer, Berlin (1997)
[12] Drezner Z., Wesolowsky G.O.: A maximin location problem with maximum distance constraints. AIIE Transact. 12, 249–252 (1980) · doi:10.1080/05695558008974513
[13] Drezner Z., Mehrez A., Wesolowsky G.O.: The facility location problem with limited distances. Transp. Sci. 25, 183–187 (1991) · Zbl 0744.90046 · doi:10.1287/trsc.25.3.183
[14] Drezner Z., Hamacher H.W.: Facility Location: Applications and Theory. Springer, Berlin (2004) · Zbl 0988.00044
[15] Drezner Z., Wesolowsky G.O., Drezner T.: The gradual covering problem. Nav. Res. Logist. 51, 841–855 (2004) · Zbl 1075.90047 · doi:10.1002/nav.20030
[16] Fekete S.P., Mitchell J.S.B., Beurer K.: On the continuous Fermat–Weber problem. Oper. Res. 53, 61–76 (2005) · Zbl 1165.90553 · doi:10.1287/opre.1040.0137
[17] Gurgel A.M.: Melhoria da segurança pública: Uma proposta para a alocação de unidades policiais utilizando o modelo das p-medianas e do caixeiro viajante. M.Sc. dissertation. Universidade Federal do Rio Grande do Norte (2010)
[18] Hansen P., Mladenović N., Mladenović N.: Heuristic solution of the multisource Weber problem as a image-median problem”. Oper. Res. Lett. 22, 55–62 (1998) · Zbl 0911.90240 · doi:10.1016/S0167-6377(98)00004-2
[19] Liberti L.: Writing global optimization software. In: Liberti, L., Maculan, N. (eds.) Global Optimization: from Theory to Implementation, pp. 211–262. Springer, Berlin (2006) · Zbl 1100.90004
[20] Liberti L.: Reformulations in mathematical programming: definitions and systematics. RAIRO-RO 43, 55–86 (2009) · Zbl 1158.90390 · doi:10.1051/ro/2009005
[21] Pirkul H., Schilling D.A.: The maximal covering location problem with capacities on total workload. Manag. Sci. 37, 233–248 (1991) · Zbl 0732.90045 · doi:10.1287/mnsc.37.2.233
[22] Schilling D.A., Jayaraman V., Barkhi R.: A review of covering problems in facility location. Locat. Sci. 1, 25–55 (1993) · Zbl 0923.90108
[23] Smith E., Pantelides C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23, 457–478 (1999) · doi:10.1016/S0098-1354(98)00286-5
[24] Smith H.K., Laporte G., Harper P.R.: Locational analysis: highlights of growth to maturity. J. Oper. Res. Soc. 60, 140–148 (2009) · Zbl 1168.90314 · doi:10.1057/palgrave.jors.2602587
[25] Tawarmalani M., Sahinidis N.V.: A polyhedral branch-and-cut approach to global optimization. Mathe. Program. 103, 225–249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[26] Wesolowsky G.O.: The Weber problem: history and perspectives. Locat. Sci. 1, 5–23 (1993) · Zbl 0923.90110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.