A location-allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations. (English) Zbl 1176.90656

Summary: The capacitated multi-facility Weber problem is concerned with locating \(m\) facilities in the Euclidean plane, and allocating their capacities to \(n\) customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation, which is even more difficult than its deterministic version. We then propose an alternate location-allocation local search heuristic generalizing the ideas used originally for the deterministic problem. In its original form, the applicability of the heuristic depends on the calculation of the expected distances between the facilities and customers, which can be done for only very few distance and probability density function combinations. We therefore propose approximation methods which make the method applicable for any distance function and bivariate location distribution.


90C59 Approximation methods and heuristics in mathematical programming


Full Text: DOI


[1] Aly, A.A.; White, J.A., Probabilistic formulations of the multi-facility Weber problem, Naval research logistics quarterly, 25, 531-547, (1978) · Zbl 0393.90056
[2] Al-Loughani, I., 1997. Algorithmic approaches for solving the Euclidean distance location – allocation problems. Ph.D. Dissertation, Industrial and System Engineering, Virginia Polytechnic Institute and State University, Blacksburgh, Virginia.
[3] Aras, N.; Orbay, M.; Altınel, İ.K., Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem, Journal of the operational society, 58, 1223-1234, (2007)
[4] Brimberg, J.; Chen, R.; Chen, D., Accelerating convergence in the fermat – weber location problem, Operations research letters, 22, 151-157, (1998) · Zbl 0911.90239
[5] Brimberg, J.; Hansen, P.; Mladenovic, N.; Taillard, T.D., Improvements and comparison of heuristics for solving the uncapacitated multi-source Weber problem, Operations research, 48, 444-460, (2000)
[6] Brimberg, J.; Love, R.F., Global convergence of a generalized iterative procedure for the minisum location problem with \(l_p\) distances, Operations research, 41, 1153-1163, (1993) · Zbl 0795.90037
[7] Cooper, L., Heuristic methods for location – allocation problems, SIAM review, 6, 37-52, (1964) · Zbl 0956.90014
[8] Cooper, L., Solutions of generalized locational equilibrium models, Journal of regional science, 7, 1-18, (1967)
[9] Cooper, L., The transportation-location problem, Operations research, 20, 94-108, (1972) · Zbl 0237.90036
[10] Cooper, L., A random locational equilibrium problem, Journal of regional sciences, 14, 47-54, (1974)
[11] Cooper, L., The stochastic transportation-location problem, Computational mathematics with applications, 4, 265-275, (1978) · Zbl 0397.90066
[12] CPLEX Mathematical Programming Optimizer, ILOG, 2006. <http://www.ilog.com/products/cplex>.
[13] Frenk, J.B.G.; Melo, M.T.; Zhang, S., A weiszfeld method for a generalized \(l_p\) distance minisum location model in continuous space, Location science., 2, 111-117, (1994) · Zbl 0926.90055
[14] GSL-GNU Scientific Library version 1.6, 2006. <http://www.gnu.org/software/gs>.
[15] Graham, R.K., An efficient algorithm for determining the convex hull of a finite planar set, Information process letter, 1, 132-133, (1972) · Zbl 0236.68013
[16] Katz, I.N.; Cooper, L., An always convergent numerical scheme for a random locational equilibrium problem, SIAM journal of numerical analysis, 11, 683-692, (1974) · Zbl 0288.60057
[17] Katz, I.N.; Cooper, L., Normally and exponentially distributed locational equilibrium problems, Journal of research of the national bureau of standards section: B, 53-73, (1976) · Zbl 0364.90113
[18] Love, R.F., Morris, J.G., 1972. Modelling inter-city road distances by mathematical functions. Operational Research. · Zbl 0231.90059
[19] Love, R.F.; Morris, J.G., Mathematical models of road travel distances, Management sciences, 25, 130-139, (1979) · Zbl 0419.90053
[20] Mathc Yahoo Group, 2006.
[21] Rao, J.R.; Varma, N.H., Stochastic multi-facility minisum location problem involving Euclidean distances, Opsearch, 22, 232-240, (1985) · Zbl 0578.90023
[22] Rockafeller, R.T., Convex analysis, Princeton mathematical science series: 28, (1970), Princeton University Press Princeton NJ, USA
[23] Sherali, H.D.; Al-Loughani, I.; Subramanian, S., Global optimization procedures for the capacitated Euclidean and \(l_p\) distance multifacility location – allocation problems, Operations research, 50, 433-448, (2002) · Zbl 1163.90615
[24] Sherali, H.D.; Nordai, F.L., NP-hard, capacitated, balanced p-Median problems on a chain graph with a continuum of link demands, Mathematics of operations research, 13, 32-49, (1988) · Zbl 0651.90025
[25] Skiena, S.S.; Revilla, M., Programming challenges: the programming contest training manual, (2003), New York Springer-Verlag · Zbl 1035.68033
[26] Tan, T.; Güllü, R.; Erkip, N., Modelling imperfect advance demand information and analysis of optimal inventory policies, European journal of operational research, 177, 897-923, (2006) · Zbl 1109.90009
[27] Ward, J.E.; Wendell, R.E., Using block norms for location modeling, Operations research, 33, 1074-1090, (1985) · Zbl 0582.90026
[28] Weiszfeld, E., Sur le point lequel la somme des distances de n points donné est minimum, Tôhoku mathematics journal, 43, 355-386, (1937) · Zbl 0017.18007
[29] Wesolowsky, G.O., The Weber problem with rectangular distances and randomly distributed destinations, Journal of regional sciences, 17, 53-60, (1977)
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.