改进邻域搜索算法的矩形件排样优化研究

Optimal Rectangle Packing Based on Improved Neighborhood Search Algorithm

针对矩形件排样问题,给出精确的数学优化模型,提出一种改进邻域搜索算法的求解方法.为了克服一般邻域搜索算法易陷入局部最优解和搜索效率低的缺点,挖掘矩形件排样的问题特征,提出反悔算子、距离受限邻域算子、以“满足容忍度”接受劣解等3种新的改进策略.以矩形件排放顺序为编码,利用“最下左填充算法”进行解码,优化矩形件排样方案.对文献中的12个经典案例进行计算,通过对不同算法的计算结果进行比较和分析,改进邻域搜索算法具有明显优势,平均板材利用率能达到98.1%,表明了所提算法的有效性.

For the rectangle packing problems,an exact mathematical optimization model was presented.And an improved neighborhood search algorithm was proposed to overcome the weakness of the traditional neigh⁃borhood search,which is easily falling into the local optimal solution and has low efficiency.Based on the char⁃acteristics of the rectangle packing problems,three new improved strategies are proposed,namely,the pulling back operator,the distance⁃restricted neighborhood operator,and the acceptance of the inferior solution by“sat⁃isfying the tolerance degree”,to enhance the performance of the neighborhood search algorithm.The order of rectangles to be packed is used for encoding and the bottom⁃left filling algorithm is used for decoding.Some com⁃putational experiments with 12 cases from literatures show that the improved neighborhood search algorithm can generate 98.1%utilization rate on average.And the comparison and analysis of the computational results of dif⁃ferent algorithms show the advantages and efficiency of the proposed algorithm.