Two new heuristic algorithms for the maximal planar layout problem

The adjacency problem is an important sub-problem in facility layout planning. It is known to be NP-complete, so heuristics are required to solve ‘large’ problem instances. In this paper two new heuristics for the adjacency problem are introduced which belong to a special class of constructive methods called Triangulation Expansion Heuristics. Extensive numerical experiments have been carried out in order to evaluate the proposed methods in terms of computing times and solution quality. It has been found that at least one method is clearly superior to the best methods proposed in the literature so far.