基于NSGA-Ⅱ与A*算法的原竹初加工生产线设施布局研究

廖政洲 刁 燕 李政豪 段必成

（四川大学机械工程学院，四川 成都 610065）

我国是世界上最主要的产竹国，竹类资源和竹类产品的对外贸易量均位于世界首位。预计到2030 年，我国竹产业总产值将达到一万亿，竹产业发展前景巨大[1]。竹材在经过一定处理后可代替木材[2]，能减少碳排放稳定气候，降低森林火灾发生风险[3]。竹类产品品种丰富，有工业产品以及各种家具[4]艺术品，其加工设备也层出不穷[5-6]，如智能化的分选剖竹设备[7]。在生产线设计方面，宋菲菲[8]以产能匹配为核心理念，设计了重组竹生产线。龚正等[9]设计了重组竹竹方冷压装料自动化生产装置[10]。周涵誉[11]建立了小型竹砧板柔性自动生产线。然而，针对原竹生产线布局的研究文献很少，现有的布局方法主要是在U型、直线型和混合型基础上进行修改或使用SPL（系统布局规划）。对加工制造企业来说，整个生产环境运营费用的20%～50%为物流费用，而精细布局能减少物流费用，并提高生产效率。在实际工厂中，往往根据经验来进行布局，没有经过详细的计算，其物流路线长、运输路径干涉多、效率低。因此，对原竹初加工生产线进行布局优化很有必要。

SPL是专门应用于平面规划的一种传统方法，在布局优化问题中应用广泛[12-13]。该方法需要人工分析物流和非物流因素，从而排布设备位置，过程繁琐，多受主观因素影响。随着计算模型的复杂化，SPL的效果不佳。目前，研究多采用智能算法来解决布局优化问题。汪和平等[14]利用人工蜂群算法对预制件厂生产布局进行了优化。谭健[15]使用遗传算法对凸轮轴生产线进行了布局优化。葛晓梅等[16]使用改进的遗传算法，对钢构件车间进行了布局优化。张一飞[17]针对翅片式蒸发器生产线的布局问题，将遗传退火算法结合SPL进行了优化。Pourhassan等[18]研究了动态布局优化问题，运用NSGA-Ⅱ算法进行优化。曾强等[19]也利用NSGA-Ⅱ算法对车间布局进行了优化。Guan等[20]建立了车间内部和外部车间布局的综合优化模型，并采用多目标粒子群优化算法进行整体布局优化。

目前研究都是根据不同生产线的特点，建立具体的数学模型，设计智能算法来进行布局优化。原竹初加工生产线具有以下特点：1）每个工序机器大小不同，是不等面积的布局优化问题；2）原竹加工生产线将趋于智能化，运输路径干涉对生产线搭建和运营有严重影响，减少干涉势在必行。针对不等面积问题，可以建立独特的数学模型。针对运输路径干涉的问题，则可以采用A*算法规划运输路径，判断路径干涉。在之前的研究中，计算设备之间运输距离多采用曼哈顿距离[21]。相比而言，A*算法可以避免其计算路径过长和无法考虑障碍的缺陷。同时，NSGA-Ⅱ在求解多目标问题时表现出色。综上，本文采用A*算法计算物料运输成本和运输路径之间的交叉干涉，并结合NSGA-Ⅱ算法进行优化，进而输出PO前沿和布局方案。

1 生产线模型构建

1.1 生产工艺分析

如图1所示，原竹初加工工艺流程主要为原竹、截断、分选、开条[22]。截断部分由锯竹机完成，分选部分由自动化的传送带和视觉识别模块完成，开条工艺由自动换刀的剖竹机完成。为了保证整个生产过程中的物料流通顺畅，在截断和开条中间增加半成品储料区进行缓冲，并根据生产情况来确定设备数量。

图1 加工工艺流程图Fig.1 Primary processing process of bamboo

1.2 数学模型建立

根据原竹初加工生产线和A*算法特点建立设备布局的数学模型。做出如下假设：1）每个设备和车间均为长方形且两边已知；2）每个设备摆放好后，其边与车间墙壁平行；3）运输起止点为设备质心，运输路径不能与其他设备干涉；4）将整个车间划分为单位长度为e的网格，设备的质心和边长需落在网格上。

原竹初加工的场地和设备都近似于长方形，且设备一般与墙壁平行放置，满足1）和2）两条假设。为了方便路径规划，避免运输时与设备碰撞，做出假设3）。A*算法是用离散节点来搜索物料运输路径的，需将空间网格化且设备落在节点上，即为假设4）。

布局示意图如图2 所示。车间长为L，宽为H。设备位置由质心坐标确定。设备i的质心坐标为（xi，yi），x轴方向长为Li，y轴方向长为Hi。

图2 布局示意图Fig.2 Representation of the layout

由于原竹初加工生产线设备多为长方形，因此设备有两种摆放方式，分别横放和竖放，如图3所示。摆放方式也会影响优化结果。引入一个0、1变量z来记录摆放方式。设备b较长边为Xb，较短边为Yb。摆放后设备b的Lb，Hb按式(1)计算：

图3 同一设备两种摆放方式Fig.3 Tow placement methods of the same equipment

式中：当z=1时为横放，当z=0时为竖放。

1.3 优化目标确定

原竹初加工生产中，物料运输成本占生产运营成本的20%～50%。同时，运输路径干涉也会使得生产线建设和维护成本上升。因此，优化目标如式（2～3）：

式中：MHC为物料运输成本；i和j为设备编号；N为设备总数；pij是一个0、1变量，表示是否有i到j的物料运输操作；cij表示由i运输到j单位距离的运输成本；A*ij表示由A*算法计算出的i和j之间的物料运输距离。OL为运输路径干涉交叉点总和，表示运输路径干涉；a、b表示路径编号；M为路径总数；olab为路径a和b之间的交叉点个数。因此，本研究的优化目标位减小MHC和OL。

A*算法所规划的路径存在3 种交叉方式，如图4所示。节点和中点重合记为交叉点，起点终点不计算。1 和2 有1 个，3 有3 个。

图4 不同交叉形式Fig.4 Three crossing modes

Horta等[23]研究了在同一条件下对于MHC和物流干涉两个目标分别优化的问题，证明了两者是相互冲突和矛盾的，是一个多目标优化问题。

1.4 约束条件

为了模型接近现实，考虑实际情况，结合算法特点总结出以下约束条件。

1）设备与车间墙面约束

式中：s为与墙面的最小间距，m。Li和Hi由式（1）计算出。不紧靠墙壁方便原竹加工设备维护。

2）设备间距离约束

式中：Δx、Δy表示在横纵坐标方向上的设备间距要求。设备间的距离保证原竹加工过程中的人员物料流动顺畅。

3）设备位于网格上约束

式中：e为网格单元长度，m，n为正整数。当设备所有边长都为e的偶数倍时，质心才有可能在网格点上。确保模型满足假设4的要求。

2 基于NSGA-Ⅱ和A*的带运输路径规划的多目标布局优化算法

2.1 NSGA-Ⅱ和A*算法原理分析

NSGA-II算法结构简单且在大部分的测试问题上表现出色。算法核心在于它的环境选择和交配选择。环境选择部分，采用分层策略搜寻PO最优解，同时定义了个体拥挤度，保留那些稀疏个体，使得求得的PO解集更加均匀和全面。交配选择方面使用锦标赛法[24-25]。

A*算法是一种全局路径算法，能在障碍物已知的情况下，在平面上找到一条能避开障碍物的较短路径。它将整个平面离散化为网格节点，从起始点出发，通过代价函数判断最优的下一个路径节点，不断延伸通往终点，找到一条能躲避障碍的最佳路径[26-27]。

2.2 算法过程

算法以NSGA-II算法为理论基础，根据数学模型进行修改。利用罚函数来去掉不满足约束的解。使用A*算法规划运输路径从而得到目标值，具体的优化过程如图5所示。

图5 优化算法流程图Fig.5 Optimization algorithm flowchart

整个算法的关键在于将A*算法和NSGA-II算法完美融合，利用A*算法来对优化过程中的每一个个体来进行物流路径的规划从而得到目标值，又不影响原算法计算。同时，算法是多目标优化算法，相较于加权方法有着更多的解、更好的结果。关键点如下：

1）使用A*算法与罚函数相结合的方式计算目标值。先用罚函数f1(A)、f2(A)来计算约束1）、约束2）的罚函数值，A为个体矩阵。当两者都为0，则用A*算法规划运输路径并计算两目标值。否则为不满足约束，使用式（8）和式（9）计算两目标值，其远大于正常值从而在后续迭代中被淘汰。α、β为惩罚因子。

2）解决A*算法嵌入后对算法影响。网格化操作导致目标值重复的个体增加。为了避免重复，计算目标值后去除部分重复目标值个体，个体数不足时则生成新个体补足。为了提高搜索效率，初始生成的是可行个体。

2.3 编码规则

采用3×N的矩阵来存个体数据。如式（10）所示，一二两行存放质心横纵坐标，第三行存放z变量。

2.4 杂交变异操作

1）杂交方法

随机生成一个1到N-1的自然数r。将父本1前r列和父本2的前r列交换得到两个子代。如图6所示。

图6 交叉示意图Fig.6 Cross operation

2）变异方法

移动：随机生成1到N的两个不同自然数r1、r2，e整数倍的d1、d2、d3、d4，大小在正负30倍之间。将父代r1列一、二行依次加上d1，d2，r2列一、二行依次加上d3、d4得到新的子代。如图7所示。

图7 移动示意图Fig.7 Move operation

改变摆放方式：随机生成一个1到N的自然数r，将父代的r列的第三行的数zr替换为,其中按式（11）计算，变异得到新的子代。如图8所示。

图8 变向示意图Fig.8 Change the placement method

交换：随机生成1到N的四个不同自然数r1、r2、r3、r4，将父代的r1、r3列和r2、r4互换变异得到新的子代。如图9所示。

图9 交换示意图Fig.9 Exchange operation

3 实例演算

3.1 输入数据

以某原竹初加工生产线车间的设备来进行实例演算。该车间L为30 m，H为30 m，单位网格长度e为0.1 m。根据产能平衡原理及节拍要求，需要2台锯竹机、4台剖竹机和3个储料仓库。具体的长宽数据如表1所示，原始布局个体如式（12）所示。设备间距离约束和设备与墙面距离约束的参数分别为s=1 m，Δx=Δy=1 m。物流关系如图1所示，单位距离物料运输成本记为1。

优化算法的相关参数如下：种群大小N=26，最大 循 环 次 数T=600。惩 罚 因 子α1=β1=1 000 000、α2=β2=1 000。在优化初期，需要较高的全局搜索能力。较高的杂交概率可以实现这个目的。优化的末期，需要较高的局部搜索能力来使得个体能更快收敛，并且这时过高的杂交概率会产生大量重复个体。在优化末期提高变异概率。当循环代数t＜300 时，杂交概率pSwap=0.75、移动概率pMove=0.1、改变摆放方式概率pT=0.05、交换概率pR=0.1。当循环代数t＞=300 时，杂交概率pSwap=0.25、移动概率pMove=0.4、改变摆放方式概率pT=0.15、交换概率pR=0.2。

3.2 优化结果分析

优化后的PO前沿如图10 所示。图中星形红点表示个体，算法计算出PO前沿分布较为均匀，个体之间的间距相似。个体不集中于一个小型区域有着较好的多样性。

图10 PO前沿Fig.10 PO front

原布局方案如图11 所示，优化后个体的位置及运输路径如图12 所示。个体1、2、3、4、5 分别对应：图12a、12b、12c、12d、12e。图名为两优化目标值，MHC单位为m，OL单位为个。图中坐标单位长e，设备之间的线为规划的物料运输路径。优化后与优化前相比，所得到的60%的PO前沿解在两个目标值上都优于原方案，所有解都有比原方案更优的目标值。优化结果中，MHC最小的个体比原方案的减少了10.5%，OL最小的个体仅有原方案的2.5%。由此可以看出，优化结果远胜于原方案，说明优化算法是有效的。在实际生产设计时，可根据实际情况在PO前沿中优选个体。

图11 原布局方案图(MHC 113.94 m OL 200)Fig.11 Original layout plan(MHC 113.94 m OL 200)

图12 PO前沿个体布局图Fig.12 PO frontier individual layout

由图12e中设备4 和设备5 之间的运输路径可以看出，使用A*算法求解出的路径可以解决曼哈顿距离中路径长度无法跨越障碍的问题。由表2 可以看出，在PO前沿个体中，A*算法计算出的MHC都比曼哈顿距离计算的MHC低，平均低18.1%。使用A*算法对运输路径进行规划，更能模拟实际情况，计算的MHC更加的精确且更低。由此可见，运用A*算法来计算优化目标比传统的曼哈顿距离更好。

表2 两种距离算法对比表Tab.2 Comparison of two different calculation methods

4 结论

本文通过将A*算法和NSGA-Ⅱ算法相结合，设计出一种新型算法来对原竹初加工生产线设施布局进行多目标优化。优化后，60%的PO前沿个体其两个目标值都比原方案好，所有个体都有比原方案更好的目标值。MHC最小的个体比原方案的减少了10.5%，OL最小的个体仅有原方案的2.5%，进一步证明了该优化算法切实可行。算法生成的PO前沿可以供实际原竹初加工生产线选择。

采用A*算法计算的物料运输成本会比曼哈顿距离计算出的平均低18.1%，可进一步降低原竹初加工生产线的物料运输成本。同时，还解决了曼哈顿距离中路径长度无法跨越障碍和运输干涉无法判断的问题，能够更好地模拟原竹初加工生产线的实际情况。