×

Discrete approximation heuristics for the capacitated continuous location-allocation problem with probabilistic customer locations. (English) Zbl 1158.90374

Summary: The capacitated continuous location-allocation problem, also called capacitated multisource Weber problem (CMWP), is concerned with locating \(m\) facilities in the Euclidean plane, and allocating their capacity 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 nonconvex optimization problem. In this work, we focus on a probabilistic extension referred to as the probabilistic CMWP (PCMWP), and consider the situation in which customer locations are randomly distributed according to a bivariate probability distribution. We first formulate the discrete approximation of the problem as a mixed-integer linear programming model in which facilities can be located on a set of candidate points. Then we present three heuristics to solve the problem. Since optimal solutions cannot be found, we assess the performance of the heuristics using the results obtained by an alternate location-allocation heuristic that is originally developed for the deterministic version of the problem and tailored by us for the PCMWP. The new heuristics depend on the evaluation of the expected distances between facilities and customers, which is possible only for a few number of distance function and probability distribution combinations. We therefore propose approximation methods which make the heuristics applicable for any distance function and probability distribution of customer coordinates.

MSC:

90B85 Continuous location
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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)
[2] Cooper, L., Heuristic methods for location-allocation problems, SIAM Review, 6, 37-52 (1964) · Zbl 0956.90014
[3] 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
[4] Cooper, L., A random locational equilibrium problem, Journal of Regional Sciences, 14, 47-54 (1974)
[5] 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
[6] Katz, I. N.; Cooper, L., Normally and exponentially distributed locational equilibrium problem, Journal of Research of the National Bureau of Standards Section: B, 53-73 (1976) · Zbl 0364.90113
[7] Wesolowsky, G. O., The Weber problem with rectangular distances and randomly distributed destinations, Journal of Regional Sciences, 17, 53-60 (1977)
[8] Özkısacık KC, Altınel İK, Aras N. Solving probabilistic multi-facility Weber problem by vector quantization. In: Paias A, Saldanha da Gama F (Eds.). EURO Winter Institute on Location and Logistics, Estoril, Portugal, 2007. p. 313-32.; Özkısacık KC, Altınel İK, Aras N. Solving probabilistic multi-facility Weber problem by vector quantization. In: Paias A, Saldanha da Gama F (Eds.). EURO Winter Institute on Location and Logistics, Estoril, Portugal, 2007. p. 313-32.
[9] Cooper, L., The stochastic transportation-location problem, Computational Mathematics with Applications, 4, 265-275 (1978) · Zbl 0397.90066
[10] Love, R. F.; Morris, J. G., Modelling inter-city road distances by mathematical functions, Operational Research Quarterly, 23, 61-71 (1972) · Zbl 0231.90059
[11] Love, R. F.; Morris, J. G., Mathematical models of road travel distances, Management Sciences, 25, 130-139 (1979) · Zbl 0419.90053
[12] Durmaz E, Heuristics for the probabilistic multi-facility Weber problem, MS thesis, Industrial Engineering Department, Boğaziçi University, İstanbul, Turkey; 2007.; Durmaz E, Heuristics for the probabilistic multi-facility Weber problem, MS thesis, Industrial Engineering Department, Boğaziçi University, İstanbul, Turkey; 2007.
[13] Berman, O.; Krass, D., Facility location problems with stochastic demands and congestion, (Drezner, Z.; Hamacher, H. W., Facility Location: Applications and Theory (2002), Springer: Springer Berlin), 329-371 · Zbl 1061.90068
[14] Averbakh, I.; Berman, O.; Drezner, Z.; Wesolowsky, G., The plant location problem with demand-dependent setup costs and centralized allocation, European Journal of Operational Research, 111, 543-554 (1998) · Zbl 0937.90054
[15] 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
[16] Cooper, L., The transportation-location problem, Operations Research, 20, 94-108 (1972) · Zbl 0237.90036
[17] Zainuddin, Z. M.; Salhi, S., A perturbation heuristic for the capacitated multisource Weber problem, European Journal of Operational Research, 179, 1194-1207 (2007) · Zbl 1127.90048
[18] Altınel İK, Özkısacık KC, Aras N. Heuristics for the probabilistic multi-facility Weber problem. Research Paper Series No: FBE-IE-14/2006-17, Boğaziçi University, Bebek, İstanbul, 2006.; Altınel İK, Özkısacık KC, Aras N. Heuristics for the probabilistic multi-facility Weber problem. Research Paper Series No: FBE-IE-14/2006-17, Boğaziçi University, Bebek, İstanbul, 2006.
[19] Drezner, Z.; Simchi-Levi, D., Asymptotic behavior of the Weber location problem on the plane, Annals of Operations Research, 40, 163-172 (1992) · Zbl 0787.90043
[20] Hansen, P.; Mladenović, N.; Taillard, É., Heuristic solution of the multisource Weber problem as a \(p\)-median problem, Operations Research Letters, 22, 55-62 (1998) · Zbl 0911.90240
[21] Hansen, P.; Perreur, J.; Thisse, F., Location theory, dominance and convexity: some further results, Operations Research, 28, 1241-1250 (1980) · Zbl 0449.90027
[22] Sherali, H. D.; Ramachandran, S.; Kim, S., A localization and reformulation discrete programming approach for the rectilinear distance location-allocation problem, Discrete Applied Mathematics, 49, 357-378 (1994) · Zbl 0799.90071
[23] Aras, N.; Orbay, M.; Altınel, İ. K., Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem, Journal of the Operational Research Society, 59, 64-79 (2008) · Zbl 1167.90557
[24] Aras, N.; Altınel, İ. K.; Orbay, M., New heuristic methods for the capacitated multi-facility Weber problem, Naval Research Logistics, 54, 21-32 (2007) · Zbl 1124.90016
[25] Gamal, M. D.H.; Salhi, S., A cellular heuristic for the multisource Weber problem, Computers and Operations Research, 30, 1609-1624 (2003) · Zbl 1039.90033
[26] 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
[27] 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
[28] Al-Loughani I. Algorithmic approaches for solving the Euclidean distance location-allocation problems, PhD dissertation, Industrial and System Engineering, Virginia Polytechnic Institute and State University, Blacksburgh, VA, 1997.; Al-Loughani I. Algorithmic approaches for solving the Euclidean distance location-allocation problems, PhD dissertation, Industrial and System Engineering, Virginia Polytechnic Institute and State University, Blacksburgh, VA, 1997.
[29] Sherali, H. D.; Al-Loughani, I.; Subramanian, S., Global optimization procedures for the capacitated Euclidean and \(\ell_p\) distance multifacility location-allocation problems, Operations Research, 50, 433-448 (2002) · Zbl 1163.90615
[30] Charon, I.; Hudry, O., The noising methods: a generalization of some metaheuristics, European Journal of Operational Research, 135, 86-101 (2001) · Zbl 1063.90042
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.