Local search algorithms for the maximal planar layout problem

Local search algorithms for the maximal planar layout problem

0.00 Avg rating0 Votes
Article ID: iaor199613
Country: United Kingdom
Volume: 2
Issue: 1
Start Page Number: 89
End Page Number: 106
Publication Date: Jan 1995
Journal: International Transactions in Operational Research
Authors: ,
Keywords: heuristics
Abstract:

The problem of laying out facilities is practically important in a modern manufacturing environment. This problem can be formulated as a weighted maximal planar graph in which vertices represent facilities and edge weights represent desirability measures between facilities. The objective is to find a planar graph that can be drawn on a plane without any edges intersecting with the highest sum of edge weights. Exact solution method can only solve small sized problems. In this paper, local search algorithms based on steepest ascent, hybrid simulated annealing and tabu search with a non-monotonic cooling schedule, and tabu search with a hashing function are developed to obtain near-optimal solutions. Different search strategies are investigated. All the developed algorithms are compared with existing construction methods and a branch and bound exact algorithm on a set of practical size problems. The proposed algorithms performed very well in terms of solution quality and computation time.

Reviews

Required fields are marked *. Your email address will not be published.