The \(p\)-median problem: a survey of metaheuristic approaches. (English) Zbl 1163.90610
Summary: The \(p\)-median problem is one of the basic models in discrete location theory. As with most location problems, it is classified as NP-hard, and so, heuristic methods are usually used to solve it. Metaheuristics are frameworks for building heuristics. In this survey, we examine the \(p\)-median, with the aim of providing an overview on advances in solving it using recent procedures based on metaheuristic rules.
MSC:
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Alp, O.; Erkut, E.; Drezner, D., An efficient genetic algorithm for the \(p\)-median problem, Annals of Operations Research, 122, 21-42 (2003) · Zbl 1038.90046 |
| [2] | Barahona, F.; Anbil, R., The volume algorithm: producing primal solutions with a subgradient algorithm, Mathematical Programming, 87, 385-399 (2000) · Zbl 0961.90058 |
| [3] | Baum, E. B., Toward practical “neural” computation for combinatorial optimization problems, (Denker, J., Neural Networks for Computing (1986), American Institute of Physics) |
| [4] | Beasley, J. E., A note on solving large \(p\)-median problems, European Journal of Operational Research, 21, 270-273 (1985) · Zbl 0569.90021 |
| [5] | Beasley, J. E., OR-Library: Distributing test problems by electronic mail, Journal of Operational Research Society, 41, 1069-1072 (1990) |
| [6] | Beasley, J. E., Lagrangian heuristics for location problems, European Journal of Operational Research, 65, 383-399 (1993) · Zbl 0768.90045 |
| [7] | Beltran, C., Tadonki, C., Vial, J.-Ph., 2004. Solving the \(p\); Beltran, C., Tadonki, C., Vial, J.-Ph., 2004. Solving the \(p\) · Zbl 1151.90521 |
| [8] | Bowerman, J.; Calamai, P. H.; Hall, G. B., The demand partitioning method for reducing aggregation errors in \(p\)-median problems, Computers & Operations Research, 26, 1097-1111 (1999) · Zbl 0940.90053 |
| [9] | Brandeau, M. L.; Chiu, S. S., An overview of representative problems in location research, Management Science, 35, 6, 645-674 (1989) · Zbl 0669.90040 |
| [10] | Captivo, E. M., Fast primal and dual heuristics for the \(p\)-median location problem, European Journal of Operational Research, 52, 65-74 (1991) · Zbl 0738.90044 |
| [11] | Casillas, P., Data aggregation and the \(p\)-median problem in continuous space, (Ghosh, A.; Rushton, G., Spatial Analysis and Location Allocation Models (1987), Van Nostrand Reinhold Publishers) |
| [12] | Chaudhry, S. S.; He, S.; Chaudhry, P. E., Solving a class of facility location problems using genetic algorithm, Expert Systems, 20, 86-91 (2003) |
| [13] | Chiyoshi, F.; Galvão, D., A statistical analysis of simulated annealing applied to the \(p\)-median problem, Annals of Operations Research, 96, 61-74 (2000) · Zbl 0997.90042 |
| [14] | Christofides, N., Graph Theory: An Algorithmic Approach (1975), Academic Press: Academic Press New York · Zbl 0321.94011 |
| [15] | Cornuejols, G.; Fisher, M. L.; Nemhauser, G. L., Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms, Management Science, 23, 789-810 (1977) · Zbl 0361.90034 |
| [16] | Crainic, T.; Gendreau, M.; Hansen, P.; Mladenović, N., Cooperative parallel variable neighborhood search for the \(p\)-median, Journal of Heuristics, 10, 293-314 (2004) |
| [17] | Current, J.; Schilling, D., Elimination of source A and B errors in \(p\)-median location problems, Geographical Analysis, 19, 95-110 (1987) |
| [18] | Dai, Z.; Cheung, T.-Y., A new heuristic approach for the \(p\)-median problem, Journal of the Operational Research Society, 48, 9, 950-960 (1997) · Zbl 0892.90118 |
| [19] | Daskin, M., Network and Discrete Location (1995), Wiley: Wiley New York · Zbl 0870.90076 |
| [20] | Densham, P. J.; Rushton, G., A more efficient heuristic for solving large \(p\)-median problems, Papers in Regional Science, 71, 3, 307-329 (1992) |
| [21] | Dibbie, C., Densham, P.J., 1993. Generating intersecting alternatives in GIS and SDSS using genetic algorithms. In: GIS/LIS Symposium, Lincoln.; Dibbie, C., Densham, P.J., 1993. Generating intersecting alternatives in GIS and SDSS using genetic algorithms. In: GIS/LIS Symposium, Lincoln. |
| [22] | Domínguez Merino, E.; Muñoz Pérez, J., An efficient neural network for the \(p\)-median problem, Lecture Notes in Artificial Intelligence, 2527, 460-469 (2002) · Zbl 1036.68529 |
| [23] | Domínguez Merino, E., Muñoz Pérez, J., Jerez Aragonés, J., 2003. Neural Network Algorithms for the \(p\); Domínguez Merino, E., Muñoz Pérez, J., Jerez Aragonés, J., 2003. Neural Network Algorithms for the \(p\) |
| [24] | Dorigo, M.; Di Caro, G., The ant colony optimization meta-heuristic, (Corne, G.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw-Hill: McGraw-Hill New York), 11-32 |
| [25] | Dorigo, M., Maniezzo, V., Colorny, A., 1991. Ant system: An autocatalytic optimizing process. Technical report TR-91-016, Politecnici di Milano.; Dorigo, M., Maniezzo, V., Colorny, A., 1991. Ant system: An autocatalytic optimizing process. Technical report TR-91-016, Politecnici di Milano. |
| [26] | (Drezner, Z., Facility Location. A Survey of Applications and Methods (1995), Springer: Springer New York) · Zbl 0917.90224 |
| [27] | (Drezner, Z.; Hamacher, H., Facility Location: Applications and Theory (2002), Springer: Springer Berlin) · Zbl 0988.00044 |
| [28] | Erkut, E.; Bozkaya, B., Analysis of aggregation errors for the \(p\)-median problem, Computers & Operations Research, 26, 1075-1096 (1999) · Zbl 0940.90055 |
| [29] | Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Operations Research, 26, 992-1009 (1978) · Zbl 0422.90053 |
| [30] | Estivill-Castro, V., Torres-Velazquez R., 1999. Hybrid genetic algorithm for solving the \(p\); Estivill-Castro, V., Torres-Velazquez R., 1999. Hybrid genetic algorithm for solving the \(p\) |
| [31] | Feldman, E.; Lehrer, F. A.; Ray, T. L., Warehouse locations under continuous economies of scale, Management Science, 12, 670-684 (1966) |
| [32] | Feo, T.; Resende, M., Greedy randomized adaptive search, JOURNAL Global Optimization, 6, 109-133 (1995) · Zbl 0822.90110 |
| [33] | Francis, R. L.; Lowe, T. J.; Tamir, A., Aggregation error bounds for a class of location models, Operations Research, 48, 294-307 (2000) · Zbl 1106.90355 |
| [34] | Francis, R. L.; Lowe, T. J.; Tamir, A., Worst-case incremental analysis for a class of \(p\)-facility location problems, Networks, 39, 139-143 (2003) · Zbl 1012.90027 |
| [35] | Galvão, R. D., A dual-bounded algorithm for the \(p\)-Median problem, Operations Research, 28, 1112-1121 (1980) · Zbl 0451.90040 |
| [36] | Galvão, R. D., Use of lagrangean relaxation in the solution of uncapacitated facility location problems, Location Science, 1, 57-70 (1993) · Zbl 0923.90102 |
| [37] | García-López, F.; Melián Batista, B.; Moreno Pérez, J. A.; Moreno Vega, J. M., The parallel variable neighborhood search for the \(p\)-median problem, Journal of Heuristics, 8, 375-388 (2002) · Zbl 1012.68796 |
| [38] | García-López, F.; Melián Batista, B.; Moreno Pérez, J. A.; Moreno Vega, J. M., Parallelization of the scatter search for the \(p\)-median problem, Parallel Computing, 29, 5, 575-589 (2003) |
| [39] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1978), Freeman: Freeman New-York · Zbl 0379.68035 |
| [40] | Glover, F., Tabu Search - Part I, ORSA Journal on Computing, 1, 190-206 (1989) · Zbl 0753.90054 |
| [41] | Glover, F., Tabu Search - Part II, ORSA Journal on Computing, 2, 4-32 (1990) · Zbl 0771.90084 |
| [42] | (Glover, F.; Kochenberger, G., Handbook of Metaheuristics (2003), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht) · Zbl 1058.90002 |
| [43] | Glover, F.; Laguna, M., Tabu Search, (Reeves, C., Modern heuristic techniques for combinatorial problems (1993), Blackwell: Blackwell Oxford), (Chapter 3) · Zbl 0930.90083 |
| [44] | Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA · Zbl 0930.90083 |
| [45] | Glover, F.; Laguna, M.; Marty, R., Fundamentals of scatter search and path relinking, Control and Cybernetics, 39, 3, 653-684 (2000) · Zbl 0983.90077 |
| [46] | Goncharov, E.; Kochetov, Y., Probabilistic tabu search for the unconstrained discrete optimization problems, Discrete Analysis and Operations Research, 9, 2, 13-30 (2002), (in Russian) · Zbl 1033.90105 |
| [47] | Goodchild, M. F., The aggregation problem in location-allocation, Geographical Analysis, 11, 240-255 (1979) |
| [48] | Hansen, P.; Jaumard, B., Cluster analysis and mathematical programming, Mathematical Programming, 79, 191-215 (1997) · Zbl 0887.90182 |
| [49] | Hansen, P.; Mladenović, N., Variable neighborhood search for the \(p\)-median, Location Science, 5, 207-226 (1997) · Zbl 0928.90043 |
| [50] | Hansen, P.; Mladenović, N., Variable neighborhood search: Principles and applications, European Journal of Operational Research, 130, 449-467 (2001) · Zbl 0981.90063 |
| [51] | Hansen, P.; Mladenović, N., Developments of variable neighborhood search, (Ribeiro, C.; Hansen, P., Essays and surveys in metaheuristics (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Boston/Dordrecht/London), 415-440 · Zbl 1017.90130 |
| [52] | Hansen, P.; Mladenović, N.; Pérez-Brito, D., Variable neighborhood decomposition search, Journal of Heuristics, 7, 4, 335-350 (2001) · Zbl 1041.68623 |
| [53] | Hillsman, E. L.; Rhoda, R., Errors in measuring distances from populations to service centers, Annals of Regional Science Association, 12, 74-88 (1978) |
| [54] | Hodgson, M. J.; Neuman, S., A GIS approach to eliminating source C aggregation error in \(p\)-median models, Location Science, 1, 155-170 (1993) · Zbl 0915.90174 |
| [55] | Hodgson, M.J., Salhi, S., 1998. Using a quadtree structure to eliminate aggregation error in point to point allocation. Presented at IFORS, Montreal.; Hodgson, M.J., Salhi, S., 1998. Using a quadtree structure to eliminate aggregation error in point to point allocation. Presented at IFORS, Montreal. |
| [56] | Hosage, C. M.; Goodchild, M. F., Discrete space location-allocation solutions from genetic algorithms, Annals of Operations Research, 6, 35-46 (1986) |
| [57] | Hribar, M.; Daskin, M., A dynamic programming heuristic for the \(p\)-median problem, European Journal of Operational Research, 101, 499-508 (1997) · Zbl 0916.90179 |
| [58] | Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems; part 2. The \(p\)-medians, SIAM Journal on Applied Mathematics, 37, 539-560 (1969) · Zbl 0432.90075 |
| [59] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [60] | Kochetov, Y., Probabilistic local search algorithms for the discrete optimization problems, Discrete Mathematics and Applications, Moscow, MSU, 84-117 (2001), (in Russian) |
| [61] | Kochetov, Y.; Alekseeva, E.; Levanova, T.; Loresh, N., Large neighborhood search for the \(p\)-median problem, Yugoslav Journal of Operations Research, 15, 1, 53-63 (2005) · Zbl 1274.90196 |
| [62] | Kuehn, A. A.; Hamburger, M. J., A heuristic program for locating warehouses, Management Science, 9, 4, 643-666 (1963) |
| [63] | Laguna, M.; Martíi, R., GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS Journal on Computing, 11, 44-52 (1999) · Zbl 1092.90544 |
| [64] | Levanova, T.; Loresh, M. A., Algorithms of ant system and simulated annealing for the \(p\)-median problem, Automation and Remote Control, 65, 431-438 (2004) · Zbl 1075.90052 |
| [65] | Love, R. F.; Morris, J. G.; Wesolowsky, G. O., Facilities Location: Models and Methods (1988), North Holland: North Holland New York · Zbl 0685.90036 |
| [66] | Maranzana, F. E., On the location of supply points to minimize transportation costs, Operations Research Quarterly, 12, 138-139 (1964) |
| [67] | (Mirchandani, P.; Francis, R., Discrete location theory (1990), Wiley-Interscience) · Zbl 0718.00021 |
| [68] | Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119 |
| [69] | Mladenović, N., Moreno-Pérez, J.A., Moreno-Vega, J.M., 1995. Tabu search in solving \(p\); Mladenović, N., Moreno-Pérez, J.A., Moreno-Vega, J.M., 1995. Tabu search in solving \(p\) |
| [70] | Mladenović, N.; Moreno-Pérez, J. A.; Moreno-Vega, J. M., A chain-interchange heuristic method, Yugoslav Journal of Operations Research, 6, 41-54 (1996) · Zbl 0848.90104 |
| [71] | Moreno-Pérez, J. A.; Rodríguez, C.; Jimenez, N., Heuristic cluster algorithm for multiple facility location-allocation problem, RAIRO - Recherche Operationnelle/Operations Research, 25, 97-107 (1991) · Zbl 0726.90043 |
| [72] | Moreno-Pérez, J. A.; García-Roda, J. L.; Moreno-Vega, J. M., A parallel genetic algorithm for the discrete \(p\)-median problem, Studies in Location Analysis, 7, 131-141 (1994) · Zbl 0891.90097 |
| [73] | Mulvey, J. M.; Crowder, H. P., Cluster analysis: An application of Lagrangian relaxation, Management Science, 25, 329-340 (1979) · Zbl 0415.90085 |
| [74] | Murray, A. T.; Church, R. L., Applying simulated annealing to planning-location models, Journal of Heuristics, 2, 31-53 (1996) |
| [75] | Ng, B. T.; Han, J., Efficient and effective clustering methods for spatial data mining, (Bocca, J.; etal., 20th International Conference on Very Large Data Bases (1994), Morgan, Kaufmann), 144-155 |
| [76] | OpenMP, October 1997. OpenMP: A proposed Industry Standard API for Shared Memory Programming. White Paper.; OpenMP, October 1997. OpenMP: A proposed Industry Standard API for Shared Memory Programming. White Paper. |
| [77] | Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049 |
| [78] | Pizzolato, N. D., A heuristic for large-size \(p\)-median location problems with application to school location, Annals of Operations Research, 50, 473-485 (1994) · Zbl 0812.90096 |
| [79] | Plastria, F., On the choice of aggregation points for continuous \(p\)-median problems: A case for the gravity center, TOP, 9, 217-242 (2001) · Zbl 0994.90092 |
| [80] | (Reeves, C., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell: Blackwell Oxford) · Zbl 0942.90500 |
| [81] | Reinelt, G., tsplib - A traveling salesman problem library, ORSA Journal on Computing, 3, 376-384 (1991) · Zbl 0775.90293 |
| [82] | Resende, M.; Werneck, R. F., On the implementation of a swap-based local search procedure for the \(p\)-median problem, (Ladner, Richard E., Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (2003), SIAM: SIAM Philadelphia), 119-127 |
| [83] | Resende, M.; Werneck, R. F., A hybrid heuristic for the \(p\)-median problem, Journal of Heuristics, 10, 1, 59-88 (2004) · Zbl 1069.68600 |
| [84] | Rolland, E.; Schilling, D. A.; Current, J. R., An efficient tabu search procedure for the \(p\)-median problem, European Journal of Operational Research, 96, 329-342 (1996) · Zbl 0924.90102 |
| [85] | Rosing, K. E.; ReVelle, C. S., Heuristic concentration: Two stage solution construction, European Journal of Operational Research, 97, 75-86 (1997) · Zbl 0923.90107 |
| [86] | Rosing, K. E.; ReVelle, C. S.; Rolland, E.; Schilling, D. A.; Current, J. R., Heuristic concentration and tabu search: A head to head comparison, European Journal of Operational Research, 104, 93-99 (1998) · Zbl 0955.90056 |
| [87] | Rosing, K. E.; ReVelle, C. S.; Schilling, D. A., A gamma heuristic for the \(p\)-median problem, European Journal of Operational Research, 117, 522-532 (1999) · Zbl 0937.90055 |
| [88] | Salhi, S., A perturbation heuristic for a class of location problems, Journal of Operational Research Society, 48, 1233-1240 (1997) · Zbl 0895.90132 |
| [89] | Salhi, S., Defining tabu list size and aspiration criterion within tabu search methods, Computers and Operations Research, 29, 67-86 (2002) · Zbl 1020.90027 |
| [90] | Salhi, S.; Atkinson, R. A., Subdrop: A modified drop heuristic for location problems, Location Science, 3, 267-273 (1995) · Zbl 0916.90183 |
| [91] | Senne, L. F.E.; Lorena, A. N.L., Lagrangian/surrogate heuristics for \(p\)-median problems, (Laguna, M.; Gonzales-Velarde, J. L., Computing tools for modelling, optimization and simulation: Interfaces in computer science and operations research (2000), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht), 115-130 |
| [92] | Taillard, É. D., Heuristic methods for large centroid clustering problems, Journal of Heuristics, 9, 1, 51-73 (2003) · Zbl 1035.90038 |
| [93] | Teitz, M. B.; Bart, P., Heuristic methods for estimating the generalized vertex median of a weighted graph, Operations Research, 16, 955-961 (1968) · Zbl 0165.22804 |
| [94] | Voss, S., A reverse elimination approach for the \(p\)-median problem, Studies in Locational Analysis, 8, 49-58 (1996) · Zbl 1176.90365 |
| [95] | 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 |
| [96] | Yannakakis, M., Computational complexity, (Aarts, E. H.L.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), Wiley: Wiley Chichester), 19-56 · Zbl 0966.90506 |
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.
