飞机制造物流问题的约束多目标优化算法研究

王鹏，谭杭波

无锡雪浪数制科技有限公司，江苏无锡，214131

0 引言

航空工业是反映一个国家综合国力和军事实力的战略性高科技产业。它是国防建设和航空运输的物质基础，对国家经济、社会发展和技术创新具有重要意义[1]。航空工业的快速发展加速了技术进步和产业升级，促进了国民经济和就业增长，并为国家安全和国防能力建设提供了坚实的支撑。航空工业是一个高端技术聚集的领域，具有技术密集、高度综合和广泛协同的特点，并是多品种、小批量和离散制造的典型代表[2]。

近年来，航空制造业面临着越来越短的开发周期、越来越高的交付质量要求以及不断增长的新产品需求的巨大压力[3]。目前的协同制造模式，主机和配套厂商信息相对滞后，缺乏科学、系统、集中化的仓储和物流管理系统。首先，由于统计和账户信息不清晰，仓库无法及时获取准确的物料库存信息，从而无法很好地组织生产。其次，缺乏科学有效的存储设施和运输设备，使物流时效性的预测成难题，结果造成大量资源浪费和成本上涨。更为严重的是，它阻碍了生产效率提高，并导致无法按时交货，使协同制造模式难以满足生产需求或成功完成开发任务[4]。

信息技术的不断发展为信息网络化和智能技术带来了新的视角，并出现了各种自动化仓储和运输设备[5]。空客和波音将物联网射频识别技术应用在供应链、飞机制造、仓储和售后管理等方面，以更好地识别、跟踪和监控实际情况[6]。

尽管当前的解决方案仅仅通过信息技术手段实现了航空制造企业内部所有环节的数据循环，但企业间的信息仍处于封闭孤立状态，不同设备、不同站点和不同车间之间仍存在许多信息孤岛。目前，由于航空企业信息技术水平不高造成的壁垒已成为供应链和生产流程中的一个巨大障碍。由于信息基础薄弱，生产过程中的信息传递和流通经常会中断，从而导致信息无法持续且及时传递。另外，信息流和物流之间的不同步引入了物料等待、仓库积压等问题，严重影响物流效率。因此，如何有效地预测物流是亟待解决的问题[7]。

为了更好地解决上述问题，研究发现基于PLC控制立体仓库[8]、烟叶复烤生产流程[9]等均引入自动导引车（AGV）技术，故对航空航天制造厂、仓库、配送中心和传输终端引入了基于AGV的内部车辆运输系统，以提高物流效率和精度，即AGV系统。AGV系统的设计和控制过程涉及导引路径设计、所需车辆数量的估计、车辆调度、空闲车辆定位、电池管理、车辆路由和锁死解决等多方面。特别是，指导路径设计是一个战略级问题，此级别的决策对其他级别的影响很大[10]。飞机制造是一个复杂的工程问题，涉及装配前[11]的许多工艺、材料和半成品，本文重点关注使用AGV系统运输作业车间使用的材料和半成品的物流问题。

相关物流问题在文献[12]中被建立为一个单目标优化模型，该模型考虑了一些特殊因素，将各种相关的关注点包含在一个单一的目标函数中。此外，为了提高飞机制造的能源效率，还考虑了AGV的最优速度，验证了该优化模型比许多其他优化模型更为有效。尽管如此，在多因素和约束条件之间很难达到平衡，只能得到单一的解决方案，没有任何替代方案。因此，本文建立了一个有约束的多目标优化模型用于航空制造物流问题，旨在同时优化多个目标并满足多个约束条件。为了建立优化模型，采用了许多先进的约束多目标元启发式算法，以获得满足所有约束条件并在目标之间进行多样化权衡的多种解决方案。实验结果表明，该方法比现有方法表现更好。

1 问题模型

飞机制造车间通常位于巨大的空间内，需要将大量材料和半成品从仓库运输至生产线上的组装点。借助自动化技术和信息技术，飞机制造车间正变得越来越智能化，常使用配备物联网设备的自由导航AGV[11]来处理运输任务。尽管如此，这样的物流问题并不简单，因为需要考虑到许多限制和成本，例如仓库的最大容量约束、在仓库存放材料和半成品的成本、AGV处理运输任务的运输成本、能源消耗成本、运输时间成本等。这些考虑高度依赖于仓库的位置、AGV运输时的速度以及仓库服务的组装点，需要充分优化以提高效率。

在文献[12]中，已经提出了一种使用AGV来解决飞机制造物流问题的优化模型，但在实际应用中存在一定的局限性。首先，该模型考虑到了仓库位置和AGV速度的优化，但忽略了哪些仓库需要由哪些组装点服务的问题。其次，该模型涉及四个按用户定义的权重系数合并的优化目标，从而将其转化为单一目标优化问题。然而，在实际场景中，不同的生产车间可能随时间变化而有不同的需求，多个目标的聚合无法满足不同场景中的不同需求。此外，通过经验很难确定最优权重系数。因此，在本文中，我们构建了一个更为精细的优化模型，将各个目标分别处理，并对更多的变量进行优化。

1.1 编码方案

鉴于不同情境下装配点的仓库数量和位置存在差异，本文提出的模型中，第一部分决策变量是为m个装配点选择n个仓库的位置。此外，考虑到每个仓库的服务能力有限，需要将每个仓库服务的装配点指标作为第二部分决策变量。另外，由于AGV的速度与交付时间和能量损耗有关，模型的第三部分决策变量包括每个用于交付过程的AGV的速度。值得注意的是，我们在此方面做出了一些假设：AGV从仓库出发，在仓库和装配点之间往返运送材料；AGV在仓库和装配点之间的速度保持恒定。因此，本文所提出的优化模型的完整决策向量如图1所示。具体而言，每个解向量都由一个混合向量表示，其中，表示第个仓库的位置，，表示属于第个仓库的AGV的速度，，表示第个装配点由第个仓库服务。

图1 优化模型的编码方案

1.2 目标函数

基于提出的编码方案，我们在优化模型中定义了四个最小化目标，其中涉及的符号见表1。为了降低AGV从仓库到装配点运输物料和半成品的成本，第一个目标基于不同需求的仓库和装配点间的距离评估运输成本，表示为：

表1 所提出的优化模型中使用的形式化符号

第二个目标与每个仓库的存储能力有关。考虑到储存能力越大，可能带来的成本越高，因此第二个目标基于每个仓库服务的所有装配点的总需求评估仓储成本，表示为：

考虑到AGV在运输物料和半成品时消耗能量，为了提高效率并降低对环境的能量消耗影响，第三个目标基于运输物料的重量和每个AGV的运输路径长度评估能量消耗，表示为：

考虑到物料运输时间将会影响生产线操作时间和员工资源的安排，第四个目标是基于仓库和装配点之间的距离和AGV的速度计算AGV运输物料和半成品的时间，表示为：

最后，考虑到一个仓库的存储容量是有限的，我们加入一个约束来确保所有由第个仓库服务的装配点的总需求不超过其最大容量，表示为：

综上所述，我们建立了以下带约束的多目标优化模型来解决飞机制造中的物流问题：

这四个目标之间存在一定程度的冲突，特别是表示能量消耗的第三个目标和表示运输时间的第四个目标。通常情况下，运输时间越短，能源消耗就越大，反之亦然。因此，很难通过定义权重系数来平衡这些目标。更重要的是，在最小化目标之前需要强制满足约束条件，这也可能会破坏目标的优化性能。因此，此模型相对较为复杂，给通用优化算法带来了困难。

2 优化算法

基于问题，我们使用多目标进化算法（MO EAs），直接处理混合变量和非凸函数，并且在不聚合任何目标的情况下，在多个目标之间取得良好的平衡。

2.1 约束多目标优化

航空航天和工作室物流问题涉及多个目标的优化和同时满足多个约束[13-15]，这些问题被称为受限多目标优化问题（CMOPs）。CMOP在数学上的定义如下：

受到进化论和自然的群体行为的启发，进化算法在优化过程中演化出一个种群而不是一个单个解，并可以在单次运行中近似一组Pareto最优解，提供多种选择作为最终的输出[17]。在过去几十年中，进化算法的研究发展迅速，多目标进化算法（MOEAs）提出了各种后代生成方案（例如，遗传算子[18]、差分进化[19]、粒子群优化[20]和分布估计算法[21]）和环境选择策略（例如，非支配排序[22]、目标分解[23]和基于指标的选择[24]）。MOEAs从一个随机初始化的种群开始，通过后代生成方案迭代产生新的后代解，并通过环境选择策略保留更好的解。经过多代的重复操作后，种群可以逐渐逼近Pareto最优解[25]，且具有良好收敛性和多样性。

2.2 多目标优化算法

相较于传统的优化算法，多目标进化算法（MOEAs）可以直接处理混合变量和非凸函数，并且在不聚合任何目标的情况下，在多个目标之间取得良好的平衡。尽管约束多目标优化问题（CMOPs）引入了在优化目标之前需要满足的额外约束条件，但近年来MOEAs的研究集中在解决CMOPs上，在此期间提出了许多有效的MOEAs，能够在不惩罚任何约束的情况下[26]，在目标和约束之间取得良好的平衡。

由于本文所定义的优化模型是一个典型的混合变量CMOP，因此在本文中采用以下五种代表性的MOEAs来解决CMOPs。

NSGA-Ⅱ[18]将可行性优势原则嵌入Pareto优势中以解决CMOPs。在该算法中，满足所有约束的解优先于不满足约束的解，剩余的满足约束的解则按照其违反约束的程度进行支配。由于NSGA-Ⅱ总是对约束的优先级高于目标，因此由于需要满足约束，它的解可能会陷入局部最优。

CCMO[27]通过解决一个简单的辅助问题，为CMOPs提出了一个协同进化的约束多目标优化框架。CCMO分别演化出具有相同优化模式的两个种群，其中第一个种群用于解决原始CMOP，第二个种群用于解决从原始CMOP衍生出的帮助问题。CCMO中的协作相比已有的MOEAs较弱，但在解决CMOPs方面证实更加有效。

BiCo[28]尝试通过双向协同进化搜索范式来解决CMOPs。BiCo协同进化两个种群（即样本种群和归档种群），能够有效地将解从可行和不可行的搜索空间中推向Pareto前沿，这对于约束多目标优化至关重要。BiCo设计了一种有效的基于角度的选择策略来更新归档种群，不仅可以维持种群多样性，还能找到更优质的解。

DCNSGA-Ⅲ[29]提出了一种处理CMOPs的问题转化技术。具体地，它将高度约束问题转换为一个约束条件很容易满足的动态CMOP。利用问题转化技术，随着搜索的进行，约束的难度逐渐增加。对于给定的时刻，转换后的问题可以被解决。通过一般MOEAs解决一个无约束问题。此外，动态约束可以帮助MOEAs在多样性和收敛性之间进行平衡，而不必过多考虑约束满足度。

CMOEA-MS[30]设计了一个解决具有复杂可行域的CMOPs的两阶段框架。该算法将进化过程分为两个阶段，并使用不同的适应度计算方法调整目标和约束的优先级。第一阶段显示得到的解大多无法使用，并且为了覆盖可行区域，各个目标给予同等的优先级。相反，第二阶段显示得到的解大多可行，目标的优先级低于约束。

3 实验结果与分析

为了验证所提出的优化模型和使用的算法的有效性，本文在所构造的数据集上进行了各个方法效果的对比。

3.1 实验设置

为了验证所提出的优化模型和使用的算法的有效性，本文构建了一个合成数据集，并在实验中使用，其中包括n=3个仓库和m=50个装配点。装配点的坐标在二维欧几里得空间中随机设置在(0,0)和(100,100)之间，并且每个装配点的需求也在[10,100]内随机设置。对于所有使用的MOEAs，人口规模设置为30，函数评估次数设置为60000。为了充分探索MOEAs在提出的优化模型上的性能，每个MOEA都配备两种类型的后代生成方案，即遗传算子（GA）和差分进化算子（DE）。遗传算子包括模拟二进制交叉[31]和多项式变异[32]，而差分进化算子包括DE/rand/1[33]和多项式变异。交叉概率设置为1，变异概率设置为1/D，交叉和变异的分布指数设置为20，DE/rand/1中的参数为CR=0.9和F=0.5。

另一方面，为了验证所提出的多目标优化模型的优越性，将其与文献[11]中的异构粒子群优化算法HPSO进行比较，该算法解决了用于航空航天物流问题的单目标优化模型。该算法的参数为k=1.86/m，。此外，它解决以下单目标优化模型：

3.2 实验结果

表2比较了六种算法HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA_MS在30次独立运行中获得的标准化超体积（HV）的均值和标准差[34]。较高的HV值表示所得种群的收敛和多样性更好。结果表明，五个多目标优化算法的HV值明显高于单目标优化算法HPSO。此外，图2和图3绘制了HV的收敛过程，这个过程由HPSO和分别使用遗传算子和差分进化算子的5个MOEAs获得。

表2 HPSO、NSGA-Ⅱ、CCMO、BICO、DCNSGA-Ⅲ和CMOEA MS 的HV 值

图2 使用遗传算子获取的HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 的HV 值的收敛过程

图3 使用差分进化获取的HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 的HV 值的收敛过程

从图中可以看出，五个多目标优化算法比HPSO收敛更快，并且最终得到的HV值也更高。因此，多目标优化算法的优越性已得证。此外，使用遗传算子的多目标优化算法表现更好，因为它可以更好地从所提出的优化模型的景观中逃脱局部最优值。

为了进行直观比较，图4列出了六种算法所获得的非支配解，依据不同目标进行排序。可以发现，对于所提出的优化模型而言，多目标优化算法特别是CMOEA_MS可以得到许多非主导解，而单目标优化算法HPSO所得到的解被许多其他解所支配。事实上，HPSO通过预定义的权重系数对四个目标进行加权求和以得到单目标优化，因此，得到的解倾向于节约能量，而对于运输成本、仓储成本和运输时间的目标优化较差。因此，证明了对于航空航天物流问题，多目标优化技术优于单目标优化技术。为了清晰地比较各种算法所获得的解，图5描述了每个仓库解码后覆盖的装配点，选择每个算法所获得的最靠近目标空间原点的解进行绘制。显然，多目标优化算法获得的解与HPSO获得的解相比有更少的交叉路径，因此在实践中更有效率。此外，表3列出了比较算法所获得的三个仓库的速度，多目标优化算法获得的解具有比HPSO更高的速度，因此在交付时间方面更短。最后，为了比较算法的优化效率，表4显示了它们所消耗的运行时间，其中多目标优化算法的计算复杂度与单目标优化算法 HPSO相似。因此，所提出的多目标优化模型以及先进的多目标优化算法对于航空制造物流问题是有效的和高效的。

表3 HPSO、NSGA-Ⅱ、CCMO、BICO、DCNSGA-Ⅲ和CMOEA MS 的速度

表4 HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 的运行时间

图4 HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 获得的非支配解

图5 HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 获得的解码后的仓库覆盖的装配点

4 结论与展望

为了解决飞机制造中的物流问题，本文建立了一个受约束的多目标优化模型，其中包含了一个混合决策向量、四个相互冲突的目标和若干约束条件。为了解决这个复杂的优化模型，本文选择了五种最先进的受约束多目标优化算法。通过实验结果的分析，本文验证了受约束多目标优化技术在现有研究中明显优于使用的单目标优化技术。

未来可以开发更有效的元启发式算法以获得更好的优化性能。此外，本文仅验证了通用多目标优化算法在黑盒优化中的优越性，对于解决物流问题，可以定制更多的启发式搜索策略，并满足不同场景中的额外考虑因素。