Efficient facility layout planning in a maximally planar graph model

In the domain of facility and factory layout planning, the difficult proble m of finding a maximum weight planar subgraph of an edge-weighted complete graph has many important practical applications. We introduce new neighbour hood structures to generate an initial solution and yield feasible modifica tions of a current layout. We compare our constructive algorithm to a coupl e of approaches from the literature in order to receive an initial feasible solution. Moreover, a new implementation of Leung's greedy heuristic outpe rforms all other layout approximation algorithms in quality. Computational results demonstrate the performance characteristics.