Why simheuristics?: benefits, limitations, and best practices when combining metaheuristics with simulation

• Autores: Manuel Chica Serrano , Ángel Alejandro Juan Pérez , Christopher Bayliss, Óscar Cordón García , W. David Kelton
• Localización: Sort: Statistics and Operations Research Transactions, ISSN 1696-2281, Vol. 44, Nº. 2, 2020, págs. 311-334
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Dialnet Métricas: 1 Cita
• Resumen

  • Many decision-making processes in our society involve NP-hard optimization problems. The largescale, dynamism, and uncertainty of these problems constrain the potential use of stand-alone optimization methods. The same applies for isolated simulation models, which do not have the potential to find optimal solutions in a combinatorial environment. This paper discusses the utilization of modelling and solving approaches based on the integration of simulation with metaheuristics.

    These ‘simheuristic’ algorithms, which constitute a natural extension of both metaheuristics and simulation techniques, should be used as a ‘first-resort’ method when addressing large-scale and NP-hard optimization problems under uncertainty –which is a frequent case in real-life applications. We outline the benefits and limitations of simheuristic algorithms, provide numerical experiments that validate our arguments, review some recent publications, and outline the best practices to consider during their design and implementation stages

• Referencias bibliográficas
  • Andradóttir, S. (2006). An overview of simulation optimization via random search. Handbooks in Operations Research and Management Science,...
  • Anter, A. M. and Ali, M. (2020). Feature selection strategy based on hybrid crow search optimization algorithm integrated with chaos theory...
  • April, J., Glover, F., Kelly, J. P. and Laguna, M. (2003). Simulation-based optimization: practical introduction to simulation optimization....
  • April, J., Better, M., Glover, F., Kelly, J. and Laguna, M. (2006). Enhancing business process management with simulation optimization. In...
  • Beyer, H.-G. and Sendhoff, B. (2007). Robust optimization–a comprehensive survey. Computer Methods in Applied Mechanics and Engineering, 196,...
  • Bhatnagar, S., Fu, M. C., Marcus, S. I. and Wang, I.-J. (2003). Two-timescale simultaneous perturbation stochastic approximation using deterministic...
  • Bonissone, P. P., Subbu, R. and Lizzi, J. (2009). Multicriteria decision making: a framework for research and applications. IEEE Computational...
  • Boschetti, M. A., Maniezzo, V., Roffilli, M. and Röhler, A. B. (2009). Matheuristics: optimization, simulation and control. In Hybrid Metaheuristics,...
  • Cabrera, G., Juan, A. A., Lázaro, D., Marquès, J. M. and Proskurnia, I. (2014). A simulation-optimization approach to deploy internet...
  • Calvet, L., Wang, D., Juan, A. A. and Bové, L. (2019). Solving the multidepot vehicle routing problem with limited depot capacity and stochastic...
  • Chau, M., Fu, M. C., Qu, H. and Ryzhov ,I. O. (2014). Simulation optimization: a tutorial overview and recent developments in gradient-based...
  • Chica, M., Barranquero, J., Kajdanowicz, T., Cordón, O. and Damas, S. (2017). Multimodal optimization: an effective framework for model...
  • Chica, M., Bautista, J., Cordón, Ó. and Damas, S. (2016). A multiobjective model and evolutionary algorithms for robust time and space...
  • Couture, R.-M., Moe, S. J., Lin, Y., Kaste, Ø., Haande, S. and Solheim, A. L. (2018). Simulating water quality and ecological status of Lake...
  • De Armas, J., Juan, A. A., Marquès, J. M. and Pedroso, J. P. (2017). Solving the deterministic and stochastic uncapacitated facility location...
  • Deb, K., Bandaru, S., Greiner, D., Gaspar-Cunha, A. and Tutum, C. C. (2014). An integrated approach to automated innovization for discovering...
  • Djanatliev, A. and German, R. (2013). Prospective healthcare decision-making by combined system dynamics, discrete-event and agent-based simulation....
  • Dokeroglu, T., Sevinc, E., Kucukyilmaz, T. and Cosar, A. (2019). A survey on new generation metaheuristic algorithms. Computers & Industrial...
  • Dorigo, M. and Stützle, T. (2004). Ant Colony Optimization. MIT Press, Cambridge.
  • Faulin, J., Juan, A. A., Serrat, C. and Bargueno, V. (2008). Predicting availability functions in timedependent complex systems with saedes...
  • Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6, 109–133.
  • Ferone, D., Gruler, A., Festa, P. and Juan, A. A. (2019). Enhancing and extending the classical GRASP framework with biased randomisation...
  • Figueira, G. and Almada-Lobo, B. (2014). Hybrid simulation–optimization methods: a taxonomy and discussion. Simulation Modelling Practice...
  • Fischetti, M. and Fischetti, M. (2018). Matheuristics. In Handbook of Heuristics, pp. 121–153. Springer.
  • Forrester, J. W. (2007). System dynamics: the next fifty years. System Dynamics Review, 23, 359–370.
  • Fu, M. C. (2002). Optimization for simulation: theory vs. practice. INFORMS Journal on Computing, 14, 192–215.
  • Fu, M. C. (2015). Handbook of Simulation Optimization, Volume 216. Springer.
  • Glover, F., Kelly, J. P. and Laguna, M. (1996). New advances and applications of combining simulation and optimization. In Proceedings of...
  • Glover, F., Kelly, J. P. and Laguna, M. (1999). New advances for wedding optimization and simulation. In Proceedings of the Winter Simulation...
  • Glover, F. and Laguna, M. (2013). Tabu search. In Handbook of Combinatorial Optimization, pp. 3261– 3362. Springer.
  • Glover, F. W. and Kochenberger, G. A. (2006). Handbook of Metaheuristics, Volume 57. Springer Science & Business Media.
  • Gonzalez-Martin, S., Juan, A. A., Riera, D., Elizondo, M. G. and Ramos, J. J. (2018). A simheuristic algorithm for solving the arc routing...
  • Gonzalez-Neira, E. M., Ferone, D., Hatami, S. and Juan, A. A. (2017). A biased-randomized simheuristic for the distributed assembly permutation...
  • Gosavi, A. (2015). Simulation-Based Optimization. Springer US, New York.
  • Gruler, A., de Armas, J., Juan, A. A. and Goldsman, D. (2019). Modelling human network behaviour using simulation and optimization tools:...
  • Gruler, A., Fikar, C., Juan, A. A., Hirsch, P. and Contreras-Bolton, C. (2017a). Supporting multi-depot and stochastic waste collection management...
  • Gruler, A., Panadero, J., de Armas, J., Moreno, J. A. and Juan, A. A. (2020a). A variable neighbourhood search simheuristic for the multiperiod...
  • Gruler, A., A. Perez-Navarro, L. Calvet, and A. A. Juan (2020b). A simheuristic algorithm for timedependent waste collection management with...
  • Gruler, A., Quintero, C. L., Calvet, L. and Juan, A. A. (2017b). Waste collection under uncertainty: a simheuristic based on variable neighbourhood...
  • Hansen, P., Mladenović, N. and Moreno, J. A. (2010). Variable neighbourhood search: methods and applications. Annals of Operations Research,...
  • Hatami, S., Calvet, L., Fernández-Viagas, V., Framiñán, J. M. and Juan, A. A. (2018). A simheuristic algorithm to set up starting times...
  • Heath, S. K., Buss, A., Brailsford, S. C. and Macal, C. M. (2011). Cross-paradigm simulation modelling: challenges and successes. In Proceedings...
  • Hubscher-Younger, T., Mosterman, P. J., DeLand, S., Orqueda, O. and Eastman, D. (2012). Integrating discrete-event and time-based models with...
  • Hussain, K., Salleh, M. N. M., Cheng, S. and Shi, Y. (2019). Metaheuristic research: a comprehensive survey. Artificial Intelligence Review,...
  • Jian, N. and Henderson, S. G. (2015). An introduction to simulation optimization. In Proceedings of the Winter Simulation Conference, Piscataway,...
  • Juan, A., Faulin, J., Grasman, S., Riera, D., Marull, J. and Mendez, C. (2011). Using safety stocks and simulation to solve the vehicle routing...
  • Juan, A. A., Corlu, C. G., Tordecilla, R. D., de la Torre, R. and Ferrer, A. (2020). On the use of biasedrandomized algorithms for solving...
  • Juan, A. A., Grasman, S. E., Caceres-Cruz, J. and Bektaş, T. (2014). A simheuristic algorithm for the single-period stochastic inventory-routing...
  • Juan, A. A., Kelton, W. D., Currie, C. S. and Faulin, J. (2018). Simheuristics applications: dealing with uncertainty in logistics, transportation,...
  • Kasaie, P. and Kelton, W. D. (2015). Guidelines for design and analysis in agent-based simulation studies. In Proceedings of the Winter Simulation...
  • Keith, A. J. and Ahner, D. K. (2019). A survey of decision making and optimization under uncertainty. Annals of Operations Research, SI, 1–35.
  • Kelton, W. D., Sadowski, R. and Zupick, N. B. (2015). Simulation with Arena (6th Edition). McGraw-Hill Education.
  • Kennedy, J. (2010). Particle swarm optimization. In Encyclopedia of Machine Learning, pp. 760–766. Springer.
  • Kirkpatrick, S.,Gelatt, J. C. D. and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671–680.
  • Kleijnen, J. P., Sanchez, S. M., Lucas, T. W. and Cioppa, T. M. (2005). State-of-the-art review: a user’s guide to the brave new world of...
  • Kleijnen, J. P. and Wan, J. (2007). Optimization of simulated systems: OptQuest and alternatives. Simulation Modelling Practice and Theory,...
  • Laguna, M. and Marti, R. (2012). Scatter Search: Methodology and Implementations in C, Volume 24. Springer Science & Business Media.
  • Larranaga, P. and Lozano, J. A. (2002). Estimation of Distribution Algorithms: a New Tool for Evolutionary Computation, Volume 2. Springer...
  • Lee, C. K. H. (2018). A review of applications of genetic algorithms in operations management. Engineering Applications of Artificial Intelligence,...
  • Li, L., Jafarpour, B. and Mohammad-Khaninezhad, M. R. (2013). A simultaneous perturbation stochastic approximation algorithm for coupled well...
  • Ligmann-Zielinska, A., Kramer, D. B., Cheruvelil, K. S. and Soranno, P. A. (2014). Using uncertainty and sensitivity analyses in socioecological...
  • Lourenço, H. R., Martin, O. C. and Stützle, T. (2010). Iterated local search: framework and applications. In Handbook of Metaheuristics,...
  • Lucas, T. W., Kelton, W. D., Sánchez, P. J., Sanchez, S. M. and Anderson, B. L. (2015). Changing the paradigm: simulation, now a method...
  • Melani, A. H., Murad, C. A., Caminada Netto, A., Souza, G. F. and Nabeta, S. I. (2019). Maintenance strategy optimization of a coal-fired...
  • Miettinen, K. (2014). Survey of methods to visualize alternatives in multiple criteria decision making problems. OR Spectrum, 36, 3–37.
  • Morecroft, J. (2007). Strategic Modelling and Business Dynamics: A Feedback Systems Approach. John Wiley & Sons.
  • Moscato, P. and Mathieson, L. (2019). Memetic algorithms for business analytics and data science: a brief survey. In Business and Consumer...
  • Oliva, R. (2003). Model calibration as a testing strategy for system dynamics models. European Journal of Operational Research, 151, 552–568.
  • Pagès-Bernaus, A., Ramalhinho, H., Juan, A. A. and Calvet, L. (2019). Designing e-commerce supply chains: a stochastic facility–location...
  • Panadero, J., Doering, J., Kizys, R., Juan, A. A. and Fito, A. (2020). A variable neighbourhood search simheuristic for project portfolio...
  • Prékopa, A. (2013). Stochastic Programming, Volume 324. Springer Science & Business Media.
  • Qudrat-Ullah, H. and Seong, B. S. (2010). How to do structural validity of a system dynamics type simulation model: the case of an energy...
  • Quintero-Araujo, C. L., Caballero-Villalobos, J. P., Juan, A. A. and Montoya-Torres, J. R. (2017). A biasedrandomized metaheuristic for the...
  • Rabe, M., Deininger, M. and Juan, A. A. (2020). Speeding up computational times in simheuristics combining genetic algorithms with discrete-event...
  • Reyes-Rubiano, L., Ferone, D., Juan, A. A. and Faulin, J. (2019). A simheuristic for routing electric vehicles with limited driving ranges...
  • Ruszczyński, A. and Shapiro, A. (2003). Stochastic programming models. Handbooks in Operations Research and Management Science, 10, 1–64.
  • Saltelli, A., Ratto, M., Andres, T., Campolongo, F., Cariboni, J., Gatelli, D., Saisana, M. and Tarantola, S. (2008). Global Sensitivity Analysis:...
  • Sargent, R. G. (2005). Verification and validation of simulation models. In Proceedings of the Winter simulation Conference, Piscataway, New...
  • Shimoyama, K., Oyama, A. and Fujii, K. (2005). A new efficient and useful robust optimization approach design for multi-objective six sigma....
  • Singh, A. and Jana, N. D. (2017). A survey on metaheuristics for solving large scale optimization problems. International Journal of Computer...
  • Spall, J. C. (2005). Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control, Volume 65. John Wiley &...
  • Sterman, J. D. (2001). System dynamics modelling: tools for learning in a complex world. California Management Review, 43, 8–25.
  • Taguchi, G. (1989). Introduction to Quality Engineering. American Supplier Institute.
  • Talbi, E.-G. (2009). Metaheuristics: from Design to Implementation. John Wiley & Sons.
  • Taleb, N. N. and Swan, B. (2008). The Impact of the Highly Improbable. Penguin Books Limited.
  • Tigane, S., Kahloul, L. and Bourekkache, S. (2017). Reconfigurable stochastic petri nets: A new formalism for reconfigurable discrete event...
  • Voinov, A. and Bousquet, F. (2010). Modelling with stakeholders. Environmental Modelling & Software, 25, 1268–1281.
  • Wainer, G. A. (2017). Discrete-Event Modeling and Simulation: a Practitioner’s Approach. CRC press.
  • Xu, J., Huang, E., Chen, C.-H. and Lee, L. H. (2015). Simulation optimization: A review and exploration in the new era of cloud computing...