基于VNABC的多规格板材二维下料问题

Two-Dimensional Cutting Stock Problem of Multi-Specification Plates Based on VNABC

针对二维下料问题板材单一的特点,研究了多规格板材二维下料问题。板材规格多样、毛坯规格多样且数量庞大,是NP(Non-deterministic Polynomial)完全问题。针对该问题的特点,将下料过程设计成规整和非规整两个阶段。规整阶段完成每种矩形毛坯的主体下料任务之后,如仍有毛坯剩余,则进入非规整阶段采用BL算法(Bottom Left Algorithm)下料剩余毛坯。根据模型特点,提出变邻域人工蜂群算法(VNABC),设计两种解码策略STD和SLD,并改进了VNABC算法的操作算子。最后,采用响应面分析法对VNABC算法进行参数标定。通过仿真实验将VNABC算法与遗传算法(GA)、改进粒子群优化算法(NUS)、模拟退火算法(SA)、人工蜂群算法(ABC)进行了对比分析,实验结果验证了VNABC解决多规格板材二维下料问题的优越性。

Aiming at the characteristic of single sheet metal,the two-dimensional cutting stock problem of multi-specification sheet metal is studied,which is an NP-complete problem,due to the diversity of plate specifications and the large quantity of blank specifications.According to the characteristics of this problem,the cutting process is designed into two stages:regular stage and non-regular stage.After completing the main cutting task for each type of rectangular roughcast in the regular stage,if there is still remaining roughcast,the non-regular stage will be entered and the BL algorithm will be used to cut the remaining roughcasts.According to the characteristics of the model,a variable neighborhood artificial bee colony algorithm(VNABC)is proposed,and two decoding strategies,STD and SLD,are designed.The operator of the VNABC algorithm is improved.Finally,the response surface analysis method is used to calibrate the parameters of VNABC.In the simulation experiments,the VNABC algorithm is compared with GA,NUS,SA,ABC algorithms.The experimental results demonstrate the superiority of VNABC in solving the two-dimensional cutting stock problem of multi-specification plates.