带有一刀切约束的二维非规则装箱算法  

Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with Guillotine Constraints

作　　者：张旭 王莉莉[1] 杨博韬 ZHANG Xu;WANG Li-li;YANG Bo-tao(School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China)

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机科学》2020年第5期212-216,共5页Computer Science

基　　金：国家自然科学青年基金(61602133)。

摘　　要：针对切割下料领域的二维非规则一刀切装箱问题,首先给出了最小移动距离的定义,然后给出了一种基于最大移动距离的启发式算法。该算法通过计算一个凸多边形滑动至另一个凸多边形内部所允许的最大移动距离,对待排件的摆放位置进行一次性定位,避免使用传统的NFP(Not-Fit-Polygon)预判交方法,极大地缩短了排样的整体时间,最后使用模拟退火算法对下料流程进行了优化,改善了排样结果。Aiming at the two-dimensional irregular packing problem with guillotine constraint in the cutting field,the definition of minimum moving distance is given firstly,and a heuristic algorithm based on maximum moving distance is proposed.The algorithm calculates the maximum moving distance needed for a convex polygon to slide into the interior of another convex polygon.The disposable positioning of the layout position avoids using the traditional NFP intersection method,and simulated annealing algorithm is used to optimize the packing process,which greatly reduces the overall time consumption of layout and meets the high requirements on layout results.

关 键 词：启发式算法 一刀切 二维非规则装箱问题 

分 类 号：TH164[机械工程—机械制造及自动化] TP311[自动化与计算机技术—计算机软件与理论]