基于束搜索的三阶段约束排样算法

An algorithm of three-stage constraint nesting based on beam search

基于矩形件三阶段约束排样问题(CTDC),提出基于束搜索的启发式算法优化排样方式、以快速生成同质块三阶段排样方式。采用动态规划确定段的价值。束搜索是一种剪枝的分支定界算法,节点用局部排样方式和余料来表示,对节点的分支,即填充余料。在每一层上选择高潜力的节点作为精英节点做进一步分支,其他节点直接删除不再回溯,这有利于提高算法效率。实验结果表明:算法生成的三阶段排样方式,排样价值高,切割工艺相对简单,且时间相对合理。

Based on three-stage constraint nesting problem of rectangular part,the optimization nesting type of heuristic algorithm based on beam search was set up and the homogeneous three-stage nesting pattern was produced quickly. Then,the stage value was determined by dynamic programming. Beam search was a kind of pruned branch and bound algorithm. The branch node was presented by the partial nesting pattern and the unused leftover. For branch nodes,namely the leftover was filled. On each level,only the elite nodes were allowed to branch further,and other nodes were directly deleted,which were helpful to improve the efficiency of algorithm. The experimental results show that the beam search algorithm provides a nesting of high value,simple cutting processing and reasonable computational time.