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:
- The authors retain the copyright and grant Transportes the right of first publication of the manuscript, without any financial charge, and waive any other remuneration for its publication by ANPET.
- Upon publication by Transportes, the manuscript is automatically licensed under the Creative Commons License CC BY 4.0 license. This license permits the work to be shared with proper attribution to the authors and its original publication in this journal.
- Authors are authorized to enter into additional separate contracts for the non-exclusive distribution of the version of the manuscript published in this journal (e.g., publishing in an institutional repository or as a book chapter), with recognition of the initial publication in this journal, provided that such a contract does not imply an endorsement of the content of the manuscript or the new medium by ANPET.
- Authors are permitted and encouraged to publish and distribute their work online (e.g., in institutional repositories or on their personal websites) after the editorial process is complete. As Transportes provides open access to all published issues, authors are encouraged to use links to the DOI of their article in these cases.
- Authors guarantee that they have obtained the necessary authorization from their employers for the transfer of rights under this agreement, if these employers hold any copyright over the manuscript. Additionally, authors assume all responsibility for any copyright infringements by these employers, releasing ANPET and Transportes from any responsibility in this regard.
- Authors assume full responsibility for the content of the manuscript, including the necessary and appropriate authorizations for the disclosure of collected data and obtained results, releasing ANPET and Transportes from any responsibility in this regard.
