Local Search Algorithms for the Maximal Planar Layout Problem |
| |
Authors: | M Hasan IH Osman |
| |
Affiliation: | 1. Sustainability Assessments of Materials and Circular Economy, Department of Materials Engineering, KU Leuven, Kasteelpark Arenberg 44, Leuven, 3001, Belgium;2. Flanders Make vzw, VCCM Corelab, Belgium;3. Center for Economics and Corporate Sustainability, Faculty of Economics and Business, KU Leuven, Belgium |
| |
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. |
| |
Keywords: | facility layout heuristics maximal planar graph simulated annealing tabu search exact algorithm hybrids |
本文献已被 ScienceDirect 等数据库收录! |
|