For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The 3D-Packing by Meta Data Structure and Packing Heuristics
Hiroyuki YAMAZAKI Keishi SAKANUSHI Shigetoshi NAKATAKE Yoji KAJITANI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
3D-packing, placement, sequence-pair, sequence-triple, simulated annealing,
Full Text: PDF(826KB)>>
The three dimensional (3D) packing problem is to arrange given rectangular boxes in a rectangular box of the minimum volume without overlapping each other. As an approach, this paper introduces the system of three sequences of the box labels, the sequence-triple, to encode the topology of the 3D-packing. The topology is the system of relative relations in pairs of boxes such as right-of, above, front-of, etc. It will be proved that the sequence-triple represents the topology of the tractable 3D-packings which is a 3D-packing such that there is an order of the boxes along which all the boxes are extracted one by one in a certain fixed direction without disturbing other remaining boxes. The idea is extended to the system of five ordered sequences, the sequence-quintuple. A decoding rule is given by which any 3D-packing is represented. These coding systems are applied to design heuristic algorithms by simulated annealing which search the codes for better 3D-packings. Experimental results were very convincing its usefulness as automated packing algorithms.