Tag: Symmetries

New Paper on Hybrid Metaheuristics for the Template Design Problem

The Template Design Problem (TDP) arises in the area of manufacturing and entails finding the best way of mass producing a collection of different packagings, i.e., trying to minimize the usage of raw materials. This entails determining a number of printing patterns/templates, which results in a combinatorial optimization problem plagued with symmetries (that is, an internal reordenation of designs within a template or the reordenation of templates thmeselves results in an equivalent solution).

To tackle these issues we have considered the use of alternative representations within the context of memetic algorithms. Our findings have been published in the paper:

The paper is freely accessible in the link above, and its abstract follows:

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.