基于混合禁忌蝙蝠算法的AGV物料配送调度研究*

魏永来，龙 伟，李炎炎，石小秋，严佳兵

(四川大学 制造科学与工程学院，成都 610065)

0 引言

随着工业4.0和智能制造2025等国家重大战略的提出，对生产制造领域的自动化水平和智能化程度的要求将会越来越高；而现如今，生产制造的含义也不仅仅只限于工厂与车间，更是衍生到了大生产，大物流以及大数据融和于一体的智能制造系统。在此背景下，像工厂与车间之间这样短时短距的局部物流是否能高效的运作则显得至关重要。自动导引小车(Automated Guided Vehicle，AGV)作为一种灵活高效的小型运输设备，在制造系统、仓储系统以及港口码头等领域得到了广泛的应用[1]。

AGV具有灵活性好、易于控制、智能化程度高等显著特点，使用AGV进行物料运输可以方便地重组系统，达到运输过程的柔性化；与传统的人工或半人工的方式相比，减轻了劳动强度，降低了危险性，提高了生产效率[2]。近年来，关于作业车间的AGV调度问题也吸引了大量学者的关注，目前主要的求解算法有遗传算法、粒子群算法、差分演化算法、禁忌搜索算法、模糊决策算法等[3-7]以及相关的组合或改进优化算法[8-9]。

蝙蝠算法(Bat Algorithm, BA)作为一种新兴启发式算法，具有结构简单、参数少、鲁棒性强以及易于理解和实现等优点[10]，已被广泛的应用于函数优化、模式识别和生产调度等领域。但是到目前为止，鲜有学者将蝙蝠算法应用于AGV调度问题。同其他智能优化算法一样，基本蝙蝠算法存在易陷入局部最优而导致早熟收敛问题，因此对基本蝙蝠算法进行了改进，提出了一种求解作业车间多AGV物料配送调度问题的混合禁忌蝙蝠算法(Hybrid Tabu Bat Algorithm，HTBA)。

1 AGV作业调度模型

1.1 调度问题的描述

本文研究的作业车间物料配送调度问题的实质是在能够保证准时性、经济性以及行走总路程最短的前提下AGV数量的配置问题。可以具体描述为:在某作业车间的各个物料库存放有加工生产所需的若干物料，根据特定的车间加工工艺流程，在给定的小车行走路径、物料装卸站点、加工工位、车间布局及小车行走规则以及相应加工工位的需求时间和每个加工步骤所需的物料数量等一系列条件约束下，将各种加工物料用AGV搬运到目标工位以满足生产的要求，求解完成上述车间物料配送调度要求的最佳AGV数量并给出相应的调度时间表。在一个生产节拍内，AGV从停靠站出发，在物料库和工位之间不断往复循环执行配料任务，并在每次加工结束后将成品运回仓库储存。具体的AGV作业过程如图1所示。

图1 AGV作业过程示意图

1.2 模型分析

在一个作业车间小物流系统中，物料区和生产区的布局方式，AGV的行走方式以及物料运输的难易程度，都会对调度问题的评价指标产生重要影响。因此为了取得更好的 调度效果，通常把车间物料调度视为一个整体的系统来建立模型[11]。

基于以上分析，对本文研究的AGV物料配送系统，假设以下条件成立:

(1)车间物流系统中的各个物料库和各个工位的位置都是确定的；

(2)生产过程中每一个工位加工所需的物料都由特定的物料库进行补给配送；

(3)生产指令的下达是任意的，即每一个AGV都可以接受该任务；

(4)在单位生产节拍内，每个物料库与每个工位之间只需配送一次；

(5)AGV每次的运载量和AGV的运行速度都限定在一定的范围内；

(6)AGV给每个工位的供料时间应小于生产节拍，即在每一个产品加工完成之前必须完成该时段加工所需全部物料的供应；

(7)AGV在行进的过程中不会发生撒料和碰撞，且每辆AGV都只允许在供料通道上单向行驶；

(8)每辆AGV的配料初始位置都是确定的，当AGV完成一个生产节拍内所有配料任务后返回初始位置。

1.3 数学模型的建立

首先定义以下参数：

作业车间生产线上的生产节拍为G，物料库的编号为m，共有M个物料库；生产线工位编号为n，共有N个工位；AGV的编号为k，共有K辆小车；配送任务的编号为r，一个生产计划周期内总任务数为R，即M个物料库与N个工位之间存在配送关系的路径总条数也为R。为了明确各个任务与物料配送路径之间的对应关系，建立一个任务资源库，在任务资源库中实现任务编号与对应的AGV配送路径之间的匹配；如任务1代表由1号物料库向1号工位供料。

对于整个车间物流系统，分别用S、T和C表示一个生产计划周期内所有AGV的总行走路程、总运输时间和总配送成本。分别用矩阵α、矩阵β和矩阵χ表示AGV从特定配料区到指定工位之间的行走距离、运输时间和配送成本。矩阵Xkr表示编号为k的小车执行第r次配送任务时配料区与工位之间的对应关系[12]。即：

根据问题的描述建立的数学模型如下：

f(k)=min{S，T，C}

(1)

式中，k为决策变量；此模型的实质是实现多个目标的结果最优化，下面分别对总行走路程S、总运输时间T和总配送成本C进行说明。

1.3.1 总行走路程

1.3.2 总运输时间

这里的总配送时间，除了受式(3)～式(6)的约束外，还需要限定不同任务的作业顺序以及作业时间。式(8)限定了当物料库m需要向多个对应的工位输送物料时的配送顺序；式(9)表示编号为k的AGV完成第r个配料任务的时间等于第r-1个配料任务的完成时间、AGV在第r和r-1个任务之间的配送时间以及装卸物料时间之和；式(10)限定了每辆AGV单位时间内供料总时间应小于生产节拍。其中：Tkr表示编号为k的AGV完成第r个配料任务的时间，Tr(r-1)表示AGV由第r-1个任务到第r个任务所消耗的时间，Ta为AGV的平均物料装卸时间，对于每辆AGV，每执行一次物料配送的任务，Ta只需计算一次。

1.3.3 总配送成本

(11)

s.t. 式(3)～式(6)

2 混合禁忌蝙蝠算法

基本蝙蝠算法是学者Yang根据自然界中蝙蝠所具备的回声定位能力而提出的一种元启发式算法[13]。针对作业车间多AGV物料配送的调度问题，本文在基本蝙蝠算法的基础上，提出了一种混合禁忌蝙蝠算法，该算法能够有效地避免算法早熟收敛、提高算法的全局搜索能力和精度，增强求解的稳定性。

2.1 编码与解码

作业车间调度问题一般都是离散型组合优化问题，而基本蝙蝠算法中每个个体位置均为连续值，因此运用蝙蝠算法求解多AGV物料配送调度问题时，首先要明确解空间和问题空间之间的映射关系，即如何合理的设计算法的编码与解码方式使其能够实现随机值与调度解之间的转换。本文采用文献[14]中的ROV规则来进行蝙蝠个体位置向量与可行调度解之间的转换。具体的转换过程如图2所示。

图2 编码转换方案

本文采用基于任务的单层整数分段编码策略，为每个任务提供2个编码位，即编码长度为2R。每个任务编码序列中的第一位表示AGV编号，第二位表示AGV执行配料任务的顺序；如编码序列113212...521中前两位11表示编号为1的AGV第1次配料是完成任务1,32表示编号为3的AGV第2次配料是完成任务2，以此类推。

2.2 种群初始化

在算法的初期，需要对种群进行初始化操作，由于编码序列中每个编码位的取值范围不同，且整个编码序列必须具有一定的实际意义，故采用如下的种群初始化方案：

步骤1 ：以工位数量N作为初始AGV数量，随机生成R个1～N之间的整数作为各任务段第一个编码位的值。

步骤2 ：若某几个任务段的第一个编码值相同，则进行随机排序作为第二个编码位的值，否则记第二个编码位的值为1。

步骤3：按从左至右的顺序依次生成直至把所有的编码位填充完整。

重复以上步骤若干次，即可得到一定规模的初始化蝙蝠种群。对于HTBA算法，种群初始化完成后，在搜索空间中，还需对蝙蝠个体的运动方式作出如下限定：

fk=fmin+(fmax-fmin)×rand

(12)

vk(t)=vk(t-1)+(xk(t-1)-x*)fk

(13)

xk(t)=xk(t-1)+vk(t)

(14)

xnew=xold+εAt

(15)

式(12)中，fk、fmin、fmax分别表示第k只蝙蝠个体在当前时刻发出的声波频率以及声波频率的最小值和最大值；rand是0～1之间的随机数，x*表示当前范围内全局最优解。式(13)、式(14)分别表示蝙蝠个体在t时刻速度与位置的更新过程。式(15)中，xold表示随机选择的一个最优解，At表示当前蝙蝠群体响度的平均值，ε表示在[-1,1]范围内的随机数。

2.3 脉冲频度和响度的更新

在蝙蝠个体的运动过程中，需要对每个个体的脉冲频度和响度进行更新，其中脉冲频度会影响个体执行局部搜索的概率，响度则影响着接受新解的概率。在初始时刻个体的脉冲响度较大，脉冲频度较小；但随着搜索过程的推进，脉冲响度会逐渐减小，脉冲频度逐渐增加，二者不断更新变化使算法结果最优化。本文采用如下的方法对个体的脉冲频度Rk和响度Ak进行更新。

Ak(t)=φAk(t-1)

(16)

Rk(t)=Rk(0)×{1-exp[-γ(t-1)]}

(17)

上述两式中，φ、γ均为常量，且满足0<φ<1，γ>0。

2.4 禁忌搜索与局部寻优

2.4.1 禁忌表

为防止算法在搜索过程中出现循环，在基本的蝙蝠算法中，引入禁忌搜索算法中的禁忌表，使得蝙蝠个体在一段时间内，不会重复地停留在同一个地方，使得算法更趋于全局的搜索。

在本文的HTBA中，通过每只蝙蝠个体的位置信息变化来决定是否将该蝙蝠加入禁忌表。当蝙蝠个体在算法迭代过程中产生重复时，就会被纳入禁忌表，成为被禁忌的对象，这些对象需要经过一定的算法迭代次数才能从禁忌表中释放出来，而迭代次数的多少通常由禁忌长度决定。如果禁忌长度越小，算法的计算时间就越短从而提高算法的效率；但是如果禁忌表的长度过小，又容易使算法陷入循环从而影响算法的性能，因此，选择合适的禁忌长度至关重要[15]。在本文的算法中，设定禁忌表的长度为固定值。

2.4.2 藐视准则

在算法迭代中，当出现候选解全部被禁忌或者存在一个优于当前最优状态的禁忌候选解的情况时，此时藐视准则将会使某些状态解禁，以此来实现算法更高效的优化性能。本文采用基于适应度值的准则：若存在某个禁忌候选解的适应度值优于当前最优状态，则解禁此候选解为当前解和新的当前最优状态。

2.4.3 局部寻优

针对AGV作业调度离散化的特点，在算法的局部寻优过程中定义如下两种用于邻域搜索的扰动操作[16]：

(1)元素插入。在蝙蝠个体位置编码序列中，随机选择两个对应位置的元素，并将前一个元素插到后一个元素后面。

(2)元素交换。在蝙蝠个体位置编码序列中，随机选择两个对应位置的元素，并交换二者的位置。

具体的局部寻优过程如图3所示。

图3 局部寻优流程图

2.4.4 适应度函数的选择

算法中蝙蝠个体位置的优劣由适应度值函数衡量，而适应度值函数通常由求解问题的目标函数决定。本文所述调度模型的目标函数是在实现AGV总行走路程S、总运输时间T和总配送成本C三者最优化的前提下给出最佳的AGV数量配置。因此，将适应度值函数设置为：

(18)

其中，k为AGV小车数，δ为比例因子,θ1、θ2、θ3分别为总行走路程、总运输时间和总配送成本的权重贡献系数。

2.5 算法的实现步骤

HTBA算法的流程示意简图如图4所示。

图4 HTBA算法流程简图

其具体的实现步骤如下：

步骤1：种群初始化，设置算法相关参数。

步骤2：依次对每个蝙蝠个体进行适应度值评价，找出当前最优个体并判断终止条件。

步骤3：设定禁忌表的长度并初始化禁忌表。

步骤4：按照2.2节中的公式更新蝙蝠个体的位置和速度。

步骤5：对于每个蝙蝠个体，若满足rand>Rk，则采用局部寻优策略对当前最优个体进行局部搜索产生一个新解。

步骤6：评价产生的新解，若优于当前最优解且满足rand

步骤7：根据2.3节中的公式更新蝙蝠个体的Rk和Ak。

步骤8：更新当前最优个体位置，并判断是否存在禁忌表中，若不是则更新禁忌表。

步骤9：终止条件检查。若满足，则解码输出最优解；否则转到步骤4。

步骤10：算法结束。

3 仿真实验与分析

采用Matlab编程语言对本文提出的混合禁忌蝙蝠算法进行编程，程序的运行环境为Win7系统下内存为4GB的Intel(R)Core(TM) i3-4170 CPU 3.70GHz的PC机。

3.1 案例计算

算法相关参数设置如表1所示。

表1 HTBA算法参数

以解放军某工厂的一作业车间生产线为例，验证算法的有效性。该生产线共有10个工位，增加一个0工位，用来表示AGV停靠站的位置；加工物料分为四类，分别记为物料库A、B、C、D，其中物料库A对1、2、4、8号工位供料，物料库B对2、3、6、7号工位供料，物料库C对7、9、10号工位供料，物料库D对4、5、8、9号工位供料。车间的生产节拍G为16min/台;AGV的平均装卸物料时间Ta为1min。经过测算，各物料库与各个工位的距离，运输时间和配送成本，分别如表2～表4所示。

表2 各物料库至各工位距离(单位：m)

表3 各物料库至各工位运输时间(单位：min)

表4 各物料库至各工位配送成本(单位：￥)

根据上述案例给出的原始数据，并结合AGV作业调度模型的相关约束条件，编程得到算法运行后的调度结果如图5、图6所示。

图5 最优解甘特图 图6 最优个体适应度值变化曲线

由图5可知，对于该作业车间，在满足生产要求的前提下，至少需要6辆AGV进行物料配送，求解出的最优调度方案对每辆AGV的配送路径和物料运输时间都进行了合理的规划。由图6可知，算法在迭代到第48次时即达到最优状态。

3.2 算法对比分析

为了进一步验证本文算法的优越性，对上述案例，分别用基本蝙蝠算法、禁忌搜索算法和遗传算法等在Matlab中进行编程求解，得到的结果对比如表5所示。

表5 算法结果对比

由以上对比可知，相较于其它算法，本文提出的混合禁忌蝙蝠算法，对于结构简单的分布式作业车间的物料调度问题，具有很好的适配性，能够得到较为理想的结果。

4 结论

本文提出了一种混合禁忌蝙蝠算法来求解在总行走路程、总运输时间、总配送成本等多目标约束下的作业车间多AGV调度问题。此外，为了避免算法的早熟收敛，引入禁忌搜索和局部寻优策略来提高算法寻优能力。最后，通过对某实际生产加工作业车间进行仿真实验，结果表明了本文的HTBA算法在解决作业车间多AGV物料配送调度问题中的可行性和高效性。同时，基于本文的研究结果，在今后可以将蝙蝠算法与其他一些智能优化算法进行结合，来求解其它类型或更加复杂的车间调度问题。