考虑转移策略的物料配送和空箱回收集成优化

2023-06-02陆志强王韵熹

同济大学学报（自然科学版） 2023年5期

陆志强，王韵熹

（同济大学机械与能源工程学院，上海 201804）

飞机总装周期约占整个飞机制造周期的 25%～40%［1］。为了缩短总装周期，近年来逐渐引入更加稳定和高效的移动装配技术［2］。但这种装配方式对精准配送提出了更高的要求，亟需建立一个有效而可靠的配套物料供给系统。

飞机装配过程中所需的物料可以分为4 类：通用标准件、大型结构件、装配件和自制件。通用标准件（如螺栓等）一般在线边存储，采用定期补货的方式供给；大型结构件（如发动机、机翼等）通常使用叉车和机械臂等其他方式直接配送。本文研究问题中的物料主要指体积中等、种类复杂的装配件，由于零部件组装的相关性，通过齐套的方式使用标准料箱以准时化的方式进行配送，并在作业完成后对空箱进行回收。

目前以飞机移动装配线为背景研究物料供给问题的文献较少，而以汽车装配线为背景的研究相对成熟且物料供给过程与飞机类似，因此可以借鉴汽车装配线中物料供给问题的模型与算法作为参考。Sali等［3］对库存、齐套和顺序配送这三种常用的物料配送策略进行了描述并总结了各种配送方式的适用环境。Souza等［4］研究装配线准时化物料配送问题，以最小化搬运费用和库存费用为目标建立数学模型，提出了具有贪婪随机自适应搜索的启发式算法。Boysen等［5］以最小化最大库存水平为目标函数建立了汽车装配线叉车配送模型，并设计了动态规划算法进行求解。但文献［5］假定每个料箱的物料量为定值，在实际应用中可能出现缺料的情形，因此Zhou 等［6］对假设进行了改进，在决策变量中引入了每次配送物料量的选择，同时设计了反向动态规划算法对该问题进行求解。上述问题均考虑的是点对点的配送问题，每次只配送一个工位。Fathi 等［7］提出了milk-run 配送方式下多载量小车装载和调度问题，即小车每次可以装载多个工位所需物料。Emde等［8］在此基础上对小车发车时间与配送工位进行了集成决策。Golz 等［9］研究了多辆小车的组批和调度问题，设计了两阶段分解算法最小化配送人员数量。Zhou 等［10］考虑了以电动机器人作为送料工具的情况，提出了一种二次搬运的策略，通过物料在不同机器人之间的转运降低了物料供给过程的能耗以及机器人的数量。

上述文献对汽车装配线的物料供给问题进行了充分的研究，但汽车装配线模型与飞机装配线模型存在区别，将其直接应用到飞机移动装配线中存在局限性。汽车装配线每个工位装配作业单一，一般采用固定料箱，研究的重点集中于小车的装载和调度问题；而飞机移动装配线装配周期长且并行作业多，不对线边空间进行合理的分配会造成物料存储空间不足等问题。胡鑫铭等［11］建立了飞机移动装配线物料配送与线边存储集成优化模型，在物料组批和小车调度的基础上，引入了物料在线边空间的存储决策。但文献［11］假设空箱在装配完成后统一回收，忽略了空箱对线边空间的占用以及回收所需要的物流成本。陆志强等［12］建立了飞机移动装配线物料配送与空箱回收集成决策模型，考虑让小车在单次出行中同时执行配送和回收任务，相比独立回收策略减少了出行次数。但是由于小车在线边只能按位置顺序执行各线边单元上的任务，因此需要在小车从中心仓库出发时就预留好空箱的存放空间，提高了小车返回仓库时的装载率却降低了配送物料时的装载率，相比独立回收策略成本优化有限。

事实上，对飞机移动装配线的物料配送和空箱回收进行集成决策存在如下权衡：在时间上，对物料分批和发车时间进行决策时需要协调配送和回收任务的时间约束；在线边空间上，料箱和空箱共享线边存放空间，不对料箱到达线边的时间以及空箱离开线边的时间进行科学的决策就会导致存放空间不足；在小车的装载能力上，小车装载率受到空箱和料箱存放位置前后关系的影响，不对线边存储进行合理的规划会降低两类任务调度的集成度，增加出行成本。因此，对物料配送和空箱回收任务的集成决策展开研究对于保障飞机移动装配线物料供给系统的稳定性和效率具有重要意义。

基于对上述文献研究成果的分析，本文在文献［12］提出的物料供给问题中引入转移策略和线边存放位置的决策，提出了考虑转移策略的物料配送和空箱回收集成优化问题（Integrated optimization of material delivery and container pickup problem considering transfer strategy，IOMDCP-TS）。以飞机的一个装配节拍为决策周期，综合考虑小车装载能力与线边空间重复共享等因素，对料箱和空箱的组批方式与其在线边存放的位置与时间进行决策，建立了以最小化小车出行成本为目标函数的数学模型并设计了以混沌差分进化算法为框架的启发式算法对该模型进行求解。其中结合了发车时间动态调度算法、存放位置决策算法和转移调度算法。最后通过数值实验验证了该算法的可行性和有效性。

1 问题描述和数学模型

飞机移动装配线物料供给问题，是通过优化各作业所需物料的配送、回收时间及其在线边空间的存放位置，以达到最小化小车出行成本的目标。图1为飞机移动装配线的物料供应模式，整条装配线被划分为多个“虚拟大工位”，每个大工位内存在大量的并行装配作业，在工位旁划定相关的区域用于存放各作业装配所需的物料，并由多载量小车将物料按照装配计划从中心仓库配送至对应的线边单元，同时将各线边单元上的空箱运回中心仓库。

图1 考虑转移策略的物料配送及空箱回收模型示意图Fig.1 Material delivery and container pickup model considering transfer strategy

小车装载率受到空箱和料箱在线边存放位置的相互关系的影响，因此。为了提高小车的装载率，减少小车出行成本，本文提出了转移策略，即允许小车将空箱放至线边末尾的空箱暂存区后直接返回装配线前端，由其他小车将暂存区的空箱运回中心仓库。通过该策略可以调整空箱的存放位置以及在线边的存放时间，减少小车从中心仓库到线边的往返次数并优化线边物料的存放状态。称执行料箱配送任务和空箱回收任务的小车为配送小车，执行空箱转移任务的小车为转移小车。

该问题的假设与符号说明如下：

（1）以飞机移动装配线的一个装配节拍时间为决策周期。假定该周期内某大工位包含n项装配作业，J={1，2，…，n}，任意作业j∈J的执行工期为tj，开始时间为TS，j，完成时间TF，j=TS，j+tj。

（2）将时间离散化，时间集合为D={1，2，…，Z}，Z表示所有作业操作时间总和，任意d∈D表示时间节点。tw，j={t|t=TDS，j…TDF，j}表示作业j在线边存放的时间窗。Jl表示线边单元l的作业集合，表示线边单元l第i个时间窗交集不为空集的作业集合。

（3）Ka表示配送小车集合k∈Ka={1，2，…，h}；Kb表示转移小车集合k∈Kb={1，2，…，h}。小车从仓库到线边的运输时间为tl，从装配线前端到末端的移动时间为tb，飞机移动速度为v，表示单位时间内经过的线边单元数量。任意配送行程r不得超过装载能力上限Cmr∈Rk= {1，2，…， π}，Rk表示小车出行趟数集合。

（4）同一个作业的料箱由一辆小车一次性配送和回收，一辆小车一次可配送或回收多项作业所需的物料，作业j对物料的需求量为mj。作业j的物料抵达线边的时间为TDS，j，离开线边的时间为TF，j，配送提前期tp，j=TS，j-TDS，j，回收滞后期tI，j=TF，j-Tf，j。

（5）将线边空间和作业空间离散化。如图2 所示，作业空间描述了各作业在飞机上的装配位置，用集合Γ={1，2，…，φ}表示，φ表示飞机的长度，任意lj∈Γ表示作业j在飞机上的装配位置；线边空间描述了物料在线边的存储位置，用l∈L={1，2，…，ξ}表示线边单元的集合，ξ表示最大线边单元的编号；用cl= {1，2，…，ψ}表示各线边单元内存储位置的集合，ψ表示线边单元的容量。对于任意一架飞机，状态A 表示飞机开始进入装配线，移动到状态B 的位置开始执行作业j，移动到状态D 的位置作业j执行结束。状态C 表示该作业执行过程飞机的中间位置，定义该状态下作业j装配位置所对应的线边单元为该作业物料的中心存储位置，即表示向上取整。

图2 飞机作业装配点及物料存放位置Fig.2 Assembly positions and material storage on aircraft moving assembly line

（6）为减少取料距离，作业j的物料只能存放在lm，j及其左右两侧各1个单位的线边空间内。为使线边物料存放整齐有序，要求任一作业的全部物料应连续存放于同一线边单元内。

（7）为了避免同一工段内前后两架飞机所需物料在线边发生重叠，在每个大工位之前设置生产缓冲带，该区间内不进行装配作业。配送小车发车时刻晚于最大提前量约束tmin。

（8）在装配线末端设置空箱暂存区，转移小车将空箱从线边单元取下暂存在该区域内，由配送小车运回中心仓库。

定义决策变量如下：

xjrk∈{0，1}，作业j的料箱在配送小车k第r趟出行配送时则xjrk等于1，否则取0。

yjrk∈{0，1}，作业j的空箱在配送小车k第r趟出行时回收则yjrk等于1，否则取0。

zjrk={0，1}，作业j的空箱在转移小车k第r趟出行时转移则zjrk等于1，否则取0。

(ta，rk，tb，rk，lj)，ta，rk表示配送小车k第r次出行的时间，tb，rk表示转移小车k第r次出行的时间，lj为作业j的存放单元。

定义辅助变量如下：

根据上述模型假设和符号定义，对该问题建模如下：

式（1）为目标函数，最小化小车出行成本，包括配送小车和转移小车的出行次数以及车辆的固定成本。其中，ca，cb，cc分别是三者的单位成本系数；式（2）表示每个作业的料箱要在作业开始时间之前送达；式（3）～（5）表示每个作业的物料只能在作业完成之后回收或转移，同时转移时间要早于回收时间；式（6）表示作业配送时间要满足最大提前量约束。式（7）～（9）表示单个作业物料的运输任务均只能由同一辆小车执行；式（10）～（11）表示小车在整个行驶过程中都不能超过其载量上限；式（12）表示任意时刻线边单元物料暂存量均不应超过其最高限度；式（13）表示物料中心存放位置为其装配过程中的中心位置。

2 算法设计

Boysen 等［13］研究了IOMDCP-TS 问题的一个子问题（从仓库向单工位组批配送物料，目标为优化小车配送次数），并证明了该问题为强 NP-hard 问题。而IOMDCP-TS 问题除了小车的配送调度外，还要考虑物料的存放以及小车的转移调度，具有较高的复杂度。精确算法在求解这类大规模问题时效率较低。差分进化算法具有速度快、鲁棒性好等优点，被广泛应用于生产调度等问题［14-15］。因此本文针对IOMDCP-TS问题的特点设计了以混沌差分进化算法为框架的启发式算法（HBCDE）。该算法上层对物料的组批方式进行搜索，下层对每个包含物料组批方案的个体依次采用发车时间动态调度算法、存放位置决策算法和转移调度算法进行解码；最后使用两种修复算子对不可行解进行修复。算法迭代过程中适应度较高的个体所对应的物料组批方案较优，将作为优质解保留在记忆池中；低适应度的个体将被淘汰或通过变异更新。设定Nm为最大迭代次数，g为当前迭代次数。算法框架如图3所示。

图3 算法结构Fig.3 algorithm structure

2.1 差分进化算法框架

本文采用离散型差分进化算法，使用双层整数编码。编码的列数为作业的数量n，编码数字为不大于作业数量的整数。上层数字代表该作业物料配送的批次序号，下层数字代表该作业物料回收的批次序号。如图4所示作业1的物料在第二批配送，在第三批回收。为了提高算法搜索的效率，在初始种群中加入了两条分别基于作业开始时间（FCFS）和作业结束时间（LFT）进行排序的个体。

图4 编解码及修复示意图Fig.4 Encoding, decoding and repairing representation

对于违反载量或时间约束的作业，从编号最小的开始执行就近转移规则，将该作业移入离当前批次最近的批次，直到该作业满足约束。如果所有批次都无法存放该作业则为该个体添加惩罚值。

混沌序列具有随机性、遍历性等特点［16］。为了防止算法早熟收敛，本文在差分变异算子中引入混沌序列对比例因子进行动态调整，根据logistic 方程yn+1，d=μyn，d(1—yn，d)产生混沌序列，然后通过载波方式将混沌变量映射到比例因子的取值范围［0，2］。式中：n∈[1，Nmax]，Nmax取 100 ，d为变量的维度， μ 是混沌状态的控制参数，本文取4，该参数下logistic方程完全进入混沌状态。在离散差分进化算法中缩放比例因子根据Fch=yn，dexp (—t/tmax）动态产生，差分进化中的变异算子如式（14）所示，其中r1，r2，r3为与i不同的互不相同的3 个随机个体。关于差分进化算法的通用部分不再赘述。

2.2 发车时间动态调度算法

在物料分批确定的情况下，对批次发车时间进行优化可以减少物料在线边的占用时间。各批次的发车时间会受到最早作业开始时间和最晚空箱回收时间的约束。在该范围内，若料箱较多而发车时间偏早会导致配送提前期过长；若空箱较多而发车时间偏晚则会导致回收滞后期长。二者均会使料箱在线边的占用时间延长，导致线边存放空间不足。在参考文献［13］提出的反向动态调度技术的基础上，基于以下定理提出了发车时间动态调度算法，该算法能保证每个批次物料在线边的总占用时间最短。应用该算法得到的物料占用时间作为中间解，为后续存放位置决策算法的应用奠定基础。

定理：对于包含配送作业集合Jx和回收作业集合Jy的作业批次Bi，若满足那么使得该批次物料在线边占用最小的发车时间为

证明如下：

发车时间规划这一子问题的目标函数是在使得物料在线边的占用在时间和空间两个维度上最小，也就是使得非必需存放时间和物料量的乘积最小。

设，则该函数可以表示为

该函数为ti的单调函数，取值由ti的系数决定。

（4）更新该车的最早可用时刻为tea，(r+1)k=trk+2t0。

（5）如果i=|Ω|，转（6），否则i=i+1，转（3）。

发车时间的动态规划算法步骤如下：

（2）令i=1，选择首个批次的物料集合Bi，安排其发车时间

2.3 存放位置决策算法

在确定了物料在线边的占用时间之后，可以将带时间维度的线边存放区看作一个长、宽、高分别对应于装配节拍、线边长度和单位线边单元容量的三维容器。胡鑫铭等［15］将物料在线边的存放过程抽象为了一类带单边时间窗的三维装箱问题。但该模型仅考虑了物料提前配送对于线边的非必需占用，而在实际情况中回收的滞后也会导致空箱对于线边空间的占用，因此本文考虑了一个带双边时间窗的三维装箱问题并为该问题设计了物料初始存储位置生成算法并为无法存放的物料设计了修复算法。

物料的初始存储位置生成算法如下：首先将线边单元li的作业集合Jli中的所有作业按照mj(TDF，j—TDS，j)降序排列，按照该顺序依次挑选作业放入其对应线边单元，判断是否满足三个维度上的约束，满足则输出该作业存放位置；若其存放范围内的线边单元均不满足则将其放入无法存放作业集合。

由于在配送小车发车时间的调度的过程中松弛了线边容量的约束，因此可能会出现作业无法存放的情况。对于无法存放的作业集合Νp，采取局部替换和削峰算法两种算子对不可行解进行修复。首先使用不会增加额外成本的局部替换算子，若不能修复则采用存在额外成本的削峰算子进行修复。

（1）局部替换：通过在局部范围内对作业存放位置进行互换调整使线边存量满足约束。主要步骤为：对于无法存放的作业jun，从其可存放范围中按照剩余空间降序选择线边单元，按物料量升序选择作业直到可以替换jun。对新的jun首先判断能否直接放入，若没有则重复相同操作直到不存在无法存放的作业。

（2）削峰算法：参考文献［17］提出的削峰操作，利用转移策略将空箱离开线边的时间提前，等同于削减物料占用立方体的长，解决因作业存放时间重合导致空间不足的问题。

削峰算法步骤如下：

（1）获取无法存放的作业集合Νp，令未被选择的作业集合Νo=Νp。

（2）从Νo中随机取出一个作业的物料j，令jun=j，ltp=lm—1，j。

（3）将线边单元ltp的作业集合的子集Jli按照升序排列。

（4）按顺序遍历各子集，判断将能否通过将该子集中作业的离开线边时间提前至作业结束时间的方式来将该作业放入。若，加入作业j后仍然满足对于∀t，mli，t＜φ，对于∀j∈Jli*，令TF，j=TDF，j，Jli=Jli∪jun，Νp=Νp—jun，转Step5；若且ltp≠ltp+1，令ltp=ltp+1，转（3）；否则转（5）。

（5）若Ν0≠Φ，转（2），否则转（6）。

（6）若Νp≠Φ，添加惩罚值到目标函数中；否则输出存放位置集合L={l1，l2，…ln}和需要削减存放时间的作业集合Jp。

如图5 所示，有7 个作业的物料被存放在线边，立方体的长代表该作业的物料在线边存放的时间窗［TDS，j，TDF，j］，高代表该作业的物料量。矩形中深色的部分代表作业的在线边存放的硬时间窗［TS，j，TF，j]，此时间窗无法调整；带斜线的浅色部分代表作业的物料的配送提前期tp，j以及存放滞后期tI，j，可以通过更改发车时间来对其进行调整。如图5所示，按照初始存储位置，作业5的物料会超出线边单元的容量。使用削峰算法将作业7在线边的时间窗从［TDS，7，TDF，7］缩短为［TDS，7，TF，7］，避免了作业5和作业7 的物料在时间上的重合，修复后使该线边单元满足了最大容量约束。

图5 削峰算法Fig.5 Peak clipping algorithm

2.4 转移调度算法

通过2.2 节和2.3 节中的算法解码可以得到需要转移的作业集合为超出线边容量约束需要减少回收滞后期的作业集合，由2.4 节中的削峰算法计算得到。Ju表示无法即时装载的作业集合。计算Ju的算法步骤如下：

（2）选中第一个还未被选择的批次Bi，初始化批次Bi的载量

（3）遍历各线边单元，若该线边单元存在配送作业，mBi=mBi—mj；若存在回收作业且mBi+mj≤Cm，则mBi=mBi+mj；若mBi+mj＞Cm，将该作业加入转移作业集合。

（4）若所有批次都已被选择，输出无法即时装载的作业集合Ju；否则转（2）。

将Jt按完成时间进行升序排列，使用最小批量法生成转移批次的初始解，以出行次数最少为目标对最优转移批次进行搜索。转移小车出发时间的决策问题是配送小车出发时间决策问题的一个特例，即各转移批次中只包含回收作业，不包含配送作业，因此最优发车时间依然适用于2.2 节中所证明的定理。

3 数值实验

本文使用文献［11］所构建的算例集进行数值实验，参考了文献［18］关于出行成本的参数设置，设定单次配送小车行驶成本45$，单次转移小车行驶成本9$，单辆小车固定成本45$。小车容量Cm=20，线边单元容量ξ=20，中心仓库到线边装卸货的时间tl=4，线边运行时间tb=1，飞机移动速度v=0.5。构建了30、60、120等3个规模的算例来进行实验，每个规模的算例集包括3组，每组10个算例。本文在Pycharm 2021.2.1（community edition）平台上使用Python 语言进行编程测试，计算机配置为Ryzen 74 800H处理器，2.9GHz主频，16G内存。

3.1 策略对比

将本文提出的转移策略TS 和文献［12］所提出的集成调度策略CHBG以及传统的两阶段调度策略CAS 进行对比。CAS 策略是指将物料配送和空箱回收作为两个独立的问题，分别进行调度，最后将总出行成本相加；CHBG 策略是指对物料配送和空箱回收进行集成调度，一个批次可以同时执行这两种任务；TS 策略是在CHBG 策略的基础上，允许空箱在线边进行转移以优化料箱和空箱的存放次序。对三种策略采用相同的解码算法。对比的结果如表 1所示，表格中Ci代表策略i物料配送的总成本，Gi代表策略i的成本和三种策略中的最低成本之间的差距，计算如下：

对表1 的数据进行分析可以得到如下实验结论：

（1）在成本上，在3种规模的算例下， TS策略都拥有最低的总成本，而且随着算例规模的上升，相比另外两种策略的优化幅度也进一步提升。在120的算例规模下，TS 策略相比CHBG 策略和CAS 策略优化比例分别达到了19.40%和29.70%。

（2）在可行解比例上，TS 策略也拥有最高的求解成功率。如图6所示，在30规模的算例下，3种策略都能对所有算例成功求解；在60 规模的算例下，TS策略依然能够成功求解所有算例，而CHBG策略和CAS 策略都下降到了93.33%；在120 的规模下，TS 策略求解成功率达到了86.67%，而CHBG 策略和CAS策略分别下降到了76.67%和73.33%。

图6 不同策略成本及可行解比例对比Fig.6 Comparison of cost and proportion of feasible solution between different strategies

综上所述，转移策略的引入能够有效降低物料配送和空箱回收集成模型的小车出行成本和不可行解比例，说明该策略在物料批次的划分和存放位置的决策上都具有优越性。

3.2 算法对比

为了验证HBCDE 算法的性能，将该算法与去除修复算法的HBCDE-RA，标准DE 算法和CMAES 算法进行了对比。在30、60、120 等3 个规模的算例下进行了实验，每个算例集包括30 个算例。用可行解比例和总成本两个指标作为衡量标准，分别用P和C进行表示。分析表2中的实验结果可以得到如下结论：

表2 不同算法结果对比Tab.2 Comparison of experimental results between different models

表3 错位度与优化幅度的回归分析Tab.3 Regression analysis of misalignment and optimization amplitude

（1）在算法框架的对比中，HBCDE 算法在3 种规模的算例下，都拥有更低的成本和更高的求解成功率，随着作业规模的增大，优势更加明显。在规模为120 的算例下，相比HBCDE 算法和CMAES 算法，该算法在成本上分别优化了6.65%和4.49%，在求解成功率上与CMAES算法持平，比DE算法高出6.67%。说明本文使用的混沌差分进化算法在求解物料组批配送这一类组合优化问题上具有优越性，可以得到更高的的求解质量和可行解比例。

（2）在修复算法的效果验证实验中，加入修复算法的HBCDE-RA 算法比HBCDE 算法成本降低了4.33%，求解成功率提高了20%，说明该修复算法在三维装箱这类问题的不可行解修复上具有良好的效果。

3.3 算例错位度对转移策略效果的影响

为了探究算例中影响转移策略有效性的因素，本文综合考虑小车运输机制和作业信息提出了一项以错位度（Dislocation degree，dld）为核心的评价指标，该指标表征了算例中空箱的回收任务与配送任务相互冲突的可能性。定义辅助变量Dl，ij，代表两个算例之间的错位关系，如果作业j完成时间和中心存放位置都小于作业i则Dl，ij=1，否则Dl，ij=0，如式（19）所示。对于任意作业j，错位度计算方式如式（20）所示，|J|表示作业数量。

分别绘制81 个成功求解的算例的错位度和转移策略的优化幅度的折线图，如图7 所示可以看出两条曲线的形状高度吻合。计算两个指标的回归方程为G= —0.0901 + 1.809dld。方差分析表如3所示，P值表示样本间的差异由抽样误差所致的可能性，其值小于0.001 说明错位度对于转移策略的优化幅度有显著的影响，而Pearson 相关性系数为0.735，说明二者的关系为正相关。对于错位度高的算例采用转移策略可以降低更多的成本。该评估方法也可以应用到其他采用循环配送方式的料箱配送和回收集成调度问题中。

图7 错位度和优化幅度曲线的对比Fig.7 Curve comparison of misalignment and optimization amplitude

3.4 成本系数对转移策略有效性的影响

成本系数之间的大小关系可能会影响该策略的有效性。为了探究二者比值处于什么范围内该策略有效，对三种规模的算例进行实验，绘制临界点的箱线图如图8 所示。比值在临界点以下则该策略有效。临界点的计算方法为：以0.01为间隔生成总成本关于转移与配送成本系数比值的变化曲线，观察与CHBG 策略成本的交叉点，以交叉点左侧的值为临界点。可以看出3 组规模算例的临界值分布在［0.61，0.84］的区间内，规模越大，临界值越高。在具体装配线的决策过程中，可以通过计算这两者的比值是否达到临界值来判断采用转移策略是否有效。