×

zbMATH — the first resource for mathematics

Aggregation error for location models: Survey and analysis. (English) Zbl 1173.90005
When the number of demand points in location models gets large, aggregation approaches are a popular tool to reduce the computational burden. However, there is a trade-off between model reduction on the one hand and solution accuracy on the other hand. This paper gives an extensive review and analysis of aggregation approaches in location modelling, emphasizing in particular different measures to assess the error induced by aggregation.
After reviewing existing error measures for aggregation approaches, a detailed literature review on demand point aggregation is given. The findings are classified with respect to the location model used (median problems, center and cover problems, and others) and summarized in two informative tables. A concluding list of the main findings gives interesting insights and recognizes common problems and open questions. Special attention is given to ADP-DP distances (i.e., the distances between the aggregated demand points and the demand points) in the context of comparing error measures, to subadditive and nondecreasing cost functions, to constraint aggregation (for example in covering location models) and to the relation between big aggregation problems and small aggregation problems.

MSC:
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agarwal, P. K., & Procopiuc, C. M. (2002). Exact and approximation algorithms for clustering. Algorithmica, 33, 201–226. · Zbl 0994.68178
[2] Agarwal, P. K., & Varadarajan, K. R. (1999). Approximation algorithms for bipartite and nonbipartite matchings in the plane, In 10th ACM-SIAM symposium on discrete algorithms (SODA), pp. 805–814. · Zbl 0929.65036
[3] Agarwal, P. K., Efrat, A., & Sharir, M. (1999). Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM Journal on Computing, 29, 912–953. · Zbl 0949.68179
[4] Agarwal, P. K., Procopiuc, C. M., & Varadarajan, K. R. (2002). Approximation algorithms for k-line center, In Proceedings 10-th annual European symposium on algorithms (ESA 2002), pp. 54–63. · Zbl 1019.68132
[5] Agarwal, P. K., Har-Peled, S., & Varadarajan, K. R. (2005). Geometric approximation via coresets. In J. E. Goodman, J. Pach, & E. Welzl (Eds.), Combinatorial and computational geometry. New York: Cambridge University Press. · Zbl 1123.68141
[6] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: theory, algorithms, and applications. Englewood Cliffs: Prentice–Hall (Exercise 12.23 on page 505 describes an O(n2.5 log n) algorithm for the bottleneck assignment problem.) · Zbl 1201.90001
[7] Andersson, G., Francis, R. L., Normark, T., & Rayco, M. B. (1998). Aggregation method experimentation for large-scale network location problems. Location Science, 6, 25–39.
[8] Bach, L. (1981). The problem of aggregation and distance for analysis of accessibility and access opportunity in location-allocation models. Environment and Planning A, 13, 955–978.
[9] Ballou, R. H. (1994). Measuring transport costing error in customer aggregation for facility location. Transportation Journal, 33, 49–54.
[10] Bender, T., Hennes, H., Kalcsics, J., Melo, T., & Nickel, S. (2001). Location software and interface with GIS and supply chain management. In Z. Drezner & H. Hamacher (Eds.), Facility location: applications and theory. Berlin: Springer. · Zbl 1027.90052
[11] Bowerman, R. L., Calamai, P. H., & Hall, B. (1999). The demand partitioning method for reducing aggregation errors in p-median problems. Computers and Operations Research, 26, 1097–1111. · Zbl 0940.90053
[12] Carrizosa, E., Hamacher, H. W., Nickel, S., & Klein, R. (2000). Solving nonconvex planar location problems by finite dominating sets. Journal of Global Optimization, 18, 195–210. · Zbl 1028.90021
[13] Casillas, P. A. (1987). Data aggregation and the p-median problem in continuous space. In A. Ghosh & G. Rushton (Eds.), Spatial analysis and location-allocation models (pp. 227–244). New York: Van Nostrand Reinhold Publishers.
[14] Chelst, K. R., Schultz, J. P., & Sanghvi, N. (1988). Issues and decision aids for designing branch networks. Journal of Retail Banking X, 2, 5–17.
[15] Cooper, L. (1967). Solutions of generalized location equilibrium models. Journal of Regional Science, 1, 334–336.
[16] Cornuejols, G., Fisher, M. L., & Nemhauser, G. L. (1977). Location of bank accounts to optimize float: an analytical study of exact and approximate algorithms. Management Science, 23, 789–810. · Zbl 0361.90034
[17] Current, J. R., & Schilling, D. A. (1987). Elimination of source A and B errors in p-median problems. Geographical Analysis, 19, 95–110.
[18] Current, J. R., & Schilling, D. A. (1990). Analysis of errors due to demand data aggregation in the set covering and maximal covering location problems. Geographical Analysis, 22, 116–126.
[19] Daskin, M. S. (1995). Network and discrete location: models, algorithms, and applications. New York: Wiley. · Zbl 0870.90076
[20] Daskin, M. S., Haghani, A. E., Khanal, M., & Malandraki, C. (1989). Aggregation effects in maximum covering models. Annals of Operations Research, 18, 115–139. · Zbl 0707.90067
[21] Dekle, J., Lavieri, M., Martin, E., Emir-Farinas, H., & Francis, R. L. (2005). A Florida county locates disaster recovery centers. Interfaces, 35(2), 133–139.
[22] Domich, P. D., Hoffman, K. L., Jackson, R. H. F., & McClain, M. A. (1991). Locating tax facilities: a graphics-based microcomputer optimization model. Management Science, 37, 960–979.
[23] Drezner, Z. (Ed.). (1995a). Facility location: a survey of applications and methods. Berlin: Springer. · Zbl 0917.90224
[24] Drezner, Z. (1995b). Replacing discrete demand with continuous demand. In Z. Drezner (Ed.), Facility location: a survey of applications and methods. Berlin: Springer.
[25] Drezner, T., & Drezner, Z. (1997). Replacing discrete demand with continuous demand in a competitive facility location problem. Naval Research Logistics, 44, 81–95. · Zbl 0882.90083
[26] Drezner, Z., & Hamacher, H. W. (Eds.). (2002). Facility location: theory and algorithms. Berlin: Springer. · Zbl 0988.00044
[27] Efrat, A., Itai, A., & Katz, M. J. (2001). Geometry helps in bottleneck matching and related problems. Algorithmica, 31, 1–28. · Zbl 0980.68101
[28] Emir-Farinas, H. (2002). Aggregation of demand points for the planar covering location problem. Ph. D. Dissertation, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL. · Zbl 1114.90057
[29] Emir-Farinas, H., & Francis, R. L. (2005). Demand point aggregation for planar covering location models. Annals of Operations Research, 136, 175–192. · Zbl 1114.90057
[30] Erkut, E., & Bozkaya, B. (1999). Analysis of aggregation errors for the p-median problem. Computers and Operations Research, 26, 1075–1096. · Zbl 0940.90055
[31] Erkut, E., & Neuman, S. (1989). Analytical models for locating undesirable facilities. European Journal of Operational Research, 40, 275–291. · Zbl 0668.90025
[32] Ernst, A., Hamacher, H. W., Jiang, H. W., Krishnamorthy, M., & Woeginger, G. (2002a). Uncapacitated single and multiple allocation p-hub center problems. Report CSIRO, Melbourne, Australia. · Zbl 1158.90372
[33] Ernst, A., Hamacher, H. W., Jiang, H. W., Krishnamorthy, M., & Woeginger, G. (2002b). Heuristic algorithms for the uncapacitated hub center single allocation problem. Report CSIRO, Melbourne, Australia.
[34] Fortney, J., Rost, K., & Warren, J. (2000). Comparing alternative methods of measuring geographic access to health services. Health Services and Outcomes Research Methodology, 1, 173–184.
[35] Fotheringham, A. S., Densham, P., & Curtis, A. (1995). The zone definition problem in location-allocation modeling. Geographical Analysis, 27, 60–77.
[36] Francis, R. L., & Lowe, T. J. (1992). On worst-case aggregation analysis for network location problems. Annals of Operations Research, 40, 229–246. · Zbl 0787.90046
[37] Francis, R. L., & Rayco, M. B. (1996). Asymptotically optimal aggregation for some unweighted p-center problems with rectilinear distances. Studies in Locational Analysis, 10, 25–36. · Zbl 0898.90084
[38] Francis, R. L., & White, J. A. (1974). Facility layout and location: an analytical approach. Englewood Cliffs: Prentice–Hall (Homework problem 7.25, p. 324).
[39] Francis, R. L., McGinnis, L. F., & White, J. A. (1992). Facility layout and location: an analytical approach (2nd ed.). Englewood Cliffs: Prentice–Hall.
[40] Francis, R. L., Lowe, T. J., & Rayco, M. B. (1996). Row-column aggregation for rectilinear p-median problems. Transportation Science, 30, 160–174. · Zbl 0865.90087
[41] Francis, R. L., Lowe, T. J., Rushton, G., & Rayco, M. B. (1999). A synthesis of aggregation methods for multi-facility location problems: strategies for containing error. Geographical Analysis, 31, 67–87.
[42] Francis, R. L., Lowe, T. J., & Tamir, A. (2000). On aggregation error bounds for a class of location models. Operations Research, 48, 294–307. · Zbl 1106.90355
[43] Francis, R. L., Lowe, T. J., & Tamir, A. (2002a). Worst-case incremental analysis for a class of p-facility location problems. Networks, 39, 139–143. · Zbl 1012.90027
[44] Francis, R. L., Lowe, T. J., & Tamir, A. (2002b). Demand point aggregation of location models. In Z. Drezner & H. Hamacher (Eds.), Facility location: applications and theory. Berlin: Springer. · Zbl 1018.90023
[45] Francis, R. L., Lowe, T. J., Rayco, M. B., & Tamir, A. (2003). Exploiting self-canceling demand point aggregation error for some planar rectilinear median problems. Naval Research Logistics, 50, 614–637. · Zbl 1044.90044
[46] Francis, R. L., Lowe, T. J., & Tamir, A. (2004a). Demand point aggregation analysis for a class of constrained location models: a penalty function approach. IIE Transactions, 36, 601–609.
[47] Francis, R. L., Lowe, T. J., Tamir, A., & Emir-Farinas, H. (2004b). Aggregation decomposition and aggregation guidelines for a class of minimax and covering location models. Geographical Analysis, 36, 332–349. · Zbl 1065.90053
[48] Francis, R. L., Lowe, T. J., Tamir, A., & Emir-Farinas, H. (2004c). A framework for demand point and solution space aggregation analysis for location models. European Journal of Operational Research, 159, 574–585. · Zbl 1065.90053
[49] Frieze, A. M. (1980). Probabilistic analysis of some Euclidean clustering problems. Discrete Applied Mathematics, 10, 295–309. · Zbl 0449.90073
[50] Gavriliouk, E. O. (2003). Aggregation in hub location models. M. Sc. Thesis, Department of Mathematics, Clemson University, Clemson, SC. · Zbl 1176.90355
[51] Geoffrion, A. (1977). Objective function approximations in mathematical programming. Mathematical Programming, 13, 23–37. · Zbl 0356.90062
[52] Goldberg, R. (1976). Methods of real analysis (2nd ed.). New York: Wiley. · Zbl 0348.26001
[53] Goodchild, M. F. (1979). The aggregation problem in location-allocation. Geographical Analysis, 11, 240–255.
[54] Hakimi, S. L. (1965). Optimum location of switching centers and the absolute centers and medians of a graph. Operations Research, 12, 450–459. · Zbl 0123.00305
[55] Hakimi, S. L., Labbe’, M., & Schmeichel, E. (1992). The Voronoi partitioning of a network and its implications in network location theory. ORSA Journal on Computing, 4, 412–417. · Zbl 0758.90052
[56] Hale, T., & Hale, L. (2000). An aggregation technique for location problems with one-dimensional forbidden regions. International Journal of Industrial Engineering, 7, 133–139.
[57] Hale, T., & Moberg, C. (2003). Location science research: a review. Annals of Operations Research, 123, 21–35. · Zbl 1137.90598
[58] Hale, T., Wysk, R., & Smith, D. (2000). A gross aggregation technique for the p-median location problem. International Journal of Operations and Quantitative Management, 6, 129–135.
[59] Handler, G. Y., & Mirchandani, P. B. (1979). Location on networks: theory and algorithms. Cambridge: MIT Press. · Zbl 0533.90026
[60] Hansen, P., Jaumard, B., & Tuy, H. (1995). Global optimization in location. In Z. Drezner (Ed.), Facility location: a survey of applications and methods. Berlin: Springer.
[61] Har-Peled, S. (2004a). Clustering motion. Discrete Computational Geometry, 31, 545–565. · Zbl 1094.68103
[62] Har-Peled, S. (2004b). No coreset, no cry. In Proceedings 24-th conf. found. soft. tech. theoretical computer science, pp. 324–335. · Zbl 1117.68525
[63] Har-Peled, S., & Kushal, A. (2007). Smaller coresets for k-median and k-means clustering. Discrete Computational Geometry, 37, 3–19. · Zbl 1106.68112
[64] Har-Peled, S., & Mazumdar, S. (2004). Coresets for k-means and k-median clustering and their applications. In Proceedings 36-th annual ACM symposium on theory of computing, pp. 291–300. · Zbl 1192.68904
[65] Hassin, R., & Tamir, A. (1991). Improved complexity bounds for location problems on the real line. O.R. Letters, 10, 395–402. · Zbl 0742.90050
[66] Hillsman, E. L., & Rhoda, R. (1978). Errors in measuring distances from populations to service centers. Annals of Regional Science, 12, 74–88.
[67] Hodgson, M. J. (2002). Data surrogation error in p-median models. Annals of Operations Research, 110, 153–165. · Zbl 1013.90077
[68] Hodgson, M. J., & Hewko, J. (2003). Aggregation and surrogation error in the p-median model. Annals of Operations Research, 123, 53–66. · Zbl 1039.90028
[69] Hodgson, M. J., & Neuman, S. (1993). A GIS approach to eliminating source C aggregation error in p-median models. Location Science, 1, 155–170. · Zbl 0915.90174
[70] Hodgson, M. J., Shmulevitz, F., & Körkel, M. (1997). Aggregation error effects on the discrete-space p-median model: the case of Edmonton, Canada. The Canadian Geographer, 41, 415–428.
[71] Hooker, J. N., Garfinkel, R. S., & Chen, C. K. (1991). Finite dominating sets for network location problems. Operations Research, 39, 100–118. · Zbl 0744.90049
[72] Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems: part 1, the p-centers; part 2, the p-medians. SIAM Journal of Applied Mathematics, 37, 513–560. · Zbl 0432.90074
[73] Kolen, A., & Tamir, A. (1990). Covering problems. In P. B. Mirchandani & R. L. Francis (Eds.), Discrete location theory (pp. 263–304). New York: Wiley–Interscience. · Zbl 0747.90058
[74] Love, R., Morris, J., & Wesolowsky, G. (1988). Facility location: models and methods. Amsterdam: North-Holland. · Zbl 0685.90036
[75] Marchetti-Spaccamela, A., & Talamo, M. (1983). Probabilistic analysis of two Euclidean location problems. R.A.I.R.O. Informatique Theorique/Theoretical Informatics, 17, 387–395. · Zbl 0523.68032
[76] Megiddo, N., & Supowit, K. J. (1984). On the complexity of some common geometric location problems. SIAM Journal on Computing, 13, 182–196. · Zbl 0534.68032
[77] Mirchandani, P. B., & Francis, R. L. (Eds.). (1990). Discrete location theory. New York: Wiley–Interscience. · Zbl 0718.00021
[78] Mirchandani, P. B., & Reilly, J. M. (1986). Spatial nodes in discrete location problems. Annals of Operations Research, 10, 329–350.
[79] Murray, A. T., & Gottsegen, J. M. (1997). The influence of data aggregation on the stability of p-median location model solutions. Geographical Analysis, 29, 200–213.
[80] Nickel, S., & Puerto, J. (1999). A unified approach to network location problems. Networks, 34, 283–290. · Zbl 0948.90086
[81] Nickel, S., & Puerto, J. (2005). Location theory: a unified approach. Berlin: Springer. · Zbl 1229.90001
[82] Ohsawa, Y., Koshizuka, T., & Kurita, O. (1991). Errors caused by rounded data in two simple facility location problems. Geographical Analysis, 23, 56–73.
[83] Pardalos, P. M., & Resende, M. (Eds.). (2002). Handbook of applied optimization. Oxford: Oxford University Press. · Zbl 0996.90001
[84] Plastria, F. (1992). GBSSS: the generalized big square small square method for planar single-facility location. European Journal of Operational Research, 62, 163–174. · Zbl 0760.90067
[85] Plastria, F. (2000). New error bounds in continuous minisum location for aggregation at the gravity centre. Studies in Locational Analysis, 14, 101–119. · Zbl 1090.90536
[86] Plastria, F. (2001). On the choice of aggregation points for continuous p-median problems: a case for the gravity center. TOP, 9, 217–242. · Zbl 0994.90092
[87] Puerto, J., & Fernandez, F. R. (2000). Geometrical properties of the symmetrical single facility location problem. Journal of Nonlinear Convex Analysis, 1, 321–342. · Zbl 0974.90009
[88] Rayco, M. B. (1996). Algorithmic approaches to demand point aggregation for location models. Ph. D. Dissertation, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL.
[89] Rayco, M. B., Francis, R. L., & Lowe, T. J. (1997). Error-bound driven demand point aggregation for the rectilinear distance p-center model. Location Science, 4, 213–235. · Zbl 0929.90051
[90] Rayco, M. B., Francis, R. L., & Tamir, A. (1999). A p-center grid-positioning aggregation procedure. Computers and Operations Research, 26, 1113–1124. · Zbl 0940.90064
[91] Reeves, C. (1993). Modern heuristic techniques for combinatorial problems. Oxford: Blackwell Scientific Press. · Zbl 0942.90500
[92] Resende, M. G. C., & de Sousa, J. P. (Eds.). (2004). Metaheuristics: computer decision-making. Boston: Kluwer Academic. · Zbl 1030.68079
[93] Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press. · Zbl 0193.18401
[94] Rodriguez-Bachiller, A. (1983). Errors in the measurement of spatial distances between discrete regions. Environment and Planning A, 15, 781–799.
[95] Rodriguez-Chia, A. M., Nickel, S., Puerto, J., & Fernandez, F. R. (2000). A flexible approach to location problems. Mathematical Methods of Operations Research, 51, 69–89. · Zbl 1031.90009
[96] Rogers, D. F., Plante, R. D., Wong, R. T., & Evans, J. R. (1991). Aggregation and disaggregation techniques and methodology in optimization. Operations Research, 39, 553–582. · Zbl 0729.90738
[97] Romero-Morales, D., Carrizosa, E., & Conde, E. (1997). Semi-obnoxious location models: a global optimization approach. European Journal of Operational Research, 102, 295–301. · Zbl 0955.90054
[98] Rosenbaum, R. A. (1950). Sub-additive functions. Duke Mathematical Journal, 17, 227–247. · Zbl 0038.06603
[99] Rushton, G. (1989). Applications of location models. Annals of Operations Research, 18, 25–42.
[100] Sheffi, Y. (1985). Urban transportation networks: equilibrium analysis with mathematical programming models (pp. 14–16). Englewood Cliffs: Prentice–Hall.
[101] Shier, D. R., & Dearing, P. M. (1983). Optimal locations for a class of nonlinear, single-facility location problems on a network. Operations Research, 31, 292–303. · Zbl 0507.90024
[102] Varadarajan, K. R. (1998). A divide and conquer algorithm for min-cost perfect matching in the plane. In Proceedings 38-th annual IEEE symposium on foundations of computer sciences, pp. 320–331.
[103] Webber, M. J. (1980). A theoretical analysis of aggregation in spatial interaction models. Geographical Analysis, 12, 129–141.
[104] Zemel, E. (1985). Probabilistic analysis of geometric location problems. SIAM J. Algebraic and Discrete Methods, 6, 189–200. · Zbl 0569.90022
[105] Zhao, P. (1996). Analysis of aggregation effects in location problems. Ph. D. Dissertation, Dept. of Industrial Engineering, University at Buffalo (SUNY), Buffalo, NY.
[106] Zhao, P., & Batta, R. (1999). Analysis of centroid aggregation for the Euclidean distance p-median problem. European Journal of Operational Research, 113, 147–168. · Zbl 0933.90044
[107] Zhao, P., & Batta, R. (2000). An aggregation approach to solving the network p-median problem with link demands. Networks, 36, 233–241. · Zbl 0985.90017
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.