Aggregation and non aggregation techniques for large facility location problems: A survey
DOI:
https://doi.org/10.2298/YJOR140909001IKeywords:
Large location problem, p-median and p-centre problems, point representation, aggregationAbstract
A facility location problem is concerned with determining the location of some useful facilities in such a way so to fulfil one or a few objective functions and constraints. We survey those problems where, in the presence of a large number of customers, some form of aggregation may be required. In addition, a review on conditional location problems where some (say q) facilities already exist in the study area is presented.References
Aikens, C. H., “Facility location models for distribution planning”, European Journal of Operational Research, 22 (1985) 263-279.
Andersson, G., Francis, R.L., Normark, T., and Rayco, M.B., “Aggregation method experimentation for large-scale network location problems”, Location Science, 6 (1998) 25-39.
Al-Khedhairi, A., and Salhi, S., “Enhancements to two exact algorithms for solving the vertex p-center problem”, Journal of Mathematical Modelling and Algorithms, 4 (2005) 129-147.
Avella, P., Boccia, M., Salerno, S., and Vasilyev, I., “An aggregation heuristic for large scale p-median problem”, Computers and Operations Research, 39 (2012) 1625-1632.
Avella, P., Sassano, A., and Vasilyev, I., “Computational study of large-scale p-median problems”, Mathematical Programming, 109 (2007) 89-114.
Bach, L., “The problem of aggregation and distance for analysis of accessibility and access opportunity in location-allocation models”, Environment and Planning A, 13 (1981) 955-978.
Ballou, R. H., “Measuring transport costing error in customer aggregation for facility location”, Transportation Journal, 33 (1994) 49-59.
Berman, O., and Drezner, Z., “A new formulation for the conditional p-median and p-center problems”, Operations Research Letters, 36 (2008) 481-483.
Berman, O., and Simchi-Levi, D., “The conditional location problem on networks”, Transportation Science, 24 (1990) 77-78.
Bowerman, R.L., Calamai, P.H., and Brent Hall, G., “The demand partitioning method for reducing aggregation errors in p-median problems”, Computers and Operations Research, 26 (1999) 1097-1111.
Bozkaya, B., and Tansel, B., “A spanning tree approach to the absolute p-center problem”, Location Science, 6 (1998) 83-107.
Brandeau, M.L., and Chiu, S.S., “An Overview of Representative Problems in Location Research”, Management Science, 35 (1989) 645-674.
Brimberg, J., Hansen, P., Mladenović, N., and Salhi, S., “A Survey of Solution Methods for the Continuous Location-Allocation Problem”, International Journal of Operations Research, 5 (2008) 1-12.
Calik, H., and Tansel, B.C., “Double bound method for solving the p-center location problem”, Computers and Operations Research, 40 (2013) 2991-2999.
Caruso, C., Colorni, A., and Aloi, L., “Dominant, an algorithm for the p-center problem”, European Journal of Operational Research, 149 (2003) 53-64.
Casillas, P., “Aggregation problems in location-allocation modeling. In Gosh, A., and Rushton, G. (Eds.), Spatial analysis and location-allocation models (327-344)”, Van Nostrand Reinhold, New York, 1987.
Chen, R., “Conditional minisum and minimax location-allocation problems in Euclidean space”, Transportation Science, 22 (1990) 158-160.
Chen, D., and Chen, R., “New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems”, Computers and Operations Research, 36 (2009) 1646-1655.
Chen, D., and Chen, R., “A relaxation-based algorithm for solving the conditional p-center problem”, Operations Research Letters, 38 (2010) 215-217.
Cheng, “An improved algorithm for the p-center problem on interval graphs with unit lengths”, Computers and Operations Research, 34 (2007) 2215-2222.
Church, R. L., and Revelle, C., “The maximal covering location problem”, Papers of the Regional Science Association, 32 (1974) 101.
Cooper, L., “Solutions of generalized locational equilibrium models”, Journal of Regional Science, 7 (1967) 2-18.
Current, J.R., and Schilling, D.A., “Elimination of source A and B errors in p-median location problems”, Geographical Analysis, 19 (1987) 95-110.
Current, J.R., and Schilling, D.A., “Analysis of Errors Due to Demand Data Aggregation in the Set Covering and Maximal Covering Location Problems”, Geographical Analysis, 22 (1990) 116-126.
Daskin, M.S., Network and discrete location: models, algorithms, and applications, Wiley, New York, 1995.
Daskin, M.S., “A new approach to solving the vertex p-center problem to optimality: algorithm and computational results”, Communications of the Operations Research Society of Japan, 45 (1995) 428-436.
Daskin, M.S., “What you should know about location modeling”, Naval Research Logistics, 55 (2008) 283-294.
Davidovic, T., Ramljak, D., Selmic, M., and Teodorovic, D., “Bee colony optimization for the p-center problem”, Computers and Operations Research, 38 (2011) 1367-1376.
Drezner, Z., “The p-centre problem - heuristic and optimal algorithms”, Journal of the Operational Research Society, 35 (1984) 741-748.
Drezner, Z., “Conditional p-center problems”, Transportation Science, 23 (1989) 51-53.
Drezner, Z., “On the conditional p-median problem”, Computers and Operations Research, 22 (1995) 525-530.
Daskin, M.S., Haghani, A.E., Khand, M., and Malandraki, C., “Aggregation Effects in Maximum Covering Models”, Annals of Operations Research, 18 (1989) 115-139.
Drezner, Z., “On the conditional p-median problem”, Computers and Operations Research, 22 (1995) 525-530.
Drezner, Z., and Hamacher, H.W., Facility location: applications and theory, Springer, Berlin, 2002.
Eilon, S., Watson-Gandy, C.D.T., and Christofides, N., Distribution Management, Hafner, New York, 1971.
Eiselt, H.A., Laporte, G., and Thisse, J., “Competitive location models: A framework and bibliography”, Transportation Science, 27 (1993) 44.
Elloumi, S., Labbe, M., and Pochet, Y., “A new formulation and resolution method for the p-center problem”, INFORMS Journal of Computing, 16 (2004) 84-94.
Emir-Farinas, H., and Francis, R., “Demand point aggregation for planar covering location models”, Annals of Operations Research, 136 (2005) 175-192.
Erkut, E., and Bozkaya, B., “Analysis of aggregation errors for the p-median problem”, Computers and Operations Research, 26 (1999) 1075-1096.
Farahani, R.Z., Masoud Hekmatfar, M., Fahimnia, B., and Kazemzadeh, N., “Hierarchical facility location problem: Models, classifications, techniques, and applications”, Computers and Industrial Engineering, 68 (2014) 104-117.
Fotheringham, A. S., Densham, P. J., and Curtis, A., “The zone definition problem in location-allocation modeling”, Geographical Analysis, 27 (1995) 60-77.
Francis, R.L., McGinnis, L.F., and White, J.A., “Locational analysis”, European Journal of Operational Research, 12 (1983) 220-252.
Francis, R.L., McGinnis, L.F., and White, J.A., Facility Layout and Location: an Analytical Approach, Prentice-Hall, Englewood Cliffs, 1992.
Francis, R. L., and Lowe, T. J., “On worst-case aggregation analysis for network location problems”, Annals of Operations Research, 40 (1992) 229-246.
Francis, R.L., Lowe, T.J., and Rayco, M.B., “Row-column aggregation for rectilinear distance p-median problems”, Transportation Science, 30 (1996) 160-174.
Francis, R. L., Lowe, T.J., and Rayco, A., “Aggregation error bounds for a class of location models”, Operations Research, 48 (2000) 294.
Francis, R. L., Francis, T. J., Rayco, M. B., and Tamir, A., “Aggregation error for location models: survey and analysis”, Annals of Operations Research, 167 (2009) 171-208.
Francis, R.L., Francis, T.J., Rayco, M.B., and Tamir, A., “Exploiting self-canceling demand point aggregation error for some planar rectilinear median location problems”, Naval Research Logistics, 50 (2003) 614-637.
Francis, R.L., Lowe, T.J., and Tamir, A., “Demand Point Aggregation Analysis for a Class of Constrained Location Models: A Penalty Function Approach”, IIE Transactions, 36 (2004) 601-609.
Francis, R.L., Lowe, T.J., and Tamir, A., “Aggregation Decomposition and Aggregation Guidelines for a Class of Minimax and Covering Location Models”, Geographical Analysis, 36 (2004) 332-349.
Garcia, S., Labbe, M., and Marin, A., “Solving large p-median problem with a radius formulation”, INFORMS Journal on Computing, 23 (2010) 546-556.
GoodChild, M.F., “The aggregation problem in location-allocation”, Geographical Analysis, 11 (1979) 240-255.
Gavriliouk, E.O., “Aggregation in hub location problems”, Computers and Operations Research, 36 (2009) 3136-3142.
Hakimi, S.L., “Optimum locations of switching centers and the absolute centers and medians of a graph”, Operations Research, 12 (1964) 450-459.
Hale, T.S., and Moberg, C.R., “Location Science Research: A Review”, Annals of Operations Research, 123 (2003) 21-35.
Handler, G.Y., and Mirchandani, P.B., Location on networks: Theory and algorithms, Cambridge: MIT Press, Cambridge, (1979).
Hansen, P., Brimberg, J., Urosevic, D., and Mladenovic, N., “Solving large p-median clustering problems by primal-dual variable neighborhood search”, Data Mining and Knowledge Discovery, 19 (2009) 351-375.
Hansen, P., and Mladenovic, N., “Variable neighbourhood search for the p-median”, Location Science, 5 (1997) 207-225.
Hassin, R., and Tamir, A., “Improved complexity bounds for location problems on the real line”, Operations Research Letters, 10 (1990) 395-402.
Hillsman, E.L., and Rhoda, R., “Errors in measuring distances from populations to service centers”, Annals of Regional Science, 12 (1978) 74-88.
Hodgson, M. J., “Data surrogation error in p-median models”, Annals of Operations Research, 110 (2002) 153-165.
Hodgson, M.J., and Neuman, S., “A GIS approach to eliminating source C aggregation error in p-median models”, Location Science, 1 (1993) 155-170.
Hodgson, M.J., and Hewko, J., “Aggregation and surrogation error in the p-median model”, Annals of Operations Research, 123 (2003) 53-66.
Hodgson, M.J., Shmulevitz, F., and Krkel, M., “Aggregation error effects on the discrete-space p-median model: The case of Edmonton, Canada”, Canadian Geographer Le Gographe canadien, 41 (1997) 415-428.
Hotelling, H., “Stability in competition”, Economic Journal, 39 (1929) 41-57.
Ilhan, T., Pinar, M., “An efficient exact algorithm for the vertex p-center problem”, http: www.ie.bilkent.edu.trmustafappubs, (2001).
Irawan C. A., and Salhi S., “Solving large p-median problems by a multistage hybrid approach using demand points aggregation and variable neighbourhood search”, Journal of Global Optimization, 63 (3)(2015) 537-554.
Irawan C.A., Salhi S., and Scaparra, M.P., “An Adaptive Multiphase Approach for Large Unconditional and Conditional p-Median Problems”, European Journal of Operational Research, 237 (2014) 590-605.
Irawan C.A., and Salhi S., “Hybrid Meta-heuristics with VNS and Exact Methods: Application to Large Unconditional and Conditional Vertex p-Centre Problems”, Journal of Heuristics, (2014) under revision.
Jaeger, M., and Kariv, O., “Algorithms for finding p-centers on a weighted tree (for relatively small p)”, Network, 15 (1985) 381-389.
Kariv, O., and Hakimi, S.L., “An algorithmic approach for the vertex p-center problem. Part I: The p-centers”, SIAM Journal of Applied Mathematics, 37 (1979) 513-538.
Kariv, O., and Hakimi, S.L., “An algorithmic approach to network location problems. Part II: The p-medians”, SIAM Journal of Applied Mathematics, 37 (1979) 539-560.
Kaveh, A., and Esfahani, H. N., “Hybrid harmony search for conditional p-median problems”, International Journal of Civil Engineering, 10 (2012) 32-36.
Kaveh, A., and Nasr, H., “Solving the conditional and unconditional p-center problem with modified harmony search: A real case study”, Scientia Iranica, 18 (2011) 867-877.
Kochetov, Y., Alekseeva, E., Levanova, T., and Loresh, N., “Large neighbourhood search for the p-median problem”, Yugoslav Journal of Operations Research, 15(1)(2005) 53-63.
Limbourg, S., and Jourquin, B., “Rail-Road terminal locations: aggregation errors and best potential locations on large networks”, European Journal of Transport and Infrastructure Research, 7 (2007) 317-334.
Love, R., Moris, J., and Wesolowsky, G., Facility location: model and methods, North-Holland, Amsterdam, 1988.
Lu, C., “Robust weighted vertex p-center model considering uncertain data: An application to emergency management”, European Journal of Operational Research, 230 (2013) 113-121.
Lu, C., and Sheu, J., “Robust vertex p-center model for locating urgent relief distribution centers”, Computers and Operations Research, 40 (2013) 2128-2137.
Mansfield, E., and Wein, H.H., “A Model for the Location of a Railroad Classification Yard”, Management Science, 4 (1958) 292-313.
Miehle, W., “Link-Length Minimization in Networks”, Operations Research, 6 (1958) 232-243.
Minieka, E., “The m-center problem”, SIAM Review, 12 (1970) 138-139.
Minieka, E., “Conditional Centers and Median on a Graph”, Network, 10 (1980) 265-272.
Mirchandani, P.B., and Francis, R.L., “Discrete location theory”, New York: Wiley-Interscience, (1990).
Mirchandani, P. B., and Reilly, J. M., “’Spatial nodes’ in discrete location problems”, Annals of Operations Research, 6 (1986) 203-222.
Mladenovic, N., Brimberg, J., Hansen, P., and Moreno-Perez, J.A., “The p-median problem: A survey of metaheuristic approaches”, European Journal of Operational Research, 179 (2007) 927-939.
Mladenovic, N., Labbe, M., and Hansen, P., “Solving the p-center problem with tabu search and variable neighbourhood search”, Network, 42 (2003) 48-64.
Murray, A. T., and Gottsegen, J. M., “The influence of data aggregation on the stability of p-median location model solutions”, Geographical Analysis, 29 (1997) 200-213.
Murray, A.T., Wei, T., “A computational approach for eliminating error in the solution of the location set covering problem”, European Journal of Operational Research, 224 (2013) 52-64.
Murray, A.T., O'Kelly, M.E., Church, R.L., “Regional service coverage modeling”, Computers and Operations Research, 35 (2008) 339-355.
Nickel, S., and Puerto, J., Location Theory: a unified approach, Springer, Berlin, 2005.
Oshawa, Y., Koshizuka, T., and Kurita, O., “Errors caused by rounded data in two simple facility location problems”, Geographical Analysis, 23 (1991) 56-73.
Papadimitriou, C.H., “Worst-case and probabilistic analysis of a geometric location problem”, SIAM Journal of Computing, 10 (1981) 542-557.
Plastria, F., “On the choice of aggregation points for continuous p-median problems: a case for the gravity center”, TOP, 9 (2001) 217-242.
Plastria, F., and Van Haverbeke, L., “Aggregation without Loss of Optimality in Competitive Location Models”, Networks and Spatial Economics, 7 (2007) 3-18.
Rayco, M.B., Francis, R.L., and Tamir, A., “A p-center grid-positioning aggregation procedure”, Computers and Operations Research, 26 (1999) 1113-1124.
Resende, M.G.C. and Werneck, R., “A fast swap-based local search procedure for location problems”, Annals of Operations Research, 150 (2007) 205-230.
Qi, L., and Shen, Z.M., “Worst-case analysis of demand point aggregation for the Euclidean p-median problem”, European Journal of Operational Research, 202 (2010) 434-443.
Salhi, S., and Al-Khedhairi, A., “Integrating heuristic information into exact methods: The case of the vertex p-centre problem”, Journal of the Operational Research Society, 61 (2010) 1619-1631.
Salhi, S., and Irawan, C.A., “A quadtree-based allocation method for a class of large discrete Euclidean location problems”, Computers and Operations Research, 55 (2015) 2335.
Salhi, S., and Sari, M., “A Multi-Level Composite Heuristic for the Multi-Depot Vehicle Fleet Mix Problem”, European Journal of Operational Research, 103 (1997) 95-112.
Sankaran, J.K., “On solving large instances of the capacitated facility location problem”, European Journal of Operational Research, 178 (2007) 663-676.
Shaw, D.X., “A unified limited column generation approach for facility location problems on trees”, Annals of Operations Research, 87 (1999) 363-382.
Sridharan, R., “The capacitated plant location problem”, European Journal of Operational Research, 87 (1995) 203-213.
Taillard, E.D., “Heuristic methods for large centroid clustering problems”, Journal of Heuristics, 9 (2003) 51-73.
Tansel, B.C., Francis, R.L., and Lowe, T.J., “State of the art location on network: a survey. Part I: the p-center and p-median problems”, Management Science, 29 (1983) 482-497.
Tansel, B.C., Francis, R.L., and Lowe, T.J., “State of the art location on network: a survey. Part II: exploiting tree network structure”, Management Science, 29 (1983) 498-511.
Tansel, B.C., Francis, R.L., Lowe, T.J., and Chen, M., “Duality and distance constraints for the nonlinear p-center and covering problem on a tree network”, Operations Research, 30 (1982) 725-744.
Valinsky, D., “A Determination of the Optimum Location of Fire-Fighting Units in New York City”, Journal of the Operations Research Society of America, 3 (1955) 494-512.
Weber, A., “Über den Standort der Industrien 1”, Teil: Reine theorie des standordes, Tübingen, Germany, 1909.
Weiszfeld, E., “Sur le point pour lequel la somme des distances de n points donnés est minimum”, Tohoku Mathematical Journal, 43 (1937) 355-386.
Whitaker, R.A., “A fast algorithm for the greedy interchange for large-scale clustering and median location problems”, INFOR, 21 (1983) 95-108.
Young, H.A., “On the Optimum Location of Checking Stations”, Operations Research, 11 (1963) 721-731.
Zeng, W., Castillo, I., and Hodgson, M.J., “Aggregating Data for the Flow-Intercepting Location Model: A Geographic Information System, Optimization, and Heuristic Framework”, Geographical Analysis, 42 (2010) 301-322.
Zhao, P., and Batta, R., “Analysis of centroid aggregation for the Euclidean distance p-median problem”, European Journal of Operational Research, 113 (1999) 147-168.
Zhao, P., and Batta, R., “An aggregation approach to solving the network p-median problem with link demands”, Networks, 36 (2000) 233-241.
Downloads
Published
Issue
Section
License
Copyright (c) 2015 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
