{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T23:31:27Z","timestamp":1769902287382,"version":"3.49.0"},"reference-count":59,"publisher":"Elsevier BV","issue":"8","license":[{"start":{"date-parts":[[2002,7,1]],"date-time":"2002-07-01T00:00:00Z","timestamp":1025481600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computer-Aided Design"],"published-print":{"date-parts":[[2002,7]]},"DOI":"10.1016\/s0010-4485(01)00109-9","type":"journal-article","created":{"date-parts":[[2002,10,8]],"date-time":"2002-10-08T14:34:08Z","timestamp":1034087648000},"page":"597-611","source":"Crossref","is-referenced-by-count":143,"title":["A survey of computational approaches to three-dimensional layout problems"],"prefix":"10.1016","volume":"34","author":[{"given":"J.","family":"Cagan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Shimada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0010-4485(01)00109-9_BIB1","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0010-4485(76)90006-3","article-title":"Nesting two-dimensional shapes in rectangular modules","volume":"8","author":"Adamowicz","year":"1976","journal-title":"Computer Aided Design"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB2","unstructured":"Baumgart BG. Geometric modeling for computer vision, PhD Thesis, Stanford University, 1974."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB3","series-title":"Proceedings of Eurographics \u201996","first-page":"378","article-title":"BOXTREE: a hierarchical representation for surfaces in 3D","author":"Barequet","year":"1996"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1287\/opre.33.1.49","article-title":"An exact two-dimensional non-guillotine cutting tree search procedure","volume":"33","author":"Beasley","year":"1985","journal-title":"Operational Research"},{"issue":"2","key":"10.1016\/S0010-4485(01)00109-9_BIB5","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0377-2217(90)90362-F","article-title":"A comparative evaluation of heuristics for container loading","volume":"44","author":"Bischoff","year":"1990","journal-title":"European Journal of Operational Research"},{"issue":"10","key":"10.1016\/S0010-4485(01)00109-9_BIB6","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1016\/S0010-4485(98)00036-0","article-title":"A simulated annealing-based algorithm using hierarchical models for general three-dimensional component layout","volume":"30","author":"Cagan","year":"1998","journal-title":"Computer Aided Design"},{"issue":"2","key":"10.1016\/S0010-4485(01)00109-9_BIB7","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1115\/1.2792210","article-title":"Optimal three-dimensional placement of heat generating electronic components","volume":"119","author":"Campbell","year":"1997","journal-title":"ASME Journal of Electronic Packaging"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB8","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0377-2217(90)90349-G","article-title":"average-case analysis of cutting and packing in two dimensions","volume":"44","author":"Coffman","year":"1990","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB9","series-title":"Proceedings of IEEE International Conference on CAD","first-page":"422","article-title":"Genetic placement","author":"Cohoon","year":"1986"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB10","first-page":"29","article-title":"An octree method for interference detection in computer aided 3-D packing","volume":"1","author":"Dai","year":"1994","journal-title":"Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB11","first-page":"117","article-title":"A hybrid approach of heuristic and neural network for packing problems","volume":"2","author":"Dai","year":"1994","journal-title":"Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB12","first-page":"125","article-title":"An octree based heuristic algorithm for 3-D packing","volume":"2","author":"Dai","year":"1994","journal-title":"Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB13","first-page":"1","article-title":"Placement of shapeable blocks","volume":"43","author":"De Bont","year":"1988","journal-title":"Philips Journal of Research"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB14","doi-asserted-by":"crossref","unstructured":"Dighe R, Jakiela MJ. Solving pattern nesting problems with genetic algorithms employing task decomposition and contact detection. Evolutionary Computation, Cambridge, MA, MIT Press 1995;3(3): 239\u201366.","DOI":"10.1162\/evco.1995.3.3.239"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0377-2217(92)90288-K","article-title":"Packing problems","volume":"56","author":"Dowsland","year":"1992","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB16","doi-asserted-by":"crossref","first-page":"1673","DOI":"10.1080\/00207549108948039","article-title":"Three-dimensional packing\u2014solution approaches and heuristic development","volume":"8","author":"Dowsland","year":"1991","journal-title":"International Journal of Production Research"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB17","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0377-2217(90)90350-K","article-title":"A typology of cutting and packing problems","volume":"44","author":"Dyckhoff","year":"1990","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"10.1016\/S0010-4485(01)00109-9_BIB18","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0377-2217(90)90363-G","article-title":"A computer-based heuristic for packing pooled shipment containers","volume":"44","author":"Gehring","year":"1990","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0305-0548(80)90001-5","article-title":"A heuristic for packing boxes into a container","volume":"7","author":"George","year":"1980","journal-title":"Computers and Operational Research"},{"issue":"3","key":"10.1016\/S0010-4485(01)00109-9_BIB20","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1142\/S0218195991000220","article-title":"Constructing discrete medial axis of 3-D objects","volume":"1","author":"Goldak","year":"1991","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB21","series-title":"Proceedings of SIGGRAPH \u201996","first-page":"171","article-title":"OBBTree: a hierarchical structure for rapid interference detection","author":"Gottschalk","year":"1996"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB22","unstructured":"Hills W, Smith N. A new approach to spatial layout design in complex engineered products. Proceedings of the International Conference on Engineering Design (ICED), Tampere, Finland, 19\u201321 August, 1997."},{"issue":"2","key":"10.1016\/S0010-4485(01)00109-9_BIB23","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1145\/321062.321069","article-title":"Direct search solutioin of numerical and statistical problems","volume":"8","author":"Hooke","year":"1961","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB25","unstructured":"Huang MD, Romeo F, Sangiovanni-Vincentelli AAn efficient general cooling schedule for simulated annealing, ICCAD-86. IEEE International Conference on Computer Aided Design\u2014Digest of Technical Papers, Santa Clara, CA, 11\u201313 November, 1986. p. 381\u20134."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB26","unstructured":"Hubbard PM, 1995. Real-time collision detection and time-critical computing. Workshop on Simulation and Interaction in Virtual Environment."},{"issue":"3","key":"10.1016\/S0010-4485(01)00109-9_BIB27","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/231731.231732","article-title":"Approximating polyhedra with spheres for time-critical collision detection","volume":"15","author":"Hubbard","year":"1996","journal-title":"ACM Transactions on Graphics"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB28","unstructured":"Hustin MD, Sangiovanni-Vincentelli A. TIM, a new standard cell placement program based on the simulated annealing algorithm. IEEE Physical Design Workshop on Placement and Floorplanning, 1987."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB29","unstructured":"Ikonen I, Biles W, Kumar A, Ragade RK, Wissel JC. A genetic algorithm for packing three-dimensional non-convex objects having cavities and holes. Proceedings of 7th International Conference on Genetic Algorithms, 1997."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB30","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1080\/00207548508904719","article-title":"performance testing of rectangular parts-nesting heuristics","volume":"23","author":"Israni","year":"1985","journal-title":"International Journal of Production Research"},{"issue":"1","key":"10.1016\/S0010-4485(01)00109-9_BIB31","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1080\/00207549208942880","article-title":"CLASS: Computerized LAyout Solutions Using Simulated Annealing","volume":"30","author":"Jajodia","year":"1992","journal-title":"International Journal of Production Research"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB32","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1115\/1.2912796","article-title":"Reasoning on the location of components for assembly packaging","volume":"113","author":"Kim","year":"1991","journal-title":"Journal of Mechanical Design"},{"issue":"4598","key":"10.1016\/S0010-4485(01)00109-9_BIB33","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB34","doi-asserted-by":"crossref","unstructured":"Kolli A, Cagan J, Rutenbar RA. Packing of generic, three dimensional components based on multi-resolution modeling. Proceedings of the 22nd ASME Design Automation Conference (DAC-1479), Irvine, CA, 19\u201322 August, 1996.","DOI":"10.1115\/96-DETC\/DAC-1479"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB35","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1115\/1.2919389","article-title":"Optimal packaging of complex parametric solids according to mass property criteria","volume":"116","author":"Landon","year":"1994","journal-title":"Journal of Mechanical Design"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB36","unstructured":"Lin M, Gottschalk S. Collision detection between geometric models: a survey. Proceedings of IMA Conference on Mathematics of Surfaces, 1998."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB37","series-title":"Geometric modeling","author":"Mortenson","year":"1997"},{"issue":"2","key":"10.1016\/S0010-4485(01)00109-9_BIB38","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1111\/1467-8659.1420105","article-title":"Collision detection for animation using sphere-trees","volume":"14","author":"Palmer","year":"1995","journal-title":"Computer Graphics Forum"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB39","series-title":"The science of fractal images","author":"Peitgen","year":"1988"},{"issue":"1","key":"10.1016\/S0010-4485(01)00109-9_BIB40","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/101.17235","article-title":"Simulated annealing algorithms: an overview","volume":"5","author":"Rutenbar","year":"1989","journal-title":"IEEE Circuits and Devices Magazine"},{"issue":"2","key":"10.1016\/S0010-4485(01)00109-9_BIB41","first-page":"151","article-title":"A Branch & Bound algorithm for solving one-dimensional cutting stock problems exactly","volume":"23","author":"Scheithauer","year":"1995","journal-title":"Aplicationes Mathematicae"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB42","doi-asserted-by":"crossref","unstructured":"Schnecke V, Vornberger O. An adaptive parallel genetic algorithm for VLSI-layout optimization. 4th International Conference on Parallel Problem Solving from Nature, 1996.","DOI":"10.1007\/3-540-61723-X_1049"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB43","series-title":"VLSI placement and global routing using simulated annealing","author":"Sechen","year":"1988"},{"issue":"4","key":"10.1016\/S0010-4485(01)00109-9_BIB44","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1080\/09544829608907946","article-title":"A layout design system for complex made-to-order products","volume":"7","author":"Smith","year":"1996","journal-title":"Journal of Engineering Design"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB45","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01759051","article-title":"Efficient simulated annealing on fractal energy landscapes","volume":"6","author":"Sorkin","year":"1991","journal-title":"Algorithmica"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB46","unstructured":"Sorkin GB. Theory and practice of simulated annealing on special energy landscapes, PhD Thesis, University of California at Berkeley, 1992."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB47","unstructured":"Szykman S. Optimal product layout using simulated annealing, PhD Thesis, Carnegie Mellon University, 1995."},{"issue":"2A","key":"10.1016\/S0010-4485(01)00109-9_BIB48","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1115\/1.2826140","article-title":"A simulated annealing approach to three-dimensional component packing","volume":"117","author":"Szykman","year":"1995","journal-title":"ASME Journal of Mechanical Design"},{"issue":"3","key":"10.1016\/S0010-4485(01)00109-9_BIB49","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1115\/1.2826902","article-title":"Synthesis of optimal non-orthogonal routes","volume":"118","author":"Szykman","year":"1996","journal-title":"ASME Journal of Mechanical Design"},{"issue":"1","key":"10.1016\/S0010-4485(01)00109-9_BIB50","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1115\/1.2828785","article-title":"Constrained three dimensional component layout using simulated annealing","volume":"119","author":"Szykman","year":"1997","journal-title":"ASME Journal of Mechanical Design"},{"issue":"3","key":"10.1016\/S0010-4485(01)00109-9_BIB51","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1115\/1.2829180","article-title":"An integrated approach to optimal three dimensional layout and routing","volume":"120","author":"Szykman","year":"1998","journal-title":"ASME Journal of Mechanical Design"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB55","first-page":"29","article-title":"From evolutionary operation to parallel direct search: pattern search algorithms for numerical optimization","author":"Torczon","year":"1997","journal-title":"Computing Science and Statistics"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB56","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1287\/opre.31.3.573","article-title":"Two algorithms for constrained two-dimensional cutting stock problems","volume":"31","author":"Wang","year":"1983","journal-title":"Operational Research"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB57","unstructured":"Wodziak JR, Fadel GM. Packing and optimizing the center of gravity location using a genetic algorithm. Journal of Computers in Industry (in preparation)."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB58","series-title":"Simulated annealing for VLSI design","author":"Wong","year":"1988"},{"issue":"1","key":"10.1016\/S0010-4485(01)00109-9_BIB59","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1115\/1.533550","article-title":"An extended pattern search algorithm for three-dimensional component layout","volume":"122","author":"Yin","year":"2000","journal-title":"ASME Journal of Mechanical Design"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB60","unstructured":"Yin S, Cagan J. Exploring the effectiveness of various patterns in an extended pattern search layout algorithm. Proceedings of the 2000 ASME Design Engineering Technical Conferences. DETC2000\/DAC-14254, Baltimore, MD, 10\u201313 September, 2000."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB61","unstructured":"Yin S, Cagan J, Hodges P, Li X. Layout of an automobile transmission using three-dimensional shapeable components, submitted to ASME Journal of Mechanical Design, also in Proceedings of the 1999 Design Engineering Technical Conferences, ASME, DETC99\/DAC-8564, Las Vegas, NV, 12\u201315 September, 1999."},{"key":"10.1016\/S0010-4485(01)00109-9_BIB62","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1016\/0010-4485(94)90014-0","article-title":"Shape annealing solution to the constrained geometric knapsack problem","volume":"26","author":"Cagan","year":"1994","journal-title":"Computer-Aided Design"},{"key":"10.1016\/S0010-4485(01)00109-9_BIB63","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1068\/b070343","article-title":"Introduction to shape and shape grammars","volume":"7","author":"Sting","year":"1980","journal-title":"Environment and Planning B"}],"container-title":["Computer-Aided Design"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0010448501001099?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0010448501001099?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T18:04:14Z","timestamp":1622225054000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0010448501001099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,7]]},"references-count":59,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2002,7]]}},"alternative-id":["S0010448501001099"],"URL":"https:\/\/doi.org\/10.1016\/s0010-4485(01)00109-9","relation":{},"ISSN":["0010-4485"],"issn-type":[{"value":"0010-4485","type":"print"}],"subject":[],"published":{"date-parts":[[2002,7]]}}}