This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
Automated Trunk Packing with Extended Pattern Search
Technical Paper
2003-01-0671
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
Automobile trunk packing is an instantiation of the general 3D product layout problem. The problem is difficult to solve because of the multi-modal and discontinuous characteristics of the layout space configuration. Moreover, the trunk packing problem has unique special properties: First it requires very tight packing. Second, based on Society of Automotive Engineers (SAE) specifications, a subset of potential components must be selected to optimize trunk space usage without having component overlap. In this work, the Extended Pattern Search algorithm is chosen as the optimization technique. To address these properties and create a time-efficient algorithm, a number of extensions were made to the basic technology: 1) selecting components based on probabilities, 2) adding more degrees of freedom, 3) swapping components in and out of the trunk. These extensions reduce the volume penalty function by over an order of magnitude compared to previous computational approaches and thereby achieve physically feasible trunk stackings. As well the method reduces packing time by one to two orders of magnitude over manual stacking efforts.
Recommended Content
Ground Vehicle Standard | Motor Vehicle Dimensions |
Technical Paper | Multi-Disciplinary Robust Optimization for Performances of Noise & Vibration and Impact Hardness & Memory Shake |
Technical Paper | Side Window Buffeting Characteristics of an SUV |
Authors
Citation
Ding, Q. and Cagan, J., "Automated Trunk Packing with Extended Pattern Search," SAE Technical Paper 2003-01-0671, 2003, https://doi.org/10.4271/2003-01-0671.Also In
References
- Beasley, J.E. 1985 “An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure,” Operational Research 33 49 65
- Bischoff, E.E. Marriott, M.D. 1990 “A Comparative Evaluation of Heuristics for Container Loading” European Journal of Operational Research 44 2 267 276
- Cagan, J. Degentesh, D. Yin, S. 1998 “A Simulated Annealing-based algorithm using hierarchical models for general three-dimensional component layout” Computer Aided Design 30 10 781 790 1998
- Cagan, J. Shimada, K. Yin, S. 2000 “A Survey of Computational Approaches to Three-dimensional Layout Problems” Computer Aided Design
- Campbell, M. 2000 “The A-Design Invention Machine: A Means of Automating and Investigating Conceptual Design” Carnegie Mellon University
- Cohoon, J.P. Paris, W.D. 1986 “Genetic Placement,” Proc. of IEEE Int. Conf. On CAD 422 425
- Dai, Z. Cha, J. Yuan, J. 1994 “An Octree Based Heuristic Algorithm for 3-D Packing,” Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference 2 125 133
- Dai, Z. Cha, J. 1994 “An Octree Method for Interference Detection in Computer Aided 3-D Packing,” Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference 1 29 33
- Dai, Z. Cha, J. “A Hybrid Approach of Heuristic and Neural Network for Packing Problems,” Advances in Design Automation 1994: Proceedings of the 20th ASME Design Automation Conference 2 117 123
- Dickinson, J. Knopf, G. 1998 “Serial packing of arbitrary 3D objects for optimizing layered manufacturing” Proceedings of the 1998 Conference on Intelligent Robots and Computer Vision XVII: Algorithms, Techniques, and Active Vision Nov 2-3
- Dowsland, K.A. Dowsland, W.B. “Packing Problems,” European Journal of Operational Research 56 2 14
- George, J.A. Robinson, D.F. 1980 “A Heuristic for Packing Boxes into a Container,” Computers and Operational Research 7 147 156
- Hooke, R. Jeeves, T.A. 1961 “Direct Search Solutioin of Numerical and Statistical Problems,” Journal of the Association for Computing Machinery 8 2 212 229
- Hustin, M.D. Sangiovanni-Vincentelli, A. 1987 “TIM, a New Standard Cell Placement Program Based on the Simulated Annealing Algorithm,” IEEE Physical Design Workshop on Placement and Floorplanning
- Kolli, A. Cagan, J. Rutenbar, R.A. 1996 “Packing of Generic, Three Dimensional Components Based on Multi-Resolution Modeling,” Proceedings of the 22nd ASME Design Automation Conference (DAC-1479) Irvine, CA August 19 22
- Landon, M.D. Balling, R.J. 1994 “Optimal Packaging of Complex Parametric Solids According to Mass Property Criteria,” Journal of Mechanical Design 116 375 381
- Mortenson, M.E. 1997 Geometric Modeling John Wiley & Sons, Inc.
- Rutenbar, R.A. 1989 “Simulated Annealing Algorithms: An Overview,” IEEE Circuits and Devices Magazine 5 1 19 26
- SAE 1993 SAE Recommended Practice, J1100 June “Motor Vehicle Dimensions”
- Scheithauer, G. Terno, J. 1995 “A Branch & Bound Algorithm for Solving One-Dimensional Cutting Stock Problems Exactly,” Aplicationes Mathematicae 23 2 151 167
- Schnecke, V. Vornberger, O. 1996 “An Adaptive Parallel Genetic Algorithm for VLSI-Layout Optimization,” 4th Int. Conf. on Parallel Problem Solving from Nature
- Sechen, C. 1988 VLSI Placement and Global Routing Using Simulated Annealing Kluwer Academic Publishers Boston
- Smith, N. Hills, W. Cleland, G. 1996 “A Layout Design System for Complex Made-to-Order Products,” Journal of Engineering Design 7 4 363 375
- Szykman, S. 1995 Optimal Product Layout Using Simulated Annealing Carnegie Mellon University
- Szykman, S. Cagan, J. 1997 “Constrained Three Dimensional Component Layout Using Simulated Annealing,” ASME Journal of Mechanical Design 119 1 28 35
- Torczon, V. Trosset, M. 1997 “from Evolutionary Operation to Parallel Direct Search: Pattern Search Algorithms for Numerical Optimization” Computing Science and Statistics 29
- Wodziak, J.R. Fadel, G.M. 1994 “Packing and Optimizing the Center of Gravity Location Using a Genetic Algorithm,” Journal of Computers in Industry
- Wong, D.F. Leong, H.W. Liu, C.L. 1988 Simulated Annealing for VLSI Design Kluwer Academic Publishers Boston
- Yin, S. 2000 “A Computational Framework For Automated Product Layout Synthesis Based on an Extended Pattern Search Algorithm” Carnegie Mellon University
- Yin, S. Cagan, J. 2000 “An Extended Pattern Search Algorithm for Three-Dimensional Component Layout” ASME Journal of Mechanical Design 122 1 102 108
- Yin, S. Cagan, J. 2000 “Exploring the effectiveness of various patterns in an Extended Pattern Search layout algorithm” Proceedings of the 2000 ASME Design Engineering Technical Conferences: Design Automation Conference, DETC2000/DAC-14254 September 10-14 Baltimore, MD
- Yin, S. Cagan, J. Hodges, P. Li, X. 1999 “Layout of an Automobile Transmission Using Three-Dimensional Shapeable Components” Proceedings of the 1999 Design Engineering Technical Conferences, ASME, DETC/DAC-8564 Las Vegas, NV September 13-16