基于遗传算法和线性规划的快递包装盒下料问题研究

矩形切割问题是二维切割一个重要研究方向，怎样实现木材最优化切割，使木板的利用率达到最高，是工业生产的重要课题。近几年来，随着传统算法的发展，各种智能算法的不断完善着矩形切割的方案。而本文是利用遗传算法探究在一块木板上的二维下料问题。

一、单一木板切割模型的建立

仅含一种约束条件:假设对-一个长为3000mm、宽为1500mm的矩形木板进行切割，需要得到n个矩形原件P1 (长为373mm宽为201mm)。不考虑木板的厚度，怎样切割才能得到最多的矩形原件P1,实现木板的利用率最大化呢？

木板利用率与切割出的小矩形的数量成正相关。依据运筹学中的整数规划问题，可将切割问题分为横向切割和纵向切割两种方案。由于斜向切割会造成原料的滥用且讨论情况更复杂，所以不采用斜向切割的方式。通过构建线性规划方程组，以木板的长、宽为限制条件，得出使木板材料剩余面积最小的方案。

根据木板的排放方式，建立整数规划方程组:

式中:木板的长与宽分别为L、W；P1原件的长与宽分别为11、w1；m表示将P1原件的宽w1沿着木板的L方向排列的个数；b指P1原件的长11沿着木板的W方向排列的个数。运用LINGO软件对方程组求解得: m=13，n=1，a=0，b=4. 即目标值z=44888，但并不是最优方案。

分析求解结果得，P1原件的宽沿着木板的长排列最多可排13列；

P1原件的长沿着木板的宽排列最多可排4行。此时木板的长边剩余387mm，宽边剩余8mm，所以可再放置一个P1原件的长边。故仍可以排放7个P1原件。综上所述，在木板上切割P1原件时，当切割59个P1板时，木板利用率为98.3%，达到最高利用率。

二、多元木板切割模型的建立

两种约束条件的切割方案:现多考虑-一个矩形原件P3 (长度为406mm，宽为229mm) 。由于矩形原件P3的切排样方式不定，加深求解的难度。针对NP类问题可建立有关遗传算法的数学模型进行求解。

構建一个函数: k (x) =1x0 0x<0 (1)

由于切割原件在排放时受到木板尺寸的影响，且每个原件之间的排放互不重叠，依此建立如下方程:

k (xli-xrj) +k (yti-ybj) +k (xlj-xri) +k (ytj-ybi) 1 (2) 式中:第i个原件排放在第j个原件后面，且i(1)遗传算法的建立:

首先初始化种群，对各个矩形原件采用符号编码，将两种原件命名为1、2。原件既可横排也可竖排，取横排为正，竖排为负。下面以P1、P3原件在长为635mm， 宽为610mm的木板上的排放为例，p={1,1，

2, 2}表示底层竖排一个原件P1，再横排-一个原件P1，第二层先横排一个原件P3，再竖排-一个一个原件P3。

其次构建适应度函数。将木板利用率作为函数，得到适应度函数方程:

H (p) =h (p) LW=∑niliwiLW (3)

式中: H (p)表示算子，指编码为p的个体的面积，ni为标号为i的原件的出现次数，li、 wi分别表示标号为i的原件的长与宽(这里.的i与方程(4)约束条件中的i有区别)。其余参量均取默认值。

(2)初始化种群的构建:

由于初始化种群的编码较多，一般初始种群的大小要在20个以上，可采用逐层排列生成初始化种群。

步骤一:建立-一个坐标系，确定上限宽度与长度(即木板尺寸) 步骤二:生成一个随机序列数，取值在集合{2，1, 1，2}内，表示

待排样的原件。

步骤三:根据随机数，将木块从左往右按层排列。

步骤四:当排样高度达到宽度限度时，跳出循环，给出排列编码。 步骤五:重复上述步骤，直至给出20个以上的初始个体，构建成一个初始化种群。

(3)模型的求解:

运用MATLAB实现遗传算法，可得三种利用率较高的方案:在实际生产中，所需原材料的种类是多样的(不仅限于矩形)，求解情况更加

复杂。对于多种约束条件，仍然利用遗传算法，加入新的约束条件，对适应度函数进行改造。

H (p，N) =h (p) NLW=∑niliwiNLW P=P{p1，p2，.，. pn} (4)

式中: ni是已知量，N是待求解量。然后改造初始化种群，对所加的参数Ci对原件进行计数，引入参数N对木板计数。合并每个板的编码排序，一个板组成一一个编码，原件全部排完时构成P。进一步对初始种群改造，再次建立坐标系。

三、评价与总结

本文构建的模型中没有给出具体的解码算法和筛选算法，另外遗传算法也的稳定性较差，因为算法属于随即类算法，对初始种群有很强的依赖性，不同的初始种群得到结果与速度也不尽相同。可采用模拟退火算法和蚁群算法相结合，当面临实际解决时，可以通过构建这两个算法解决人力解码的问题。