×

zbMATH — the first resource for mathematics

Local search algorithms for the maximal planar layout problem. (English) Zbl 0868.90072
Summary: 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 methods 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.

MSC:
90B80 Discrete location and assignment
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Boswell S.G., International Journal of Production Research 30 pp 1957– (1992)
[2] DOI: 10.1016/0305-0483(78)90008-7 · doi:10.1016/0305-0483(78)90008-7
[3] N. Christofides, and H. Hasan (1991 ). Lagrangian relaxation for the maximal planar graph . Technical report SWP9127/OR, The Management School, Imperial College of Science, Technology and Medicine, University of London, UK.
[4] Collins N.E., American Journal, of Mathematical and Management Science 8 pp 209– (1988)
[5] Domschke W., Location and Lyout planning: An Internationl Bibliograph (1985) · doi:10.1007/978-3-662-02447-8
[6] Eades P., In Lecture notes in Mathematics (1982)
[7] DOI: 10.1016/0377-2217(90)90001-R · Zbl 0699.90080 · doi:10.1016/0377-2217(90)90001-R
[8] Foulds L.R., International Journal of Production Research 16 pp 27– (1978)
[9] Foulds L.R., Operational Research Quarterly 27 pp 845– (1976)
[10] Foulds L.R., Operations Research 33 pp 1091– (1985)
[11] J.W. Giffin (1984 ). Graph theoretic techniques for facilities layout. Doctoral dissertation, University of Canterbury, Christchurch, New Zealand.
[12] DOI: 10.1016/0305-0548(86)90048-1 · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[13] Glover F., ORSA Journal on computing 1 pp 190– (1989) · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[14] Glover F., ORSA Journal on computing 2 pp 4– (1990) · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[15] Glover F., Annals of Operations Research 41 (1993)
[16] Goethschalckx M., European Journal of Operational Research 23 pp 987– (1992)
[17] M. Hasan (1992 ). A graph-theoretic approach to the facility layout problem. Ph.D. dissertation, The Management Scholl. Imperial College of Science, Technology and Medicine. Univeristy of London, UK.
[18] Hassan M. M., Omega 7 pp 301– (1987)
[19] DOI: 10.1016/0377-2217(91)90088-D · Zbl 0726.90024 · doi:10.1016/0377-2217(91)90088-D
[20] Kirkpatrick S., Science 20 pp 1050– (1983)
[21] DOI: 10.2307/1907742 · Zbl 0098.12203 · doi:10.2307/1907742
[22] DOI: 10.1016/0377-2217(87)90238-4 · Zbl 0612.90035 · doi:10.1016/0377-2217(87)90238-4
[23] Laarhoven P., Simulated Annealing: Theor and Applications (1987) · doi:10.1007/978-94-015-7744-1
[24] Laporte G., Metaheuristics in Cimbinatorial Optmization, Annals of Operations Research (1995)
[25] Leung J., Management Science 38 pp 595– (1992) · Zbl 0773.90034 · doi:10.1287/mnsc.38.4.594
[26] Levin P.H., Architects Journal 7 pp 809– (1964)
[27] DOI: 10.1007/BF01582166 · Zbl 0581.90061 · doi:10.1007/BF01582166
[28] Montreuil B., IIE Transoctions 21 pp 136– (1989)
[29] DOI: 10.1016/0305-0483(76)90060-8 · doi:10.1016/0305-0483(76)90060-8
[30] Muther R., Practical Plant Layout (1975)
[31] Muther R., Systematic Layout Planning (1973)
[32] Nijenhuis A., Combinatorial Algorithms for Computers and Calculators (1978) · Zbl 0476.68047
[33] Nugent C.E., Operations Research 16 pp 150– (1968)
[34] I.H. Osman (1991 ). Metastrategy: simulated annealing and tabu search for combinatorial optimization problems. Ph.D. dissertation. The Management School. Imperial College of Science, Technology and Medicine. University of London, UK.
[35] DOI: 10.1007/BF02023004 · Zbl 0775.90153 · doi:10.1007/BF02023004
[36] Osman I.H., OR Spektrum 17 (231) (1995)
[37] Osman I.H., Simulated annealing and desent algorithms for capacitated clustering problem (1989)
[38] DOI: 10.1016/0969-6016(94)90032-9 · Zbl 0857.90107 · doi:10.1016/0969-6016(94)90032-9
[39] Osman I.H., Metaheuristics: the state of the art 1995 (1995)
[40] I.H. Osman, and G. Laporte (1995 ). Modern heuristics for combinational optimization problems: an annotated bibliography. Forthcoming in Annals of Operations Research.
[41] DOI: 10.1016/0305-0483(89)90059-5 · doi:10.1016/0305-0483(89)90059-5
[42] Osman I.H., Heuristics for the vehicle fleet mix problem (1994)
[43] Reeves C.R., Modern Heuristic Techniques for combinatorial Problems (1993) · Zbl 0942.90500
[44] Sahni S., Journal of Associated Comuting Machinery 23 pp 555– (1976) · Zbl 0348.90152 · doi:10.1145/321958.321975
[45] Sepanen J., Management Science 17 pp 242– (1970) · doi:10.1287/mnsc.17.4.B242
[46] DOI: 10.1016/0377-2217(92)90034-7 · Zbl 0825.90474 · doi:10.1016/0377-2217(92)90034-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.