A comparative evaluation of heuristics for the adjacency problem in facility layout planning

The adjacency problem is an important subproblem in facility layout planning. It is known to be NP-complete, so heuristics are required to solve ‘large’ problem instances. Several heuristics have been suggested for the adjacency problem, but very little reliable information is available on their relative performance. Thus, extensive numerical experiments have been carried out with a special class of heuristics called triangulation expansion methods. Two algorithms, the Wheel-Expansion Heuristic by Eades et al. and a method by Leung have proven to be superior. The test procedure that has been used to evaluate the methods is described and suggested for future testing of newly developed heuristics.