Incorporating neighborhood reduction for the solution of the planar \(p\)-median problem.

*(English)*Zbl 1381.90043Summary: Two efficient neighborhood reduction schemes are proposed for the solution of the \(p\)-median problem on the plane. Their integration into a local search significantly reduces the run time with an insignificant deterioration in the quality of the solution. For completeness this fast local search is also embedded into one of the most powerful metaheuristic algorithms, which is a combination of a genetic algorithm and a new improvement algorithm, recently developed for this continuous location problem. Excellent results for instances with up to 1060 demand points with various values of \(p\) are reported. Eight new best known solutions for ten instances of a large problem with 3038 demand points and up to 500 facilities are also found.

PDF
BibTeX
XML
Cite

\textit{Z. Drezner} and \textit{S. Salhi}, Ann. Oper. Res. 258, No. 2, 639--654 (2017; Zbl 1381.90043)

Full Text:
DOI

##### References:

[1] | Berman, O; Drezner, Z; Krass, D, Big segment small segment global optimization algorithm on networks, Networks, 58, 1-11, (2011) · Zbl 1231.90264 |

[2] | Bongartz, I; Calamai, PH; Conn, AR, A projection method for \(ℓ _p\) norm location-allocation problems, Mathematical Programming, 66, 238-312, (1994) · Zbl 0829.90085 |

[3] | Brimberg, J; Drezner, Z, A new heuristic for solving the p-Median problem in the plane, Computers & Operations Research, 40, 427-437, (2013) · Zbl 1349.90557 |

[4] | Brimberg, J; Drezner, Z; Mladenović, N; Salhi, S, A new local search for continuous location problems, European Journal of Operational Research, 232, 256-265, (2014) · Zbl 1305.90267 |

[5] | Brimberg, J; Hansen, P; Mladenović, N, Decomposition strategies for large-scale continuous location-allocation problems, IMA Journal of Management Mathematics, 17, 307-316, (2006) · Zbl 1126.90043 |

[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] | Chen, PC; 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, Operations Research, 46, 548-562, (1998) · Zbl 0979.90099 |

[9] | Chen, R, Solution of minisum and minimax location-allocation problems with Euclidean distances, Naval Research Logistics Quarterly, 30, 449-459, (1983) |

[10] | Christofides, N; Beasley, JE, A tree search algorithm for the p-Median problem, European Journal of Operational Research, 10, 196-204, (1982) · Zbl 0481.90020 |

[11] | Church, RL, COBRA: A new formulation of the classic p-Median location problem, Annals of Operations Research, 122, 103-120, (2003) · Zbl 1039.90023 |

[12] | Church, RL, BEAMR: an exact and approximate model for the p-Median problem, Computers & Operations Research, 35, 417-426, (2008) · Zbl 1141.90463 |

[13] | Cooper, L, Location-allocation problems, Operations Research, 11, 331-343, (1963) · Zbl 0113.14201 |

[14] | Cooper, L, Heuristic methods for location-allocation problems, SIAM Review, 6, 37-53, (1964) · Zbl 0956.90014 |

[15] | Drezner, Z, The planar two-center and two-Median problems, Transportation Science, 18, 351-361, (1984) |

[16] | Drezner, Z; Brimberg, J; Salhi, S; Mladenović, N, New heuristic algorithms for solving the planar \(p\)-Median problem, Computers and Operations Research, 62, 296-304, (2015) · Zbl 1348.90388 |

[17] | Drezner, Z., Brimberg, J., Salhi, S., & Mladenović, N. (2015b). New local searches for solving the multi-source Weber problem. Annals of Operations Research. doi:10.1007/s10479-015-1797-5. · Zbl 1357.90165 |

[18] | Drezner, Z; Mehrez, A; Wesolowsky, GO, The facility location problem with limited distances, Transportation Science, 25, 183-187, (1991) · Zbl 0744.90046 |

[19] | Drezner, Z; Suzuki, A, The big triangle small triangle method for the solution of non-convex facility location problems, Operations Research, 52, 128-135, (2004) · Zbl 1165.90552 |

[20] | Eilon, S., Watson-Gandy, C. D. T., & Christofides, N. (1971). Distribution management. New York: Hafner. |

[21] | García, S; Labbé, M; Marín, A, Solving large p-Median problems with a radius formulation, INFORMS Journal on Computing, 23, 546-556, (2011) · Zbl 1243.90091 |

[22] | Golden, BL; Magnanti, TL; Nguyen, HQ, Implementing vehicle routing algorithms, Networks, 7, 113-148, (1977) · Zbl 0359.90054 |

[23] | Hansen, P; Mladenović, N, Variable neighborhood search for the \(p\)-Median, Location Science, 5, 207-226, (1997) · Zbl 0928.90043 |

[24] | Hansen, P; Peeters, D; Thisse, J-F, On the location of an obnoxious facility, Sistemi Urbani, 3, 299-317, (1981) |

[25] | Hillsman, E. (1979). A system for location-allocation analysis. Ph.D. thesis, University of Iowa, Iowa City. · Zbl 1126.90043 |

[26] | Krau, S. (1997). Extensions du problème de Weber. Ph.D. thesis, École Polytechnique de Montréal. · Zbl 1039.90023 |

[27] | Megiddo, N; Supowit, KJ, On the complexity of some common geometric location problems, SIAM Journal on Computing, 13, 182-196, (1984) · Zbl 0534.68032 |

[28] | Mladenović, N; Dražić, M; Kovačevic-Vujčić, V; Čangalović, M, General variable neighborhood search for the continuous optimization, European Journal of Operational Research, 191, 753-770, (2008) · Zbl 1156.90005 |

[29] | Mladenović, N; Hansen, P, Variable neighborhood search, Computers & Operations Research, 24, 1097-1100, (1997) · Zbl 0889.90119 |

[30] | Murtagh, BA; Niwattisyawong, SR, An efficient method for the multi-depot location-allocation problem, Journal of the Operational Research Society, 33, 629-634, (1982) · Zbl 0484.90032 |

[31] | Plastria, F, GBSSS, the generalized big square small square method for planar single facility location, European Journal of Operational Research, 62, 163-174, (1992) · Zbl 0760.90067 |

[32] | Reinelt, G, TSLIB a traveling salesman library, ORSA Journal on Computing, 3, 376-384, (1991) · Zbl 0775.90293 |

[33] | Rosing, K; ReVelle, C, Heuristic concentration: A two stage solution construction, European Journal of Operational Research, 97, 75-86, (1997) · Zbl 0923.90107 |

[34] | Rosing, KE, An optimal method for solving the (generalized) multi-Weber problem, European Journal of Operational Research, 58, 414-426, (1992) · Zbl 0760.90064 |

[35] | Rosing, KE; Harris, B, Algorithmic and technical improvements: optimal solutions to the (generalized) multi-Weber problem, Papers in Regional Science, 71, 331-352, (1992) |

[36] | Salhi, S; Sari, M, A multi-level composite heuristic for the multi-depot vehicle fleet mix problem, European Journal of Operational Research, 103, 95-112, (1997) · Zbl 0922.90061 |

[37] | Schöbel, A; Scholz, D, The big cube small cube solution method for multidimensional facility location problems, Computers and Operations Research, 37, 115-122, (2010) · Zbl 1171.90451 |

[38] | Sorensen, PA; Church, RL, A comparison of strategies for data storage reduction in location-allocation problems, Geographical Systems, 3, 221-242, (1995) |

[39] | Taillard, É, Heuristic methods for large centroid clustering problems, Journal of Heuristics, 9, 51-73, (2003) · Zbl 1035.90038 |

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.