A sim-learnheuristic algorithm for solving a capacitated dispersion problem under stochastic and non-static conditions

Elnaz Ghorbani; Juan F. Gomez; Javier Panadero; Angel A. Juan; Elnaz Ghorbani; Juan F. Gomez; Javier Panadero; Angel A. Juan

doi:10.3934/math.20241180

AIMS Mathematics

2024, Volume 9, Issue 9: 24247-24270. doi: 10.3934/math.20241180

Previous Article Next Article

Research article Special Issues

A sim-learnheuristic algorithm for solving a capacitated dispersion problem under stochastic and non-static conditions

1.
Department of Computer Science, Universitat Oberta de Catalunya, 08018 Barcelona, Spain
2.
Research Center on Production Management and Engineering, Universitat Politècnica de València, 03801 Alcoy, Spain
3.
Department of Computer Architecture and Operating Systems, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spain

Received: 11 June 2024 Revised: 30 July 2024 Accepted: 05 August 2024 Published: 16 August 2024
MSC : 68T20, 90-08, 90-10, 90Bxx, 90B36

A fundamental assumption in addressing real-world problems is acknowledging the presence of uncertainty and dynamism. Dismissing these factors can lead to the formulation of an optimal solution for an entirely different problem. This paper presents a novel variant of the capacitated dispersion problem (CDP) referred to as the stochastic and non-static CDP. The main objective of this problem is to strategically position facilities to achieve maximum dispersion while meeting the capacity demand constraint. The proposed approach combines stochastic and non-static elements, introducing a new paradigm to address the problem. This innovation allows us to consider more realistic and flexible environments. To solve this challenging problem, a novel sim-learnheuristic algorithm is proposed. This algorithm combines a biased-randomized metaheuristic (optimization component) with a simulation component (to model the uncertainty) and a machine learning component (to model non-static behavior). The non-static part works by using black box and white box mechanisms to learn the uncertainty with some related facilities' variables. Based on an extended set of traditional benchmarks for the CDP, a series of computational experiments were carried out. The results demonstrate the effectiveness of the proposed sim-learnheuristic approach for solving the CDP under non-static and stochastic scenarios.
- capacitated dispersion problem,
- sim-learnheuristic,
- machine learning,
- simulation
Citation: Elnaz Ghorbani, Juan F. Gomez, Javier Panadero, Angel A. Juan. A sim-learnheuristic algorithm for solving a capacitated dispersion problem under stochastic and non-static conditions[J]. AIMS Mathematics, 2024, 9(9): 24247-24270. doi: 10.3934/math.20241180

Related Papers:

Abstract

A fundamental assumption in addressing real-world problems is acknowledging the presence of uncertainty and dynamism. Dismissing these factors can lead to the formulation of an optimal solution for an entirely different problem. This paper presents a novel variant of the capacitated dispersion problem (CDP) referred to as the stochastic and non-static CDP. The main objective of this problem is to strategically position facilities to achieve maximum dispersion while meeting the capacity demand constraint. The proposed approach combines stochastic and non-static elements, introducing a new paradigm to address the problem. This innovation allows us to consider more realistic and flexible environments. To solve this challenging problem, a novel sim-learnheuristic algorithm is proposed. This algorithm combines a biased-randomized metaheuristic (optimization component) with a simulation component (to model the uncertainty) and a machine learning component (to model non-static behavior). The non-static part works by using black box and white box mechanisms to learn the uncertainty with some related facilities' variables. Based on an extended set of traditional benchmarks for the CDP, a series of computational experiments were carried out. The results demonstrate the effectiveness of the proposed sim-learnheuristic approach for solving the CDP under non-static and stochastic scenarios.

References

[1]	A. Ala, M. Deveci, E. A. Bani, A. H. Sadeghi, Dynamic capacitated facility location problem in mobile renewable energy charging stations under sustainability consideration, Sustain. Comput. Infor., 41 (2024), 100954. https://doi.org/10.1016/j.suscom.2023.100954 doi: 10.1016/j.suscom.2023.100954
[2]	N. Aydin, A. Murat, B. S. Mordukhovich, Sample intelligence-based progressive hedging algorithms for the stochastic capacitated reliable facility location problem, Artif. Intell. Rev., 57 (2024), 135.
[3]	M. Bieniek, A note on the facility location problem with stochastic demands, Omega, 55 (2015), 53–60. https://doi.org/10.1016/j.omega.2015.02.006 doi: 10.1016/j.omega.2015.02.006
[4]	M. Chica, A. A. Juan, C. Bayliss, O. Cordón, W. D. Kelton, Why simheuristics? benefits, limitations, and best practices when combining metaheuristics with simulation, SORT-Stat. Oper. Res. T., 44 (2020), 311–334.
[5]	B. R. Cobb, R. Rumí, A. Salmerón, Inventory management with log-normal demand per unit time, Comput. Oper. Res., 40 (2013), 1842–1851. https://doi.org/10.1016/j.cor.2013.01.017 doi: 10.1016/j.cor.2013.01.017
[6]	P. B. de Oliveira, R. S. de Camargo, G. de Miranda Júnior, A. X. Martins, A computational study of a decomposition approach for the dynamic two-level uncapacitated facility location problem with single and multiple allocation, Comput. Ind. Eng., 151 (2021), 106964.
[7]	A. Duarte, R. Marti, Tabu search and grasp for the maximum diversity problem, Eur. J. Oper. Res., 178 (2007), 71–84. https://doi.org/10.1016/j.ejor.2006.01.021 doi: 10.1016/j.ejor.2006.01.021
[8]	E. Ghorbani, T. Fluechter, L. Calvet, M. Ammouriova, J. Panadero, A. A. Juan, Optimizing energy consumption in smart cities' mobility: Electric vehicles, algorithms, and collaborative economy, Energies, 16 (2023).
[9]	F. Glover, K. Ching-Chung, K. S. Dhir, A discrete optimization model for preserving biological diversity, Appl. Math. Model., 19 (1995), 696–701. https://doi.org/10.1016/0307-904X(95)00083-V doi: 10.1016/0307-904X(95)00083-V
[10]	F. Glover, C. C. Kuo, K. Dhir, Heuristic algorithms for the maximum diversity problem, J. Inform. Optim. Sci., 1998, 19. https://doi.org/10.1080/02522667.1998.10699366
[11]	J. F. Gomez, A. Martínez-Gavara, J. Panadero, A. A. Juan, R. Martí, A forward-backward simheuristic for the stochastic capacitated dispersion problem, Mathematics, 12 (2024), 909. https://doi.org/10.3390/math12060909 doi: 10.3390/math12060909
[12]	J. F. Gomez, J. Panadero, R. D. Tordecilla, J. Castaneda, A. A. Juan, A multi-start biased-randomized algorithm for the capacitated dispersion problem, Mathematics, 10 (2022).
[13]	J. F. Gomez, A. R. Uguina, J. Panadero, A. A. Juan, A learnheuristic algorithm for the capacitated dispersion problem under dynamic conditions, Algorithms, 16 (2023), 532. https://doi.org/10.3390/a16120532 doi: 10.3390/a16120532
[14]	A. Grasas, A. A. Juan, J. Faulin, J. de Armas, H. Ramalhinho, Biased randomization of heuristics using skewed probability distributions: A survey and some applications, Comput. Ind. Eng., 110 (2017), 216–228. https://doi.org/10.1016/j.cie.2017.06.019 doi: 10.1016/j.cie.2017.06.019
[15]	S. D. Jena, J. F. Cordeau, B. Gendron, Solving a dynamic facility location problem with partial closing and reopening, Comput. Oper. Res., 67 (2016), 143–154. https://doi.org/10.1016/j.cor.2015.10.011 doi: 10.1016/j.cor.2015.10.011
[16]	M. Landete, J. Peiró, H. Yaman, Formulations and valid inequalities for the capacitated dispersion problem, Networks, 81 (2023), 294–315. https://doi.org/10.1002/net.22132 doi: 10.1002/net.22132
[17]	Z. Lu, A. Martínez-Gavara, J. K. Hao, X. Lai, Solution-based tabu search for the capacitated dispersion problem, Expert Syst. Appl., 223 (2023), 119856.
[18]	J. Maisano, A. Radchik, T. Ling, A log-normal model for demand forecasting in the national electricity market, ANZIAM J., 57 (2016), 369–383. https://doi.org/10.21914/anziamj.v57i0.8910 doi: 10.21914/anziamj.v57i0.8910
[19]	R. Marti, A. Martinez-Gavara, J. Sanchez-Oro, The capacitated dispersion problem: An optimization model and a memetic algorithm, Memetic Comp., 13 (2021), 131–146. https://doi.org/10.1007/s12293-020-00318-1 doi: 10.1007/s12293-020-00318-1
[20]	A. Martinez-Gavara, T. Corberan, R. Marti, Grasp and tabu search for the generalized dispersion problem, Expert Syst. Appl., 173 (2021), 114703. https://doi.org/10.1016/j.eswa.2021.114703 doi: 10.1016/j.eswa.2021.114703
[21]	R. Martí, M. Gallego, A. Duarte, A branch and bound algorithm for the maximum diversity problem, Eur. J. Oper. Res., 200 (2010), 36–44. https://doi.org/10.1016/j.ejor.2008.12.023 doi: 10.1016/j.ejor.2008.12.023
[22]	M. Marufuzzaman, R. Gedik, M. S. Roni, A benders based rolling horizon algorithm for a dynamic facility location problem, Comput. Ind. Eng., 98 (2016), 462–469. https://doi.org/10.1016/j.cie.2016.06.029 doi: 10.1016/j.cie.2016.06.029
[23]	S. Mišković, Z. Stanimirović, I. Grujičić, An efficient variable neighborhood search for solving a robust dynamic facility location problem in emergency service network, Electron. Notes Discrete Math., 47 (2015), 261–268. https://doi.org/10.1016/j.endm.2014.11.034 doi: 10.1016/j.endm.2014.11.034
[24]	N. Mladenović, R. Todosijević, D. Urošević, M. Ratli, Solving the capacitated dispersion problem with variable neighborhood search approaches: From basic to skewed vns, Comput. Oper. Res., 139 (2022), 105622. https://doi.org/10.1016/j.cor.2021.105622 doi: 10.1016/j.cor.2021.105622
[25]	R. H. Pearce, M. Forbes, Disaggregated benders decomposition and branch-and-cut for solving the budget-constrained dynamic uncapacitated facility location and network design problem, Eur. J. Oper. Res., 270 (2018), 78–88.
[26]	J. Peiró, I. Jiménez, J. Laguardia, R. Martí, Heuristics for the capacitated dispersion problem, Int. T. Oper. Res., 28 (2021), 119–141. https://doi.org/10.1111/itor.12799 doi: 10.1111/itor.12799
[27]	B. S. Pimentel, G. R. Mateus, F. A. Almeida, Stochastic capacity planning and dynamic network design, Int. J. Prod. Econ., 145 (2013), 139–149. https://doi.org/10.1016/j.ijpe.2013.01.019 doi: 10.1016/j.ijpe.2013.01.019
[28]	R. M. Rosati, A. Schaerf, Multi-neighborhood simulated annealing for the capacitated dispersion problem, Expert Syst. Appl., 255 (2024), 124484. https://doi.org/10.1016/j.eswa.2024.124484 doi: 10.1016/j.eswa.2024.124484
[29]	D. J. Rosenkrantz, G. K. Tayi, S. Ravi, Facility dispersion problems under capacity and cost constraints, J. Comb. Optim., {\bf4 } (2000), 7–33.
[30]	A. Silva, D. Aloise, L. C. Coelho, C. Rocha, Heuristics for the dynamic facility location problem with modular capacities, Eur. J. Oper. Res., 290 (2021), 435–452. https://doi.org/10.1016/j.ejor.2020.08.018 doi: 10.1016/j.ejor.2020.08.018
[31]	L. Wang, Z. Zhang, C. Wu, D. Xu, X. Zhang, Approximation algorithms for the dynamic k-level facility location problems, Theor. Comput. Sci., 853 (2021), 43–56.
[32]	J. Xu, S. Sen, Ensemble variance reduction methods for stochastic mixed-integer programming and their application to the stochastic facility location problem, INFORMS J. Comput., 36 (2024), 587–599. https://doi.org/10.1287/ijoc.2021.0324 doi: 10.1287/ijoc.2021.0324

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)