A hybrid genetic algorithm with decomposition phases for the Unequal Area Facility Layout Problem

We address the Unequal-Area Facility-Layout Problem (UA-FLP), which aims to dimension and locate rectangular facilities in an unlimited floor space, without overlap, while minimizing the sum of distances among facilities weighted by “material-handling” flows. We introduce two algorithmic approaches to address this problem: a basic Genetic Algorithm (GA), and a GA combined with a decomposition strategy via partial solution deconstructions and reconstructions. To efficiently decompose the problem, we impose a solution structure where no facility should cross the X or Y axis. Although this restriction can possibly deteriorate the value of the best achievable solution, it also greatly enhances the search capabilities of the method on medium and large problem instances. For most such instances, current exact methods are impracticable. As highlighted by our experiments, the resulting algorithm produces solutions of high quality for the two classic datasets of the literature, improving six out of the eight best known solutions from the first set, with up to 125 facilities, and all medium- and large-scale instances from the second set. For some of the largest instances of the second set, with 90 or 100 facilities, the average solution improvement goes as high as 6 percent or 7 percent when compared to previous algorithms, in less CPU time. We finally introduce additional instances with up to 150 facilities. On this benchmark, the decomposition method provides an average solution improvement with respect to the basic GA of about 9 percent and 1.3 percent on short and long runs, respectively.