Premium
Local Search Algorithms for the Maximal Planar Layout Problem
Author(s) -
Hasan M.,
Osman I.H.
Publication year - 1995
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1995.tb00007.x
Subject(s) - tabu search , simulated annealing , mathematical optimization , algorithm , computation , schedule , monotonic function , search algorithm , graph , guided local search , computer science , local search (optimization) , hill climbing , mathematics , theoretical computer science , operating system , mathematical analysis
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.