Metaheuristics for the template design problem: encoding, symmetry and hybridisation

David Rodríguez Rueda (), Carlos Cotta () and Antonio J. Fernández-Leiva ()
Additional contact information
David Rodríguez Rueda: Universidad Nacional Experimental del Táchira (UNET)
Carlos Cotta: Universidad de Málaga
Antonio J. Fernández-Leiva: Universidad de Málaga

Journal of Intelligent Manufacturing, 2021, vol. 32, issue 2, No 14, 559-578

Abstract: Abstract The template design problem (TDP) is a hard combinatorial problem with a high number of symmetries which makes solving it more complicated. A number of techniques have been proposed in the literature to optimise its resolution, ranging from complete methods to stochastic ones. However, although metaheuristics are considered efficient methods that can find enough-quality solutions at a reasonable computational cost, these techniques have not proven to be truly efficient enough to deal with this problem. This paper explores and analyses a wide range of metaheuristics to tackle the problem with the aim of assessing their suitability for finding template designs. We tackle the problem using a wide set of metaheuristics whose implementation is guided by a number of issues such as problem formulation, solution encoding, the symmetrical nature of the problem, and distinct forms of hybridisation. For the TDP, we also propose a slot-based alternative problem formulation (distinct to other slot-based proposals), which represents another option other than the classical variation-based formulation of the problem. An empirical analysis, assessing the performance of all the metaheuristics (i.e., basic, integrative and collaborative algorithms working on different search spaces and with/without symmetry breaking) shows that some of our proposals can be considered the state-of-the-art when they are applied to specific problem instances.

Keywords: Template design problem; Symmetry breaking; Optimisation; Problem formulation; Metaheuristics; Memetic algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10845-020-01587-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joinma:v:32:y:2021:i:2:d:10.1007_s10845-020-01587-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10845

DOI: 10.1007/s10845-020-01587-w

Access Statistics for this article

Journal of Intelligent Manufacturing is currently edited by Andrew Kusiak

More articles in Journal of Intelligent Manufacturing from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().