A Genetic Algorithm for Packing Three-Dimensional Non-Convex Objects Having Cavities and Holes.

Abstract

In this paper we describe a unique threedimensional bin-packing problem with nonconvex parts having holes and cavities. Parts can be arranged in any orientation and location in the packing cylinder, where parts float like in a weightless environment. The solution approach utilizes a genetic algorithm (GA) which represents a solution for the problem as a three-dimensional chromosome. Each dimension in the chromosome is an ordered list of integers. As a function evaluator we have developed a packing simulator, which utilizes actual CAD file of parts, when packing parts. Part intersection calculations are based on methods common in computational geometry. Keywords: genetic algorithms, 3D bin packing, nonconvex objects, selective laser sintering, rapid prototyping 1 INTRODUCTION 1.1 SELECTIVE LASER SINTERING RAPID PROTOTYPING TECHNOLOGY Like all current rapid prototyping (RP) techniques, the selective laser sintering (SLS) machine produces parts directly from CAD files through an addit...