Minimization of consecutive blocks at large scale using the Lin-Kernighan-Helsgaun algorithm

Consecutive Blocks Minimization (CBM) is an NP-hard problem with relevant applications in different domains. This study investigates a solution approach based on a reduction to the traveling salesman problem, combined with the Lin-Kernighan-Helsgaun algorithm, resulting in the LKH-CBM method. The experiments were conducted on a consolidated benchmark from the literature, composed of 85 instances, including large-scale cases. The results show that LKHCBM obtained 71 new best solutions, with no results worse than the best values previously reported. Furthermore, the method found optimal solutions for all 42 instances with a known optimum in the classical subset and showed statistically significant superiority compared to state-of-the-art methods.