An analysis of the impact of demand aggregation on the solution quality for facility location problems
DOI:
https://doi.org/10.58922/transportes.v31i3.2801Keywords:
Demand aggregation, Facility location, K-meansAbstract
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
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
How to Cite
Issue
Section
License
Copyright (c) 2023 Renata Akemi Marçal Imai, Claudio Barbieri da Cunha, Cauê Sauter Guazzelli
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who submit papers for publication by TRANSPORTES agree to the following terms:
- Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.
- Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.
- Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.
- Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.
