Automated Trunk Packing with Extended Pattern Search

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.