基于改进多目标布谷鸟搜索算法的汽车装配线物料配送调度

2020-12-30周炳海李秀娟

湖南大学学报（自然科学版） 2020年12期

周炳海，李秀娟

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

以多品种、小批量为特色的混流生产模式使得汽车装配线所需零部件的种类和数量显著增加，因而准时化物料配送调度对制造型企业降本增效具有重要意义[1-2].

目前，国内外已有许多学者对汽车装配线物料配送问题进行了较深入的研究.Emde[3]等构建了禁忌搜索算法来解决装配线物料配送系统中的车辆装载和配送频率问题.Fathi[4]等采用融合优先级规则的改进粒子群算法解决了装配线的零件补给问题.Peng[5]等采用一种基于物料超市模式的准时制交货策略，解决了搬运车辆配送调度的多目标优化问题.Zhou[6]等利用神经网络解决了装配线物料配送的动态调度问题.文献[3]和[7]在周期性物料配送的基础上解决了具有预定路线的车辆调度和装载问题.以上关于传统燃料车辆在固定路径下的物料配送模式往往存在着拣货复杂、响应速度慢、能耗大以及线边库存多等不足.点对点（Point-to-Point，PTP）物料配送模式[8-9]以其灵活性和时效性弥补了传统配送模式的不足.本文在分析上述文献的基础上，研究了电动车辆（Electric Vehicles，EV）点对点物料配送问题，建立准时制物料配送问题的数学规划模型，并提出求解该模型的改进多目标布谷鸟搜索算法.最后，通过仿真实验验证了所提出调度算法的可行性和有效性.

1 问题描述与模型建立

1.1 问题描述

图1 所示为电动车辆点对点物料配送的示意图.物料超市的配货工人根据各个工位发出的补货要求把零件事先分拣好并装进标准大小的物料箱中.电动配送车辆在物料超市补货完成后在各个配送任务的补货时间窗内对需求工位进行物料配送.考虑物料量和行驶距离带来的电量变化，电动车辆必须在电量不足时返回换电站进行换电.

1.2 数学模型

为有效描述电动车辆点对点物料配送系统调度问题，做如下基本假设：1）电动车辆换电时间已知；2）在执行首次配送任务前，所有车辆均为满电状态；3）车辆的行驶速度处于稳定状态；4）所有的车辆执行配送任务时均从物料超市出发并返回物料超市；5）车辆的耗电速率和负载重量、行驶距离成正相关；6）换电站设置在物料超市旁边，不计车辆因换电产生的额外行驶距离；7）线边卸载物料时间很短，忽略不计.

图1 装配线点对点物料供应Fig.1 The point-to-point part feeding for assembly lines

为方便描述，定义符号如下：

1）下标表示

K：可用车辆集合；

k：车辆编号，k∈K；

S：配送任务集合；

s：任务编号，s∈S；

T：配送行程集合；

t：配送行程序号，t∈T.

2）时间相关

β：一次换电时间间隔；

δ：小车在物料超市的补货时长；

Es：任务s 最早补料时刻；

Ls：任务s 最晚补料时刻；

3）其他符号

Q：小车的满电电量；

re：小车空载时的单位距离耗电量；

gs：任务s 需要配送的物料质量；

γ：每增加单位质量料箱时单位距离的耗电增量；

V：小车的行驶速度；

dms：配送任务s 对应工作站与物料超市之间的距离；

Skst：小车k 第t 次配送执行任务s 的起始电量；

Rkst：小车k 第t 次配送执行完任务s 后返回物料超市的剩余电量；

fkst：二进制变量，小车k 在执行完任务s 之后去充电为1，否则为0.

4）决策变量

xk：1，小车k 投入使用，否则为0；

ykst：1，小车k 在第t 次配送执行任务s，否则为0.

此外，为了接下来更好地构建数学模型，给出二元阶跃函数的定义如下：

据上述问题描述、模型假设及符号定义，并参考文献[2]和[3]的相关约束条件的表示方法，对汽车装配线点对点物料配送调度问题建模如下：

目标函数：

其中：

约束如下：

模型中，式（2）～（4）为目标函数，表示最小化电动车辆数量以及最长物料搬运时间；式（5）表示每个配送任务仅被执行一次；式（6）表示每辆小车在一次配送行程中只执行一个配送任务；式（7）表示车辆在投入使用后才能执行配送任务；式（8）表示每个配送任务的首次补料时间；式（9）～（10）表示补料任务必须在其时间窗内完成；式（11）表示每个配送任务的结束时间；式（12）～（13）表示车辆每次行程结束的剩余电量；式（14）表示车辆执行每个任务前的起始电量，这也是连接两次配送任务的桥梁；式（15）表示车辆执行首次配送任务前为满电状态；式（16）表示当小车的电量低于10%时返回换电站进行换电，从而减少因过放电对电池造成的损害[10]；式（17）定义了二进制变量.

2 算法构建

本文研究的调度问题属于NP-hard 问题，群智能算法能有效解决这类难题.布谷鸟搜索算法是Yang 等人提出的一种新型的群智能算法[11]，具有参数少、收敛性能稳定、易于实现等优点，已经成功应用于工程优化、资源调度等领域[12-13].

为了有效地解决汽车装配线准时化物料补给问题，本文提出一种基于混沌动态步长的多目标布谷鸟搜索算法.该算法基于混沌模型对搜索步长进行自适应调整，并加入高斯变异和精英选择策略来提高算法的全局搜索能力和解的质量.此外，设计两种局部搜索算子强化算法的深度寻优能力.

2.1 解的编码与解码

采用基于车辆编号的融合编码机制，将任务分配方案及其执行序列融于同一编码.如图2 所示，编码长度为S，代表任务总数，每个配送任务与一个实数编码相对应，其中编码的整数部分表示负责该工位的车辆编号，小数部分按照升序排列，表示该车辆的任务执行序列.

图2 编码方式Fig.2 Encoding presentation

2.2 任务分配规则

为增加初始解的多样性，任务分配规则在公式（12）～（14）的基础上以减少车辆空闲时间为原则，按照分级概率选择配送任务，产生初始解.同时，让不可行个体参与进化过程，赋予其被选择的概率，从而利用不可行解所包含的进化信息，分级概率如式（18）所示，其中，ξ 为（0，1）之间的随机数.

假设种群规模为NP，编码长度为S，可用车辆集合为K，其基本步骤为：

步骤1 初始化车辆编号k∈K，车辆k 的配送任务集合Jk=Ø，可执行任务J={1，2，…，S}，车辆k剩余可执行任务=J；

步骤3 生成一个（0，1）之间的随机数p，随机选择任务s′∈，通过计算车辆k 执行任务s′的补料时间，根据式（18）得出选择概率.若p≤ps′，则选择当前任务s′为车辆k 的下一配送任务，更新En′＞Ls′，n′∈}，Jk=Jk∪{s′}和J=J/{s′}.若继续选择下一任务，否则，当J ≠Ø 时，转至步骤4，当J=Ø 时，转至步骤5；

步骤4 整理车辆k 的任务集合{Jk}，k=k+1，返回步骤2；

步骤5 整理所有电动车辆的配送任务为[{J1}{J2}…{Jk}].

2.3 局部搜索机制

为了提高算法的局部搜索能力以适应本文的电动车辆点对点物料配送问题，本文针对两个目标函数，设计remove 算子和swap 算子进行目标优化.

remove：找出配送次数最少的车辆k 的任务执行序列Jk，将任务j∈Jk插入到其他车辆k′的任务执行序列Jk′（Jk′≠Ø）中.为了减少时间冲突，插入位置为当最后一个任务从Jk中移除时，车辆k 从当前配送方案中移除.

swap：找到搬运时间最长的车辆k 的任务执行序列Jk，将任务j∈Jk与其他车辆k′的任务j′∈Jk′（Jk′≠Ø）进行交换.为了提高任务可行性，任务j′的位置为argmin，交换条件为dmj＞dmj′.

2.4 基于混沌动态步长的多目标布谷鸟搜索算法

为了避免布谷鸟搜索算法在搜索过程中早熟，搜索步长α 在迭代初期应保证足够大，从而快速找到全局最优解.随着迭代次数增加，α 值应逐步减小，使得算法趋于稳定.本文采用Iterative 混沌映射模型函数对步长递减系数进行自适应调整，即

式中：it 表示当前迭代次数；λit表示第it 次迭代的步长缩减系数；b 是介于0 和1 之间的常数；αit表示第it 次迭代的搜索步长.通过自适应levy 飞行得到变换后的鸟巢位置，即

引入任务分配规则和局部搜索机制以进一步提高算法的寻优能力.

步骤1 初始化.结合任务分配规则生成NP 个个体X1，X2，…，XNP.

步骤2 鸟巢更新.对每一鸟巢的位置Xi，根据式（21）实现鸟巢位置的更新.

步骤3 鸟巢淘汰.根据发现概率pa=0.25[14]淘汰当前解后采用随机游走方式生成相同数量的新解，即

步骤4 鸟巢扰动.为进一步增强算法的全局开发能力，采用高斯变异对鸟巢位置进行扰动.给定候选解Xi，扰动公式为

式中：Lbi，j和Ubi，j分别表示第i 个个体第j 个编码的最小值和最大值，GM（Xi，j，σ）表示由正态分布产生的一个随机数，其均值和标准差分别为Xi，j和σ.

根据文献[15]的研究工作，σc=20.

步骤5 解的修复.采用任务内、外转移规则进行修复.任务内前移：对任意车辆k，按编码值大小升序排列，按照顺序找到违反时间窗约束的任务kd，进行任务前移.将其向前转移至与之相邻的任务前，计算前kd个任务是否违反时间窗约束，若仍违反时间窗约束，则继续前移动，直至kd移至第一个位置；任务内后移：上述操作后，若解仍不可行，则按相同规则操作，直至该任务移至最后一个位置.任务外移：对剩余违反时间窗约束的任务重复操作，将无法通过任务内转移的任务转移至另外一辆车辆k′.

步骤6 精英选择.合并父代和子代种群，并对其进行Pareto 非支配排序，为了进一步为提高种群分布质量，综合考虑拥挤距离大小和距离波动，采用波动拥挤距离对个体进行排序，波动拥挤距离大的个体保留至下一代，计算如下：

算法流程图如图3 所示.

图3 算法流程图Fig.3 Framework of the algorithm

3 仿真实验分析

3.1 参数分析

在基于Windows 10 操作系统的Core i5/2.5 GHz内存4 GB 的计算机上进行.由于此问题的真实帕累托前沿很难得到，本文在进行实验时采用以下方法获得近似帕累托前沿：算法独立运行多次后记录每次的帕累托解集，从所有帕累托前沿中获得新的帕累托解集作为近似前沿.参考文献[16]的参数设置，实验设置电池容量Q=100，车辆空载时单位距离耗电率re=0.1，每单位料箱质量造成的耗电速率增量γ=0.2，小车速度V=2，工作站到物料超市的距离、时间窗长度和物料质量分别在 [20，50]，[20，30]，[10，20] 的均匀分布中随机生成.为了获得更高质量的解，根据文献[17]对算法参数进行调优，选取不同的参数组合进行多次实验.当设置种群规模nPop=100，Levy 飞行搜索概率pc=0.8，扰动概率pr=0.4，局部搜索概率pl=0.5 时，算法以较高质量求解.

为验证任务分配规则以及局部搜索机制的有效性，将其与未采用任务分配规则和局部搜索算子的改进多目标布谷鸟搜索算法（Improved Multi-objective Cuckoo Search，IMCS）进行对比.算法运行时间设置为300 s，表1 记录了不同问题规模下的求解结果.由表1 可知，结合任务分配规则和局部搜索机制的改进多目标布谷鸟搜索算法（IMCS-Task allocation rule-Local search，IMCS-TL）在对电动车辆进行调度时，平均车辆数量和最长搬运时间明显低于IMCS 算法.对任务数为150 的情况进行分析，得到迭代结束时两种算法的帕累托前沿，如图4 所示.从图中可以看出，IMCS-TL 算法的帕累托前沿能向更优解逼近，这是因为IMCS-TL 算法在引入任务分配规则和局部搜索算子后，能够合理地分配任务和确定任务执行序列，减少车辆闲置时间并提高任务分配的均衡性.

3.2 数值分析

为测试本文提出的算法在求解电动车辆点对点物料配送调度问题时的整体性能，设计具有代表性的多目标优化NSGA-II 和MOPSO 算法在相同运行时间下的对比计算实验.三种规模的算法运行时间分别设置为120 s，240 s 和480 s，以帕累托解的个数（NF）、非支配解的最优度（DPS）、解的均匀性（ES）、反世代距离（IGD）作为评价算法性能的指标，各项评价指标计算如下：

表1 不同问题规模下的结果对比Tab.1 Comparison of results between various tasks

图4 任务数量为150 的帕累托前沿Fig.4 Pareto frontier with 150 tasks

3）解的均匀性指标：

式中：Di是xi与其最近邻域解的欧式距离.ES 越小表示解分布越均匀.

4）反世代距离：

式中：P 为真实帕累托前沿面上的解集，用近似前沿代替；v 表示每个分布在真实帕累托前沿面上的个体；d（v，Q）表示v 与算法得到的解集之间的最小距离.IGD 越小，算法的综合性能包括收敛性和分布性越好.

每种问题规模取三种任务情况进行仿真实验，每个任务进行25 次实验并取计算结果的平均值，如表2 所示，其中，加粗字体表示不同问题规模下各项评价指标的最优值.对表2 中的计算结果进行分析可得出以下结论：

表2 三种算法的数值结果对比Tab.2 Numerical calculation results of three algorithms

1）根据表中的NF 指标值可知，IMCS-TL 算法获得的非支配解的数量明显多于NSGA-II 和MOPSO，并且随着问题规模的扩大，它们之间的差距更明显.

2）根据表中DPS 指标值可知，IMCS-TL 获得的解的最优度远高于NSGA-II 和MOPSO，说明IMCSTL 能够获得更高质量的解，具有更好的搜索能力.

3）根据表中ES 指标值可知，从解的均匀性来看，IMCS-TL 和NSGA-II 明显优于MOPSO 算法.IMCS-TL 在中大规模问题下获得的解集比NSGA-II获得的解集分布得更加均匀，这是由于IMCS-TL 采用任务分配策略和局部搜索算子后，IMCS-TL 更容易在当前解附近获得新的邻域解，从而提高解集分布的均匀性，算法具有更好的深度寻优能力.

4）根据表中IGD 指标值可知，IMCS-TL 获得的解的收敛性和分布性明显优于NSGA-II 和MOPSO，这是由于高斯变异和精英选择策略产生并保留了更高质量的解，算法的收敛性和分布性得以提高.

图5 和图6 分别以任务数为90 和250 的一组数据为例，给出了IMCS-TL、NSGA-Ⅱ和MOPSO 三种算法得到的帕累托解集.从图中可以看出，当问题规模较小时，IMCS-TL 能获得比NSGA-II 和MOPSO分布更广的非支配解集，且解的最优度更高.随着问题规模的增大，IMCS-TL 算法与另外两种算法相比优势更加明显，说明其具有更好的全局搜索能力，可以向更优的帕累托前沿逼近.

以上对比测试证明了在相同运行时间下，IMCS-TL 算法能够找到更多且质量更高的帕累托解集，验证了IMCS-TL 在解决汽车装配线点对点物料配送调度问题时的有效性.