On the Effectiveness of Memetic Search in Population-Based Metaheuristics for the One-Dimensional Cutting Stock Problem
TL;DR
A comparative assessment of how the common local search component affects different metaheuristic paradigms for full 1D-CSP is provided.
Abstract
Although population-based metaheuristic algorithms have been widely applied to the One-Dimensional Cutting Stock Problem (1D-CSP), their performance is often limited by premature convergence and insufficient local search capability. This study presents a comparative investigation of the effect of local search on four population-based metaheuristic paradigms for the one-dimensional cutting stock problem (1D-CSP). Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), and Grey Wolf Optimizer (GWO) are evaluated both in their standard forms and after incorporating a common Simulated Annealing (SA)-based local refinement procedure. The objective is not to introduce a new hybridization strategy but to systematically examine whether and to what extent the same local search mechanism affects algorithms with different search characteristics. The methods are evaluated on two complementary benchmark datasets comprising 39 industrial instances from the Japanese chemical fiber industry and 1800 CUTGEN1 instances. Performance was evaluated using clipping loss, computational cost, Friedman ranks, win counts, and paired Wilcoxon signed-rank tests. According to the results, statistically significant differences were observed for GA, PSO, and GWO across both benchmark sets, while the difference between ACO and M-ACO was not statistically significant. The study provides a comparative assessment of how the common local search component affects different metaheuristic paradigms for full 1D-CSP.