摘要
长方体布局问题属于NP完全问题,在串行机上解决这类问题只能依赖启发式算法。本文提出了一种对布局空间进行动态分解和对剩余空间进行合并和再利用的启发式算法。分解过程采用三叉树数据结构表示,深度优先原则搜索,根据一定的定序规则和定位规则快速求得问题的满意解。同时针对影响布局结果的"难布置的布局物体",设计剩余空间的合并规则,达到该类物体的布入,并通过算例说明了本算法的有效性,对长方体布局具有一定的指导意义,也为人机结合的优化布局提供了良好基础。
Threedimensional bin packing problems are categorized as NPcomplete problems, which can be solved only by heuristic algorithms. In this paper a heuristic method based on dynamic space decomposition and merging of empty space is proposed. The packing space is expressed by the tritree structure and is searched by the depthfirst rule. According to the appointed sequential rule and positional rule, the optimal packing result can be obtained quickly. The rule of merging empty space is specified to pack the 'awkward packing objects'. The conclusion drawn from the experimental study is meaningful and useful to the threedimensional bin packing.
出处
《铁道学报》
EI
CAS
CSCD
北大核心
2003年第6期8-13,共6页
Journal of the China Railway Society
基金
国家自然科学基金资助项目(500750002)
关键词
布局
启发式算法
空间分解
packing
heuristic algorithm
space decomposition
