An Iterated Greedy with Path Relinking for Corridor Allocation Problem

Layouts are widely applied in real-world scenarios, such as arranging rooms in buildings, machinery in production lines, and semiconductors on circuit boards. A well-designed layout is crucial for minimizing costs and increasing efficiency. The Corridor Allocation Problem (CAP) focuses on arranging facilities along a two-sided corridor to minimize communication costs. A previous study applied a Grammar-based Genetic Programming Hyper-heuristic to CAP, where the best-generated heuristic resembled an Iterated Greedy (IG) algorithm, highlighting its potential. Motivated by this, we propose a dedicated IG algorithm for solving CAP,  designing each component to fully explore this technique’s capabilities. Our method incorporates Path Relinking (PR) and Random Variable Neighborhood Descent as local search strategies, resulting in the IG-PR algorithm. We tested our approach on 89 benchmark instances and obtained competitive results compared to state-of-the-art methods, achieving similar or better solution quality while requiring less execution time than the best-performing algorithm reported in the literature.