A Fast and Efficient Compact Packing Algorithm for SAE and ISO Luggage Packing Problems

Abstract

In this paper, a compact packing algorithm for the placement of objects inside a container is described. The proposed packing algorithm is designed to pack three-dimensional free-form objects inside an arbitrary enclosure such that the packing efficiency is maximized. The proposed packing algorithm can handle objects with holes or cavities, and its performance does not degrade significantly with the increase in complexity of the enclosure or the objects. The packing algorithm takes as input the tessellated geometry of the container and all the objects to be packed and outputs the list of objects that can be placed inside the enclosure. The packing algorithm also outputs the location and orientation of all the objects, the packing sequence, and the packed configuration. An improved layout algorithm that works with arbitrary container geometry is also proposed. Separate layout algorithms for the SAE and ISO luggage are developed. Several heuristics to improve the performance of the packing algorithm are also incorporated. Certain aspects that facilitate fast and efficient handling of the computer aided design (CAD) data are also discussed. A comprehensive benchmarking of the proposed packing algorithm on synthetic and hypothetical problems reflects its superior performance as compared with other similar approaches.