×

zbMATH — the first resource for mathematics

Speeding up the optimal method of Drezner for the \(p\)-centre problem in the plane. (English) Zbl 1394.90383
Summary: This paper revisits an early but interesting optimal algorithm first proposed by Drezner to solve the continuous \(p\)-centre problem. The original algorithm is reexamined and efficient neighbourhood reductions which are mathematically supported are proposed to improve its overall computational performance. The revised algorithm yields a considerably high reduction in computational time reaching, in some cases, a decrease of 96%. This new algorithm is now able to find proven optimal solutions for large data sets with over 1300 demand points and various values of \(p\) for the first time.

MSC:
90B80 Discrete location and assignment
90B85 Continuous location
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
Software:
TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brandenberg, R.; Roth, L., New algorithms for k-center and extensions, Journal of Combinatorial Optimization, 18, 376-392, (2009) · Zbl 1184.90133
[2] Caruso, C.; Colorni, A.; Aloi, L., Dominant, an algorithm for the p-center problem, European Journal of Operational Research, 149, 53-64, (2003) · Zbl 1035.90037
[3] Chen, D.; Chen, R., New relaxation-based algorithms for the optimal solution of the continuous and discrete problems, Computers and Operations Research, 36, 1646-1655, (2009) · Zbl 1177.90246
[4] Chen, D.; Chen, R., A relaxation based algorithm for solving the conditional p-center problem, Operations Research Letters, 38, 215-217, (2010) · Zbl 1187.90180
[5] Chen, D.; Chen, R., Optimal algorithms for the α-neighbor p-center problem, European Journal of Operational Research, 225, 36-43, (2013) · Zbl 1292.90159
[6] Chen, R., Solution of minisum and minimax location-allocation problems with Euclidean distances, Naval Research Logistics Quarterly, 30, 449-459, (1983)
[7] Chen, R.; Handler, G. Y., Relaxation method for the solution of the minimax location-allocation problem in Euclidean space, Naval Research Logistics, 34, 775-788, (1987) · Zbl 0648.90026
[8] Chen, R.; Handler, G. Y., The conditional p-center problem in the plane, Naval Research Logistics, 40, 117-127, (1993) · Zbl 0769.90061
[9] Cooper, L., Heuristic methods for location-allocation problems, SIAM Review, 6, 37-53, (1964) · Zbl 0956.90014
[10] Drezner, Z., The p-centre problem - heuristic and optimal algorithms, Journal of Operational Research Society, 35, 8, 741-748, (1984) · Zbl 0544.90024
[11] Drezner, Z., Continuous center problems, (Eiselt, H. A.; Marianov, V., Foundations of location analysis, (2011), Springer New York), 63-78 · Zbl 1387.90121
[12] Elloumi, S.; Labbe, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS Journal of Computing, 16, 84-94, (2004) · Zbl 1239.90103
[13] Elshaikh, A.; Salhi, S.; Nagy, G., The continuous p-centre problem: an investigation into variable neighbourhood search with memory, European Journal of Operational Research, 241, 606-621, (2015) · Zbl 1339.90204
[14] Elzinga, J.; Hearn, D., Geometric solutions for some minimax location problems, Transportation Science, 6, 379-394, (1972)
[15] Hakimi, S. L., Optimum location of switching centers in a communications network and some related graphical theoretic problems, Operations Research, 13, 462-475, (1965) · Zbl 0135.20501
[16] Kavah, A.; Nasr, H., Solving the conditional and unconditional p-centre problem with modified harmony search: A real case study, Scientia Iranica, 4, 867-877, (2011)
[17] Travelling Salesman Problem Library (2015). http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/. Accessed 01.05.16.
[18] Lu, C., Robust weighted vertex p-center model considering uncertain data: an application to emergency management, European Journal of Operational Research, 230, 113-121, (2013) · Zbl 1317.90166
[19] Megiddo, N.; Supowit, K., On the complexity of some common geometric location problems, Society for Industrial and Applied Mathematics, 13, 1, 182-196, (1984) · Zbl 0534.68032
[20] Minieka, E., The m-centre problem, SIAM Review, 12, 138-139, (1970) · Zbl 0193.24204
[21] Pacheco, J. A.; Casado, S., Solving two location models with few facilities by using a hybrid heuristic: a real health resources case, Computers and Operations Research, 32, 3075-3091, (2004) · Zbl 1146.90460
[22] Plastria, F., Continuous covering location problems, (Drezner, Z.; Hamacher, H. W., Facility location: Applications and theory, (2002), New York Springer), 37-72 · Zbl 1013.90089
[23] Richard, D.; Beguin, H.; Peeters, D., The location of fire stations in a rural environment: a case study, Environment and Planning, 22, 39-52, (1990)
[24] Wei, H.; Murray., A. T.; Xiao, N., Solving the continuous space p-center problem: planning application issues, IMA Journal of Management Mathematics, 17, 4, 413-425, (2006) · Zbl 1126.90047
[25] Welzl, E., Smallest enclosing disks (balls and ellipsoids), (Maurer, H., New results and new trends in computer science, (1991), Springer), 359-370
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.