GRASP with path relinking for the single row facility layout problem

The single row facility layout problem (SRFLP) is an NPNP-hard problem that consists of finding an optimal arrangement of a set of rectangular facilities (with equal height and different lengths), placing them next to each other along a line. The SRFLP has practical applications in contexts such as arranging rooms along corridors, setting books on shelves, allocating information on magnetic disks, storing items in warehouses, or designing layouts for machines in manufacturing systems. This paper combines the greedy randomized adaptive search procedure (GRASP) methodology, and path relinking (PR) in order to efficiently search for high-quality solutions for the SRFLP. In particular, we introduce: (i) several construction procedures, (ii) a new fast local search strategy, and (iii) an approach related to the Ulam distance in order to construct short path relinking trajectories. We also present a new set of large challenging instances, since previous sets do not allow to determine significant differences among advanced metaheuristics. Experiments show that our procedure outperforms state-of-the-art methods in all of the scenarios we considered. Firstly, the GRASP with PR finds the best known solutions for previous instances used in the literature, but employing considerably less computing time than its competitors. Secondly, our method outperforms the current state-of-the-art methods in 38 out of 40 new instances when running for the same amount of computing time. Finally, nonparametric tests for detecting differences between algorithms report p  -values below 10−11,10−11, which supports the superiority of our approach.