×

zbMATH — the first resource for mathematics

A new heuristic for solving the \(p\)-median problem in the plane. (English) Zbl 1349.90557
Summary: This paper presents a new local search for solving the continuous p-median problem in the plane. The basic idea is to first find a good starting solution by overlaying the area containing the set of demand points with a grid and solving heuristically the location problem on this grid. The solution is then used as an initial point for running an improved version of Cooper’s well-known alternating local search.

MSC:
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alp, O.; Drezner, Z.; Erkut, E., An efficient genetic algorithm for the \(p\)-Median problem, Annals of Operations Research, 122, 21-42, (2003) · Zbl 1038.90046
[2] Arthanari, T. S.; Dodge, Y., Mathematical programming in statistics, (1993), John Wiley & Sons, Inc. New York · Zbl 0850.62010
[3] Babich, G., An efficient algorithm for solving the rectilinear location – allocation problem, Environment and Planning A, 10, 1387-1395, (1978)
[4] Bongartz, I.; Calamai, P. H.; Conn, A. R., A projection method for \(\ell_p\) norm location – allocation problems, Mathematical Programming, 66, 238-312, (1994) · Zbl 0829.90085
[5] Brimberg, J.; Hansen, P.; Mladenović, N., Attraction probabilities in variable neighborhood search, 4OR—Quarterly Journal of Operations Research, 8, 181-194, (2010) · Zbl 1193.90216
[6] Brimberg, J.; Hansen, P.; Mladenović, N.; Salhi, S., A survey of solution methods for the continuous location – allocation problem, International Journal of Operations Research, 5, 1-12, (2008) · Zbl 1153.90487
[7] Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E., Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem, Operations Research, 48, 444-460, (2000)
[8] Brimberg, J.; Hodgson, M. J., Heuristics for location models, (Eiselt, H. A.; Marianov, V., Foundations of location analysis: industrial series in operations research & management science, vol. 155, (2011), Springer New York, NY), 335-355, (Chapter 15) · Zbl 1387.90109
[9] Brimberg, J.; Mladenović, N., Degeneracy in the multi-source Weber problem, Mathematical Programming, 85, 213-220, (1999) · Zbl 0956.90016
[10] Chen, R., Solution of minisum and minimax location – allocation problems with Euclidean distances, Naval Research Logistics Quarterly, 30, 449-459, (1983)
[11] Cooper, L., Location-allocation problems, Operations Research, 11, 331-343, (1963) · Zbl 0113.14201
[12] Cooper, L., Heuristic methods for location – allocation problems, SIAM Review, 6, 37-53, (1964) · Zbl 0956.90014
[13] Current, J.; Daskin, M.; Schilling, D., Discrete network location models, (Drezner, Z.; Hamacher, H. W., Facility location: applications and theory, (2002), Springer-Verlag Berlin), 81-118 · Zbl 1061.90070
[14] Densham, P. J.; Rushton, G., A more efficient heuristic for solving large p-Median problems, Papers in Regional Science, 71, 307-329, (1992)
[15] Drezner, T.; Drezner, Z.; Salhi, S., Solving the multiple competitive facilities location problem, European Journal of Operational Research, 142, 138-151, (2002) · Zbl 1081.90575
[16] Drezner, Z., The planar two-center and two-Median problems, Transportation Science, 18, 351-361, (1984)
[17] Drezner, Z., A note on accelerating the weiszfeld procedure, Location Science, 3, 275-279, (1996) · Zbl 0916.90178
[18] Drezner, Z.; Klamroth, K.; Schöbel, A.; Wesolowsky, G. O., The Weber problem, (Drezner, Z.; Hamacher, H. W., Facility location: applications and theory, (2002), Springer Berlin), 1-36 · Zbl 1041.90023
[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] Eilon, S.; Watson-Gandy, C. D.T.; Christofides, N., Distribution management, (1971), Hafner New York
[21] Eiselt, H. A.; Marianov, V., Foundations of location analysis: industrial series in operations research & management science, vol. 155, (2011), Springer New York
[22] Feldman, E.; Lehrer, F. A.; Ray, T. L., Warehouse location under continuous economies of scale, Management Science, 12, 670-684, (1966)
[23] Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 156-166, (1977)
[24] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 533-549, (1986) · Zbl 0615.90083
[25] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Boston, MA · Zbl 0930.90083
[26] Hakimi, S. L., Optimum locations of switching centres and the absolute centres and medians of a graph, Operations Research, 12, 450-459, (1964) · Zbl 0123.00305
[27] Hakimi, S. L., Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research, 13, 462-475, (1965) · Zbl 0135.20501
[28] Hansen, P.; Mladenović, N.; Taillard, E., Heuristic solution of the multisource Weber problem as a p-Median problem, Operations Research Letters, 22, 55-62, (1998) · Zbl 0911.90240
[29] Hartigan, J.; Wong, M., Algorithm AS 136: A k-means clustering algorithm, Journal of the Royal Statistical Society. Series C (Applied Statistics), 28, 100-108, (1979) · Zbl 0447.62062
[30] Krishna, K.; Narasimha Murty, M., Genetic k-means algorithm, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 29, 433-439, (1999)
[31] Kuehn, A. A.; Hamburger, M. J., A heuristic program for locating warehouses, Management Science, 9, 643-666, (1963)
[32] Love, R. F., One dimensional facility location – allocation using dynamic programming, Management Science, 22, 614-617, (1976) · Zbl 0318.90054
[33] Love, R. F.; Morris, J. G., A computation procedure for the exact solution of location – allocation problems with rectangular distances, Naval Research Logistics Quarterly, 22, 441-453, (1975) · Zbl 0338.90057
[34] Love, R. F.; Morris, J. G.; Wesolowsky, G. O., Facilities location: models & methods, (1988), North Holland New York, NY · Zbl 0685.90036
[35] Maranzana, E. E., On the location of supply points to minimize transport costs, Operational Research Quarterly, 15, 261-270, (1964)
[36] Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM Journal on Computing, 13, 182-196, (1984) · Zbl 0534.68032
[37] Mladenović, N.; Brimberg, J.; Hansen, P.; Moreno-Perez, J. A., The p-Median problem: a survey of metaheuristic approaches, European Journal of Operations Research, 179, 927-939, (2007) · Zbl 1163.90610
[38] Murtagh, B. A.; Niwattisyawong, S. R., An efficient method for the multi-depot location – allocation problem, Journal of the Operational Research Society, 33, 629-634, (1982) · Zbl 0484.90032
[39] Okabe A, Boots B, Sugihara K, Chiu SN. Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley series in probability and statistics. John Wiley; 2000. · Zbl 0946.68144
[40] Reinelt, G., TSLIB a traveling salesman library, ORSA Journal on Computing, 3, 376-384, (1991) · Zbl 0775.90293
[41] Salhi, S.; Atkinson, R. A., Subdrop: a modified drop heuristic for location problems, Location Science, 3, 267-273, (1995) · Zbl 0916.90183
[42] Scott, A. J., Location-allocation systems: a review, Geographical Analysis, 2, 95-119, (1970)
[43] Sherali, H. D.; Shetty, C. M., The rectilinear distance location – allocation problem, AIIE Transactions, 9, 136-143, (1977)
[44] Sherali, H. D.; Tuncbilek, C. H., A squared Euclidean distance location – allocation problem, Naval Research Logistics, 39, 447-469, (1992) · Zbl 0763.90061
[45] Suzuki, A.; Okabe, A., Using Voronoi diagrams, (Drezner, Z., Facility location: a survey of applications and methods, (1995), Springer New York), 103-118
[46] Tornqvist G, Nordbeck S, Rystedt B, Gould P. Multiple location analysis. In: Lund studies in geography, Series C, general, mathematical and regional geography, No. 12. University of Lund, Sweden; 1971.
[47] Weiszfeld, E., Sur le point pour lequel la somme des distances de n points donnes est minimum, Tohoku Mathematical Journal, 43, 355-386, (1936) · JFM 63.0583.01
[48] Weiszfeld, E.; Plastria, F., On the point for which the sum of the distances to n given points is minimum, Annals of Operations Research, 167, 7-41, (2009) · Zbl 1176.90616
[49] Whitaker, R., A fast algorithm for the greedy interchange for large-scale clustering and Median location problems, INFOR, 21, 95-108, (1983) · Zbl 0527.90017
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.