Ir al contenido

Documat

GRASP: an application to efficiently plan the low carbon emission distributed additive manufacturing

  • Daniele Ferone [1] ; Paola Festa [1] Árbol académico ; Tommaso Pastore [1]
    1. [1] University of Naples “Federico II”,Italy
  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 199-228
  • Idioma: inglés
  • DOI: 10.1007/s11750-025-00696-0
  • Enlaces
  • Resumen

    • GRASP is a well-established metaheuristic algorithm that efficiently designs optimized solutions for complex problems. It has achieved notable results in scientific literature, particularly when addressing scenarios with many intricacies, where optimal solutions can be difficult to achieve in short computational times. This is often the case for challenging optimization problems aiming to foster sustainable practices. Our paper discusses the basic components of a GRASP and some of the most notable improvement strategies, while presenting an implementation that is specifically tailored to plan a sustainable framework for distributed additive manufacturing. The problem we address is planning a production schedule for a set of additively manufactured parts required by customers, followed by their subsequent shipment from the fabrication plants to the customers’ location. A comparison between GRASP and CPLEX showed that GRASP can obtain optimal or high-quality solutions while significantly reducing computational times.

  • Referencias bibliográficas
    • Aiex RM, Resende M, Pardalos PM et al (2005) GRASP with path relinking for three-index assignment. INFORMS J Comput 17(2):224–247. https://doi.org/10.1287/ijoc.1030.0059
    • Ait Haddadene SR, Labadie N, Prodhon C (2016) A GRASP × ILS for the vehicle routing problem with time windows, synchronization and precedence...
    • Al Chami Z, Bechara B, Manier H et al (2021) A GRASP-ALNS combination for robust pickup and delivery problem. Int J Prod Res 60(12):3809–3828....
    • Allahyari S, Yaghoubi S, Van Woensel T (2021) The secure time-dependent vehicle routing problem with uncertain demands. Comput Oper Res 131:105253....
    • Alvarez-Valdes R, Parreño F, Tamarit JM (2008) Reactive GRASP for the strip-packing problem. Comput Oper Res 35(4):1065–1083. https://doi.org/10.1016/j.cor.2006.07.004
    • Alvarez-Valdés R, Parreño F, Tamarit JM (2013) A GRASP/Path relinking algorithm for two-and three-dimensional multiple bin-size bin packing...
    • Bautista J, Pereira J (2007) A GRASP algorithm to solve the unicost set covering problem. Comput Oper Res 34(10):3162–3173. https://doi.org/10.1016/j.cor.2005.11.026
    • Boudia M, Louly M, Prins C (2007) A reactive GRASP and path relinking for a combined production-distribution problem. Comput Oper Res 34(11):3402–3419....
    • Bruglieri M, Ferone D, Festa P et al (2022) A GRASP with penalty objective function for the green vehicle routing problem with private capacitated...
    • Canuto SA, Resende M, Ribeiro CC (2001) Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks...
    • Chaovalitwongse W, Kim D, Pardalos PM (2003) GRASP with a new local search scheme for vehicle routing problems with time windows. J Comb Optim...
    • Di Puglia PL, Ferone D, Festa P et al (2022) Solution approaches for the vehicle routing problem with occasional drivers and time windows....
    • Duarte A, Sánchez-Oro J, Mladenović N et al (2018) Variable neighborhood descent. Springer International Publishing, pp 341–367. https://doi.org/10.1007/978-3-319-07124-4_9
    • Díaz JA, Luna DE, Camacho-Vallejo JF et al (2017) GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location problem with...
    • Felici G, Ferone D, Festa P et al (2017) A GRASP for the minimum cost SAT problem. Springer International Publishing, pp 64–78. https://doi.org/10.1007/978-3-319-69404-7_5
    • Feo TA, Resende M (1995) Greedy randomized adaptive search procedures. J Glob Optim 6:109–133
    • Ferone D, Festa P, Resende M (2015) Hybridizations of GRASP with path relinking for the far from most string problem. Int Trans Oper Res 23(3):481–506....
    • Ferone D, Gruler A, Festa P et al (2019) Enhancing and extending the classical GRASP framework with biased randomisation and simulation. J...
    • Ferone D, Festa P, Guerriero F (2022) The rainbow Steiner tree problem. Comput Oper Res 139:105621. https://doi.org/10.1016/j.cor.2021.105621
    • Ferone D, Festa P, Pastore T et al (2023) Efficient GRASP solution approach for the prisoner transportation problem. Comput Oper Res 153:106161....
    • Ferreira CS, Ochi LS, Parada V et al (2012) A GRASP-based approach to the generalized minimum spanning tree problem. Expert Syst Appl 39(3):3526–3536....
    • Festa P, Resende M (2009) An annotated bibliography of GRASP-part I: algorithms. Int Trans Oper Res 16(1):1–24
    • Festa P, Resende M (2009) An annotated bibliography of GRASP-part II: applications. Int Trans Oper Res 16(2):131–172
    • Festa P, Pardalos PM, Resende M et al (2002) Randomized heuristics for the max-cut problem. Optim Methods Softw 17(6):1033–1058. https://doi.org/10.1080/1055678021000090033
    • Festa P, Pastore T, Ferone D et al (2018) Integrating biased-randomized GRASP with Monte Carlo simulation for solving the vehicle routing...
    • Fu Y, Banerjee A (2020) Heuristic/meta-heuristic methods for restricted bin packing problem. J Heuristics 26(5):637–662. https://doi.org/10.1007/s10732-020-09444-y
    • Glover F (1997) Tabu search and adaptive memory programming—advances, applications and challenges. Springer US, pp 1–75. https://doi.org/10.1007/978-1-4615-4102-8_1
    • Gonzalez-Neira EM, Ferone D, Hatami S et al (2017) A biased-randomized simheuristic for the distributed assembly permutation flowshop problem...
    • Guerine M, Rosseti I, Plastino A (2016) Extending the hybridization of metaheuristics with data mining: dealing with sequences. Intell Data...
    • Kucukkoc I (2024) Scheduling of distributed additive manufacturing machines considering carbon emissions. Int J Optim Control Theor Appl (IJOCTA)...
    • Laguna M, Martí R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11(1):44–52. https://doi.org/10.1287/ijoc.11.1.44
    • López-Ibáñez M, Dubois-Lacoste J, Pérez Cáceres L et al (2016) The irace package: iterated racing for automatic algorithm configuration. Oper...
    • López-Sánchez AD, Sánchez-Oro J, Hernández-Díaz AG (2019) GRASP and VNS for solving the p-next center problem. Comput Oper Res 104:295–303....
    • Martínez-Gavara A, Corberán T, Martí R (2021) GRASP and tabu search for the generalized dispersion problem. Expert Syst Appl 173:114703. https://doi.org/10.1016/j.eswa.2021.114703
    • Marzo RG, Ribeiro CC (2019) A GRASP with path-relinking and restarts heuristic for the prize-collecting generalized minimum spanning tree...
    • Mateus GR, Resende M, Silva R (2010) GRASP with path-relinking for the generalized quadratic assignment problem. J Heuristics 17(5):527–565....
    • Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097–1100. https://doi.org/10.1016/s0305-0548(97)00031-2
    • Napoletano A, Martínez-Gavara A, Festa P et al (2019) Heuristics for the constrained incremental graph drawing problem. Eur J Oper Res 274(2):710–729....
    • Parreño F, Alvarez-Valdes R, Oliveira JF et al (2008) A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing. Ann Oper Res...
    • Plastino A, Fuchshuber R, Martins SL et al (2011) A hybrid data mining metaheuristic for the p-median problem. Stat Anal Data Min ASA Data...
    • Resende M, Ribeiro CC (2016) Optimization by GRASP: greedy randomized adaptive search procedures. Springer, New York. https://doi.org/10.1007/978-1-4939-6530-4
    • Reyes V, Araya I (2019) A GRASP-based scheme for the set covering problem. Oper Res Int J. https://doi.org/10.1007/s12351-019-00514-z
    • Ribeiro CC, Uchoa E, Werneck RF (2002) A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J Comput 14(3):228–246....
    • Ribeiro CC, Rosseti I, Souza RC (2013) Probabilistic stopping rules for GRASP heuristics and extensions. Int Trans Oper Res 20(3):301–323....
    • Santana I, Plastino A, Rosseti I (2020) Improving a state-of-the-art heuristic for the minimum latency problem with data mining. Int Trans...
    • Scholz FW (2014) Maximum likelihood estimation. https://doi.org/10.1002/9781118445112.stat01663
    • Wang Y, Lü Z, Glover F et al (2013) Probabilistic GRASP-Tabu search algorithms for the UBQP problem. Comput Oper Res 40(12):3100–3107. https://doi.org/10.1016/j.cor.2011.12.006
    • Yahiaoui A, Moukrim A, Serairi M (2022) GRASP-ILS and set cover hybrid heuristic for the synchronized team orienteering problem with time...
    • Yang Z, Wang G, Chu F (2013) An effective GRASP and tabu search for the 0–1 quadratic knapsack problem. Comput Oper Res 40(5):1176–1185. https://doi.org/10.1016/j.cor.2012.11.023
    • Yepes-Borrero JC, Villa F, Perea F et al (2020) GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno