MATH and ME faculty engaged in long-term collaboration

December 14, 2015

Packing Optimization of Free-Form Objects in Engineering Design*


Margaret Wiecek, Professor of Mathematical Sciences of the Operations Research (OR) subfaculty, and Georges Fadel, Professor of Mechanical and Manufacturing Systems and ExxonMobil Employees’ Chaired Professor of the Clemson Engineering Design Applications and Research (CEDAR) group, have been collaborating on complex systems design and optimization for seventeen years. They have developed and established Clemson’s expertise in multidisciplinary, multilevel, and multiobjective optimization for engineering design with special interest in automotive design.


Figure 1. CAD representation of the underhood

One part of their research program involves packing for engineering design that involves the development of models and methods to determine the arrangement of a set of subsystems or components within some enclosure to achieve a set of objectives without violating spatial or performance constraints. Packing problems, also known as layout optimization problems are challenging because they are highly multimodal, are characterized by models that lack closed-form mathematical representations, and require expensive computational procedures. The time needed to resolve intersection calculations increases exponentially with the number of objects to be packed while the space available for the placement of these components becomes less and less available. Figure 1 depicts a computer-aided design (CAD) representation of a vehicle underhood to reflect the realism of the underhood packing problem.


Figure 2. Compact packing of boxes in a nonconvex trunk.

Profs. Fadel and Wiecek deal with the packing problem from three different perspectives. The first one is motivated by geometric considerations and does not require optimization. An outer shell or envelope is constructed for each object to be packed while its internal details are ignored. Additionally, an inner shell or envelope is constructed for an enclosure within which the objects are packed. According to the other two perspectives, known as compact packing and noncompact packing, the packing problem is formulated as an optimization problem whose optimal solution is the optimal packing arrangement.



Figure 3. Compact free-form packing with full-rotational freedom in a nonconvex trunk.

Methods for geometric representation of objects have been employed in effective algorithms that convert CAD representations to formats used in the fast calculation of intersections or overlap between objects. These methods have given a foundation for the development of models and algorithms for compact and noncompact packing. The solution approaches to packing problems rely on exact algorithms as well as on heuristic methods whenever the level of complexity precludes development of effective exact algorithms. The developed heuristic algorithms have made it possible to solve very difficult optimization problems once thought intractable.


Figure 4. Nonconpact underhood packing with a water (grey) container in an initial position.

The compact packing consists in placing free-form objects with full rotational freedom inside an arbitrarily shaped enclosure so that the volume of the objects inside the enclosure or their number is maximized. The problem is mathematically represented as a single-objective optimization problem since compactness is the only criterion of interest to designers. Figure 2 depicts an optimal arrangement of rectangular boxes representing a set of suitcases of prescribed dimensions inside a nonconvex trunk space. An optimal arrangement of free-form objects with full rotational freedom is shown in Figure 3.

In noncompact packing, the designers are interested in optimizing other objectives evaluating the performance of packing. In automotive design, in addition to compactness the objectives such as balance, maintainability, and survivability of the vehicle are of interest. The mathematical formulation of the problem assumes the form of a multiobjective optimization problem. In the traditional noncompact packing the shapes of components are fixed prior to the packing process during which only their positions and orientations are optimized. However, the ability of packing with morhpable components, i.e., the components that change their shape while their shape and functional requirements are respected, leads to far better packing arrangements. The effect of a morphing water container is shown in Figures 4 and 5. In Figure 4 the water container starts expanding to attempt to reach a specified volume and occupy the available space. Figure 5 shows a bigger container which slightly affects the location of the other components.


Figure 5. Nonco5mpact underhood packing with a water container expanding to a target volume and filling the avilable space.

Engineering design of a complex system, that is composed of subsystems and components, requires interaction among several engineering disciplines (such as fluid dynamics, thermodynamics, structures, controls, and others) that are involved in the design process of the system. Because system and component designs are typically assigned to independent engineering teams with complementary background and expertise, packing for a distributed or decentralized design process has also been studied.

Figures 6 and 7 depict optimal packings of six components (battery, engine, radiator, coolant reservoir, air filter, and brake booster) within the underhood of a hybrid electric vehicle, while one of these components, the battery, is being designed under demanding thermal criteria. The design process is distributed between two design teams: the vehicle-level team responsible for packing of the underhood and the component-level team who designs the battery. When high importance is assigned to the vehicle level, the battery is placed on the left (the rectangular box in Figure 6). In contrast, when high importance is assigned to the battery level, the battery is not only placed on the right but also changes its shape (the long rectangular box in Figure 7), while the other components also change places due to the different location and shape of the battery. The vehicle performs differently with each packing arrangement.


Figure 6. Noncompact distributed underhood packing with high importance given to the vehicle level.

Drs. Fadel and Wiecek will direct their future research toward more advanced packing problems such as packing with multiple morphable components or with the consideration of wiring, hoses, and pipes. Maintaining the interdisciplinary character of work by integrating engineering and sciences perspective is likely to continue leading them to new significant accomplishments in their future studies on packing optimization.

figure 7

Figure 7. Noncompact distributed underhood packing with high importance given to the battery level.






(*) G.M. Fadel and M.M. Wiecek, “Packing Optimization of Free-Form Objects in Engineering Design,” in Optimal Packings with Applications edited by J. D. Pintér and G. Fasano, Springer, 2015, pp.37—66.