An analysis of the impact of demand aggregation on the solution quality for facility location problems

Authors

DOI:

https://doi.org/10.58922/transportes.v31i3.2801

Keywords:

Demand aggregation, Facility location, K-means

Abstract

Inspired by real-world applications, this paper studies the impact on the quality of solutions for facility location problems in which demand points are aggregated to reduce the size of the underlying mathematical formulation. Two aggregation methods are analyzed and compared: demand points aggregated based on municipal boundaries or other similar administrative boundaries as usually done in practice and using the K-means clustering algorithm. Regarding a business-to-business (B2B) distribution context, two datasets comprising the location of thousands of drugstores in Brazil were generated, and 18 different instances of the fixed cost facility location problem were derived. The results show that solutions with aggregated demand points by municipality yield a maximum 0.43% difference in the objective function value in comparison with the respective disaggregated mode, while the difference using K-means algorithm did not exceed 0.03%. We also performed an in-depth analysis of the regions where the demand points were allocated to distinct selected facilities in the aggregated and disaggregated models. It was possible to observe that in the model with aggregated demand points by municipality, differences in transportation costs are greater than using the K-means clustering algorithm as the aggregation procedure. This suggests that aggregating demand points with the K-means clustering algorithm yields both better objective function values, and selected facilities closer to demand points in the cases where the resulting assignment of demand points to the selected facilities is not the same as the results of the unaggregated model.

Downloads

Download data is not yet available.

References

Aardal, K. (1998) Capacitated facility location: separation algorithms and computational experience. Mathematical Programming, Series B, v. 81, n. 2, p. 149-175. DOI: 10.1007/BF01581103. DOI: https://doi.org/10.1007/BF01581103

Aardal, K.; Y. Pochet and L.A. Wolsey (1995) Capacitated facility location: valid inequalities and facets. Mathematics of Operations Research, v. 20, n. 3, p. 562-582. DOI: 10.1287/moor.20.3.562. DOI: https://doi.org/10.1287/moor.20.3.562

Andersson, G.; R.L. Francis; T. Normark et al. (1998) Aggregation method experimentation for large-scale network location problems. Location Science, v. 6, n. 1-4, p. 25-39. DOI: 10.1016/S0966-8349(98)00045-X. DOI: https://doi.org/10.1016/S0966-8349(98)00045-X

Barahona, F. and F.A. Chudak (2005) Near-optimal solutions to large-scale facility location problems. Discrete Optimization, v. 2, n. 1, p. 35-50. DOI: 10.1016/j.disopt.2003.03.001. DOI: https://doi.org/10.1016/j.disopt.2003.03.001

Barcelo, J.; Å.Hallefjord; E. Fernandez et al.(1990) Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing. OR-Spektrum, v. 12, n. 2, p. 79-88. DOI: 10.1007/BF01784983. DOI: https://doi.org/10.1007/BF01784983

Beasley, J.(1990) OR-Library: distributing test problems by electronic mail. The Journal of the Operational Research Society, v. 41, n. 11, p. 1069-1072. DOI: 10.1057/jors.1990.166. DOI: https://doi.org/10.1057/jors.1990.166

Brasil (2021) Resolução nº 5.949, de 13 de julho de 2021. Altera o Anexo II da Resolução ANTT nº 5.867, de 14 de janeiro de 2020, em razão do disposto nos parágrafos 1º e 2º do artigo 5º da Lei nº 13.703, de 8 de agosto de 2018. Diário Oficial da República Federativa do Brasil. Seção 1, Brasília.

Bueno, A. (2019) Preço Médio do Aluguel de Salas e Conjuntos Comerciais Acelera em Maio. Available at: <https://fipezap.zapimoveis.com.br/preco-medio-do-aluguel-de-salas-e-conjuntos-comerciais-acelera-em-maio/> (accessed 10/16/2023).

Cebecauer, M. and Ľ. Buzna (2017) A versatile adaptive aggregation framework for spatially large discrete location-allocation problems. Computers & Industrial Engineering, v. 111, p. 364-380. DOI: 10.1016/j.cie.2017.07.022. DOI: https://doi.org/10.1016/j.cie.2017.07.022

Daskin, M.S. (2013) Network and Discrete Location (2nd ed.). Hoboken: John Wiley & Sons, Ltd.

Daskin, M.S.; A.E. Haghani; M. Khanal et al. (1989) Aggregation effects in maximum covering models. Annals of Operations Research, v. 18, n. 1, p. 113-139. DOI: http://dx.doi.org/10.1007/BF02097799. DOI: https://doi.org/10.1007/BF02097799

De Armas, J.; A.A. Juan; J.M. Marquès et al. (2017) Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic. The Journal of the Operational Research Society, v. 68, n. 10, p. 1161-1176. DOI: 10.1057/s41274-016-0155-6. DOI: https://doi.org/10.1057/s41274-016-0155-6

Erkut, E. and B. Bozkaya (1999) Analysis of aggregation errors for the p-median problem. Computers & Operations Research, v. 26, n. 10-11, p. 1075-1096. DOI: 10.1016/S0305-0548(99)00021-0. DOI: https://doi.org/10.1016/S0305-0548(99)00021-0

Erlenkotter, D.A. (1978) Dual-based procedure for uncapacitated facility location. Operations Research, v. 26, n. 6, p. 992-1009. DOI: 10.1287/opre.26.6.992. DOI: https://doi.org/10.1287/opre.26.6.992

Ester, M.; H.-P. Kriegel; J. Sander et al. (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD'96) (Portland, OR). Washington, DC: AAAI Press, p. 226-231. DOI: 10.5555/3001460.3001507.

Fischetti, M.; I. Ljubić and M. Sinnl (2016) Benders decomposition without separability: a computational study for capacitated facility location problems. European Journal of Operational Research, v. 253, n. 3, p. 557-569. DOI: 10.1016/j.ejor.2016.03.002. DOI: https://doi.org/10.1016/j.ejor.2016.03.002

Francis, R.L.; T.J. Lowe; M.B. Rayco et al. (2009) Aggregation error for location models: survey and analysis. Annals of Operations Research, v. 167, n. 1, p. 171-208. DOI: 10.1007/s10479-008-0344-z. DOI: https://doi.org/10.1007/s10479-008-0344-z

Galvão, R. and L. Raggi (1989) A method for solving to optimality uncapacitated location problems. Annals of Operations Research, v. 18, n. 1, p. 225-244. DOI: 10.1007/BF02097805. DOI: https://doi.org/10.1007/BF02097805

Gao, X. (2021) A location-driven approach for warehouse location problem. The Journal of the Operational Research Society, v. 72, n. 12, p. 2735-2754. DOI: 10.1080/01605682.2020.1811790. DOI: https://doi.org/10.1080/01605682.2020.1811790

Goodchild, M.F. (1979) The aggregation problem in location-allocation. Geographical Analysis, v. 11, n. 3, p. 240-255. DOI: 10.1111/j.1538-4632.1979.tb00692.x. DOI: https://doi.org/10.1111/j.1538-4632.1979.tb00692.x

Gurobi (2022) Gurobi Optimizer Reference Manual. Available at: <https://www.gurobi.com> (acessed 10/16/2023).

Hakli, H. and Z. Ortacay (2019) An improved scatter search algorithm for the uncapacitated facility location problem. Computers & Industrial Engineering, v. 135, p. 855-867. DOI: 10.1016/j.cie.2019.06.060. DOI: https://doi.org/10.1016/j.cie.2019.06.060

Han, J.; M. Kamber and J. Pei (2012) Data Mining. Boston: Morgan Kaufmann.

Hansen, P.; J. Brimberg; D. Urošević et al. (2007) Primal-dual variable neighborhood search for the simple plant-location problem. INFORMS Journal on Computing, v. 19, n. 4, p. 552-564. DOI: 10.1287/ijoc.1060.0196. DOI: https://doi.org/10.1287/ijoc.1060.0196

Hillsman, E.L. and R. Rhoda (1978) Errors in measuring distances from populations to service centers. The Annals of Regional Science, v. 12, n. 3, p. 74-88. DOI: 10.1007/BF01286124. DOI: https://doi.org/10.1007/BF01286124

Hodgson, M.J.; F. Shmulevitz and M. Körkel (1997) Aggregation error effects on the discrete-space p-median model: the case of Edmonton, Canada. Canadian Geographer, v. 41, n. 4, p. 415-428. DOI: 10.1111/j.1541-0064.1997.tb01324.x. DOI: https://doi.org/10.1111/j.1541-0064.1997.tb01324.x

Irawan, C.A. and S. Salhi (2015) Aggregation and non aggregation techniques for large facility location problems-a survey. Yugoslav Journal of Operations Research, v. 25, n. 3, p. 313-341. DOI: 10.2298/YJOR140909001I. DOI: https://doi.org/10.2298/YJOR140909001I

Irawan, C.A.; S. Salhi; M. Luis et al.(2017) The continuous single source location problem with capacity and zone-dependent fixed cost: models and solution approaches. European Journal of Operational Research, v. 263, n. 1, p. 94-107. DOI: 10.1016/j.ejor.2017.04.004. DOI: https://doi.org/10.1016/j.ejor.2017.04.004

Jacobs-Crisioni, C.; P. Rietveld and E. Koomen (2014) The impact of spatial aggregation on urban development analyses. Applied Geography, v. 47, p. 46-56. DOI: 10.1016/j.apgeog.2013.11.014. DOI: https://doi.org/10.1016/j.apgeog.2013.11.014

Janjevic, M.; M. Winkenbach and D. Merchán (2019) Integrating collection-and-delivery points in the strategic design of urban last-mile e-commerce distribution networks. Transportation Research Part E: Logistics and Transportation Review, v. 131, p. 37-67. DOI: 10.1016/j.tre.2019.09.001. DOI: https://doi.org/10.1016/j.tre.2019.09.001

Khumawala, B. (1972) An efficient branch and bound algorithm for the warehouse location problem. Management Science, v. 18, n. 12, p. B-635-B-749. DOI: 10.1287/mnsc.18.12.B718. DOI: https://doi.org/10.1287/mnsc.18.12.B718

Kratica, J.; D. Tošic; V. Filipović et al. (2001) Solving the simple plant location problem by genetic algorithm. Operations Research, v. 35, n. 1, p. 127-142. DOI: 10.1051/ro:2001107. DOI: https://doi.org/10.1051/ro:2001107

Laporte, G.; S. Nickel and F. Saldanha-da-Gama (2019) Location Science. Cham: Springer. DOI: 10.1007/978-3-030-32177-2. DOI: https://doi.org/10.1007/978-3-030-32177-2

Levin, Y. and A. Ben-Israel (2004) A heuristic method for large-scale multi-facility location problems. Computers & Operations Research, v. 31, n. 2, p. 257-272. DOI: 10.1016/S0305-0548(02)00191-0. DOI: https://doi.org/10.1016/S0305-0548(02)00191-0

MacQueen, J. (1967) Some methods for classification and analysis of multivariate observations. In Le Cam, L.M. and J. Neyman (eds.) Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability (v. 1). Oakland: University of California Press, p. 281-297.

Melo, M.; S. Nickel and F. Saldanha-da-Gama (2009) Facility location and supply chain management – a review. European Journal of Operational Research, v. 196, n. 2, p. 401-412. DOI: 10.1016/j.ejor.2008.05.007. DOI: https://doi.org/10.1016/j.ejor.2008.05.007

O’Kelly, M.E. (1992) A clustering approach to the planar hub location problem. Annals of Operations Research, v. 40, n. 1, p. 339-353. DOI: 10.1007/BF02060486. DOI: https://doi.org/10.1007/BF02060486

Paul, J.A. and L. Macdonald (2016) Location and capacity allocations decisions to mitigate the impacts of unexpected disasters. European Journal of Operational Research, v. 251, n. 1, p. 252-263. DOI: 10.1016/j.ejor.2015.10.028. DOI: https://doi.org/10.1016/j.ejor.2015.10.028

Rahmah, N. and I.S. Sitanggang (2016) Determination of optimal Epsilon (Eps) value on DBSCAN algorithm to clustering data on peatland hotspots in Sumatra. IOP Conference Series: Earth and Environmental Science, v. 31, n. 1, p. 012012. DOI: 10.1088/1755-1315/31/1/012012. DOI: https://doi.org/10.1088/1755-1315/31/1/012012

ReVelle, C.S.; H.A. Eiselt and M.S. Daskin (2008) A bibliography for some fundamental problem categories in discrete location science. European Journal of Operational Research, v. 184, n. 3, p. 817-848. DOI: 10.1016/j.ejor.2006.12.044. DOI: https://doi.org/10.1016/j.ejor.2006.12.044

Rodero, R. (2018) Gostaria de Saber Qual o Tamanho Mínimo de Uma Drogaria por Partes. Available at: <https://guiadafarmacia.com.br/perguntas/qual-o-tamanho-minimo-de-uma-drogaria-por-partes/> (accessed 10/16/2023).

Saldanha-da-Gama, F. (2022) Facility location in logistics and transportation: an enduring relationship. Transportation Research Part E: Logistics and Transportation Review, v. 166, p. 102903. DOI: 10.1016/j.tre.2022.102903. DOI: https://doi.org/10.1016/j.tre.2022.102903

Sankaran, J.K. (2007) On solving large instances of the capacitated facility location problem. European Journal of Operational Research, v. 178, n. 3, p. 663-676. DOI: 10.1016/j.ejor.2006.01.035. DOI: https://doi.org/10.1016/j.ejor.2006.01.035

Tong, D. and R.L. Church (2012) Aggregation in continuous space coverage modeling. International Journal of Geographical Information Science, v. 26, n. 5, p. 795-816. DOI: 10.1080/13658816.2011.615748. DOI: https://doi.org/10.1080/13658816.2011.615748

Van Roy, T.A. (1986) Cross decomposition algorithm for capacitated facility location. Operations Research, v. 34, n. 1, p. 145-163. DOI: 10.1287/opre.34.1.145. DOI: https://doi.org/10.1287/opre.34.1.145

Verter, V. (2011) Uncapacitated and capacitated facility location problems. In Eiselt, H.A. and V. Marianov (eds.) Foundations of Location Analysis. New York: Springer, p. 25-37. DOI: 10.1007/978-1-4419-7572-0_2. DOI: https://doi.org/10.1007/978-1-4419-7572-0_2

Wolsey, L.A. (1998) Integer Programming. New York: John Wiley & Sons, Ltd.

Zhao, P. and R. Batta (1999) Analysis of centroid aggregation for the Euclidean distance p-median problem. European Journal of Operational Research, v. 113, n. 1, p. 147-168. DOI: 10.1016/S0377-2217(98)00010-1. DOI: https://doi.org/10.1016/S0377-2217(98)00010-1

Downloads

Published

2023-12-20

How to Cite

Imai, R. A. M., Barbieri da Cunha, C. ., & Sauter Guazzelli, C. (2023). An analysis of the impact of demand aggregation on the solution quality for facility location problems. TRANSPORTES, 31(3), e2801. https://doi.org/10.58922/transportes.v31i3.2801

Issue

Section

Artigos