摘要
针对切割下料领域的二维非规则一刀切装箱问题,首先给出了最小移动距离的定义,然后给出了一种基于最大移动距离的启发式算法。该算法通过计算一个凸多边形滑动至另一个凸多边形内部所允许的最大移动距离,对待排件的摆放位置进行一次性定位,避免使用传统的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.
作者
张旭
王莉莉
杨博韬
ZHANG Xu;WANG Li-li;YANG Bo-tao(School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China)
出处
《计算机科学》
CSCD
北大核心
2020年第5期212-216,共5页
Computer Science
基金
国家自然科学青年基金(61602133)。
关键词
启发式算法
一刀切
二维非规则装箱问题
Heuristic algorithm
Guillotine
Two-dimensional irregular bin packing
