×

zbMATH — the first resource for mathematics

New heuristic algorithms for solving the planar \(p\)-median problem. (English) Zbl 1348.90388
Summary: In this paper we propose effective heuristics for the solution of the planar \(p\)-median problem. We develop a new distribution based variable neighborhood search and a new genetic algorithm, and also test a hybrid algorithm that combines these two approaches. The best results were obtained by the hybrid approach. The best known solution was found in 466 out of 470 runs, and the average solution was only 0.000016% above the best known solution on 47 well explored test instances of 654 and 1060 demand points and up to 150 facilities.

MSC:
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Software:
GLOB; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alp, O.; Drezner, Z.; Erkut, E., An efficient genetic algorithm for the p-Median problem, Ann Oper Res, 122, 21-42, (2003) · Zbl 1038.90046
[2] Bongartz, I.; Calamai, P. H.; Conn, A. R., A projection method for ℓ_p norm location-allocation problems, Math Program, 66, 238-312, (1994) · Zbl 0829.90085
[3] Brimberg, J.; Drezner, Z., A new heuristic for solving the p-Median problem in the plane, Comput Oper Res, 40, 427-437, (2013) · Zbl 1349.90557
[4] Brimberg, J.; Drezner, Z.; Mladenovic, N.; Salhi, S., Generating good starting solutions for the p-Median problem in the plane, Electron Notes Discret Math, 39, 225-232, (2012) · Zbl 1268.90133
[5] Brimberg, J.; Drezner, Z.; Mladenović, N.; Salhi, S., A new local search for continuous location problems, Eur J Oper Res, 232, 256-265, (2014) · Zbl 1305.90267
[6] Brimberg, J.; Hansen, P.; Mladenović, N., Decomposition strategies for large-scale continuous location-allocation problems, IMA J Manag Math, 17, 307-316, (2006) · Zbl 1126.90043
[7] Brimberg, J.; Hansen, P.; Mladenović, N.; Salhi, S., A survey of solution methods for the continuous location-allocation problem, Int J Oper Res, 5, 1-12, (2008) · Zbl 1153.90487
[8] Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E., Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem, Oper Res, 48, 444-460, (2000)
[9] Brimberg, J.; Mladenović, N., Degeneracy in the multi-source Weber problem, Math Program, 85, 213-220, (1999) · Zbl 0956.90016
[10] Carlsson, S., Improving worst-case behavior of heaps, BIT Numer Math, 24, 14-18, (1984) · Zbl 0528.68041
[11] Carrizosa, E.; Dražić, M.; Dražić, Z.; Mladenović, N., Gaussian variable neighborhood search for continuous optimization, Comput Oper Res, 39, 2206-2213, (2012) · Zbl 1251.90305
[12] Chen, P. C.; Hansen, P.; Jaumard, B.; Tuy, H., A fast algorithm for the greedy interchange for large-scale clustering and Median location problems by D.-C. programming, Oper Res, 46, 548-562, (1998)
[13] Chen, R., Solution of minisum and minimax location-allocation problems with Euclidean distances, Naval Res Logist Quart, 30, 449-459, (1983)
[14] Cooper, L., Location-allocation problems, Oper Res, 11, 331-343, (1963) · Zbl 0113.14201
[15] Cooper, L., Heuristic methods for location-allocation problems, SIAM Rev, 6, 37-53, (1964) · Zbl 0956.90014
[16] Das, S.; Suganthan, P. N., Differential evolutiona survey of the state-of-the-art, IEEE Trans Evol Comput, 15, 4-31, (2011)
[17] Drezner, T.; Drezner, Z., Gender specific genetic algorithms, INFOR Inf Syst Oper Res, 44, 117-127, (2006)
[18] Drezner, Z., The planar two-center and two-Median problems, Transp Sci, 18, 351-361, (1984)
[19] Drezner, Z., A new genetic algorithm for the quadratic assignment problem, INFORMS J Comput, 15, 320-330, (2003) · Zbl 1238.90108
[20] Drezner, Z., A distance based rule for removing population members in genetic algorithms, 4OR-Quart J Oper Res, 3, 109-116, (2005) · Zbl 1084.68891
[21] Drezner Z. The fortified Weiszfeld algorithm for solving the Weber problem. IMA J Manage Math; 2013, in press.
[22] Drezner Z, Brimberg J, Salhi S, Mladenović N. New local searches for solving the multi-source Weber problem; 2013, in review. · Zbl 1357.90165
[23] Drezner, Z.; Marcoulides, G. A., A distance-based selection of parents in genetic algorithms, (Resende, M. G.C.; de Sousa, J. P., Metaheuristics: computer decision-making, (2003), Kluwer Academic Publishers Massachusetts, USA), 257-278
[24] Drezner, Z.; Mehrez, A.; Wesolowsky, G. O., The facility location problem with limited distances, Transp Sci, 25, 183-187, (1991) · Zbl 0744.90046
[25] Drezner, Z.; Salhi, S., Using hybrid metaheuristics for the one-way and two-way network design problem, Naval Res Logist, 49, 449-463, (2002) · Zbl 1013.90013
[26] Eilon, S.; Watson-Gandy, C. D.T.; Christofides, N., Distribution management, (1971), Hafner New York
[27] Epelman, M. A.; Pollock, S.; Netter, B.; Low, B. S., Anisogamy, expenditure of reproductive effort, and the optimality of having two sexes, Oper Res, 53, 560-567, (2005) · Zbl 1165.90641
[28] Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E., Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, 6, 109-122, (1986) · Zbl 0608.05027
[29] Hansen, P.; Mladenović, N., Variable neighborhood search for the p-Median, Locat Sci, 5, 207-226, (1997) · Zbl 0928.90043
[30] Hansen, P.; Peeters, D.; Thisse, J.-F., On the location of an obnoxious facility, Sist Urbani, 3, 299-317, (1981)
[31] Krau S. Extensions du problème de Weber [Ph.D. thesis]. École Polytechnique de Montréal; 1997.
[32] Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM J Comput, 13, 182-196, (1984) · Zbl 0534.68032
[33] Mladenović, N.; Dražić, M.; Kovačevic-Vujčić, V.; Čangalović, M., General variable neighborhood search for the continuous optimization, Eur J Oper Res, 191, 3, 753-770, (2008) · Zbl 1156.90005
[34] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput Oper Res, 24, 1097-1100, (1997) · Zbl 0889.90119
[35] Murtagh, B. A.; Niwattisyawong, S. R., An efficient method for the multi-depot location-allocation problem, J Oper Res Soc, 33, 629-634, (1982) · Zbl 0484.90032
[36] Plastria, F., GBSSS the generalized big square small square method for planar single facility location, Eur J Oper Res, 62, 163-174, (1992) · Zbl 0760.90067
[37] Reinelt, G., TSLIB a traveling salesman library, ORSA J Comput, 3, 376-384, (1991) · Zbl 0775.90293
[38] Salhi, S.; Gamal, M. D.H., A genetic algorithm based approach for the uncapacitated continuous location-allocation problem, Ann Oper Res, 123, 203-222, (2003) · Zbl 1053.90089
[39] Schöbel, A.; Scholz, D., The big cube small cube solution method for multidimensional facility location problems, Comput Oper Res, 37, 115-122, (2010) · Zbl 1171.90451
[40] Taillard, É., Heuristic methods for large centroid clustering problems, J Heurist, 9, 51-73, (2003) · Zbl 1035.90038
[41] Xiao YY, Zhao QH, Mladenović N. Variable neighborhood simulated annealing algorithm for capacitated vehicle routing problems. Eng Optim; 2013, in press.
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.