A Grammar-based Genetic Programming Hyper-Heuristic for Corridor Allocation Problem

Layout problems are the physical arrangement of facilities along a given area commonly used in practice. The Corridor Allocation Problem (CAP) is a class of layout problems in which no overlapping of rooms is allowed, no empty spaces are allowed between the rooms, and the two first facilities (one on each side) are placed on zero abscissa. This combinatorial problem is usually solved using heuristics, but designing and selecting the appropriate parameters is a complex task. Hyper-Heuristic can be used to alleviate this task by generating heuristics automatically. Thus, we propose a Grammar-based Genetic Programming Hyper-Heuristic (GGPHH) to generate heuristics for CAP. We investigate (i) the generation of heuristics using a subset of the instances of the problem and (ii) using a single instance. The results show that the proposed approach generates competitive heuristics, mainly when a subset of instances are used. Also, we found a single instance that can be used to generate heuristics that generalize to other cases.