填充启发式算法的二维矩形排样问题

›› 2011, Vol. 24 ›› Issue (1): 50-.

填充启发式算法的二维矩形排样问题

杨彩君,张玉萍

(上海师范大学信息与机电工程学院,上海 200234)

出版日期:2011-01-15 发布日期:2010-12-30
作者简介:杨彩君(1984-),女,硕士研究生。研究方向:计算机辅助设计。

A Filling Heuristic Algorithm for the Two-dimensional Rectangle Packing Problem

YANG Cai-Jun, ZHANG Yu-Ping

(College of Mechanical and Electronic Engineering,Shanghai Normal University,Shanghai 200234,China)

Online:2011-01-15 Published:2010-12-30

摘要/Abstract

摘要：

针对小矩形切割的二维排样问题,尤其是对玻璃或厚钢板等材料,在切割时定向一次性切割到头的排布,结合综合蚂蚁算法和模拟退火算法思想,提出了一种最低水平线与填充式算法相结合的启发式排样算法。通过对计算机上随机产生的实验数据进行模拟,实现了自动排样。实验表明,该算法提高了单次切割的材料利用率,得到较好的排样效果。

关键词: 排样, 矩形件, 启发式, 填充式算法

Abstract:

The packing problem of cutting the optimal layout of small rectangles on a pallet is considered.Combining the ant algorithm with the simulated annealing algorithm,a mixed new algorithm of layout optimization,which is implemented by the lowest horizontal and filling algorithm,is proposed in this paper.In order to investigate the computation,numerical tests with randomly generated instances are carried out.By comparison,the solutions show the robust effectiveness of this approach.The results show that this approach achieves a better effect.

Key words: packing problem;rectangle;heuristics;filling algorithm

中图分类号:

TP301.6

杨彩君, 张玉萍. 填充启发式算法的二维矩形排样问题[J]. , 2011, 24(1): 50-.

YANG Cai-Jun, ZHANG Yu-Ping. A Filling Heuristic Algorithm for the Two-dimensional Rectangle Packing Problem[J]. , 2011, 24(1): 50-.

[1]	夏倩,张晓龙. 一类0-1背包问题的启发式网络策略模型与算法[J]. , 2014, 27(10): 71-.
[2]	郭瑞峰,叶艳. 改进的临界多边形生成算法[J]. , 2014, 27(10): 107-.