求解二维正交矩形布局问题的动态填空启发式算法  

Dynamic fill blank heuristics algorithm for solving 2D orthogonal rectangular packing problem

作　　者：孙宝金[1] 贺良华[1] 

机构地区：[1]中国地质大学自动化学院,武汉430074

出　　处：《计算机应用研究》2017年第6期1685-1689,1703,共6页Application Research of Computers

摘　　要：为更高效解决二维正交矩形布局问题,建立该问题的数学模型,改进BL算法规则;为寻找布局过程中的空余平面,建立了新颖的图形矩阵化理论。最后提出一种动态填空(DFB)启发式算法,制定了四条动态调整机制,结合遗传算法对该问题进行求解。大量算例测试显示,DFB算法可达到100%的平面利用率,极大地提高了BL算法的效率,并且可以适用于大规模布局问题。In order to solve the 2D orthogonal rectangular packing problem more effectively, this paper established a mathematical model of the problem to improve the rule of BL algorithm. For finding the spare plane during the packing progress, it created a new graphic matrixed theory. At last, it proposed a dynamic fill blank （DFB） heuristic algorithm and developed four dynamic adjustments mechanism to solve the problem combined with genetic algorithms. Numerous examples show the DFB algorithm can achieve 100% plane utilization, greatly improve the efficiency of the BL algorithm, and can be applied to largescale packing problem.

关 键 词：二维正交矩形布局 动态填空 启发式算法 图形矩阵化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]