考虑可变速度和载重的多AGV任务调度*

张彦如，陈 灏，石 珂

(合肥工业大学机械工程学院，安徽 230009)

0 引言

自动化物料处理是集成制造的关键，目前，由自动引导车辆(AGV)组成的自动引导车辆系统(AGV系统)是最先进的，自动导引车(AGV)是一种无人驾驶的物料处理设备，使用可充电电池和感应电机，遵循引导路径，并由计算机控制。随着生产车间对AGV需求的增加，AGV系统中AGV的数量和车间物料运输的任务也相应增加，因此，如何合理调度AGV任务，设计优化的任务调度方案，使物料分配时间最小化，已成为一个重要的问题。

任务调度的目的是将每个任务分配给合适的AGV，以提高自动化系统的效率，必须考虑AGV的性能，避免碰撞。AGV调度问题基本上分为路由问题和调度问题，本文主要研究调度问题。目前，研究者们已经做了大量的研究和应用。FAZLOLLAHTABAR等[1]对AGV的调度和路径规划问题进行了详细的综述，并对相关方法进行了比较。NISHI等[2]提出了一种双层分解算法，较好地解决了多AGV系统的同时调度和无冲突路径规划问题。RASHIDI等[3]建立了一个最小费用流模型，提出了一种新的算法NSA2，它扩展了标准网络单纯形算法(NSA)，可用于求解多项式时间复杂度的大型问题。另外，常见的路径规划算法包括Dijkstra算法[4]、A*算法[5-6]、人工势场算法[7]、模糊路径规划算法[8-9]等。SUN等[4]对Dijkstra算法进行了改进，增加了AGV的转弯次数和转弯角度作为评价指标，并结合时间窗法建立了多AGV调度系统。WANG、SHEN等[5-6]分别对A*算法进行了改进，并对AGV路径规划问题进行了详细研究。对于多AGV调度系统，静态算法往往效率低下，或者无法解决AGV的碰撞问题，因此SMOLIC等[7]提出了一种时间窗方法，可以有效地解决AGV的碰撞问题。综上所述，大多数学者从任务与AGV同步调度和AGV无冲突路径规划两个方面对调度系统进行优化，使调度系统的效率得到一定程度的提高。在几乎所有AGV调度研究中，都有一个共同的假设，即AGV以恒定的速度运行，但由于实际环境中AGV的速度是可变的，需要在调度系统中考虑AGV的速度。

因此，基于AGV的可变速度和不同的载重电能消耗的不同，本文提出了第3个优化目标，AGV的耗电量。系统消耗的电力越少，碳排放就越少，这不仅降低了运行成本，也保证了作业车间的绿色调度，调度最终的决策需要在3个目标之间进行权衡，最小化最大完工时间意味着需要更多的AGV，且AGV必须是快速运行的，而AGV的速度越高，单位时间消耗的电量越多，而如果要使AGV的数量最小化，则最大完工时间会增加，AGV必须以尽可能高的速度来完成所有的任务，这将导致更多的电量消耗。因此，如何平衡这3个目标是本文研究的重点。

1 多AGV任务调度问题描述与数学模型

在我们的作业车间调度问题中，任务被表示为通过装卸站(L/U)进入和离开的作业序列[12]。本文主要研究AGV在各个工作站之间运输物料的任务调度，AGV可被看成是待分配的资源。本文基于3个目标建立了AGV任务调度的数学模型：①最小化最大完工时间；②最小化AGV的使用数量；③最小化所有AGV的耗电量。

1.1 假设条件

(1)忽略货物的体积，只考虑货物的重量，不考虑AGV自身重量，单个货物的重量不超过AGV的最大承载能力；

(2)AGV消耗的功率与AGV负载的重量成正比；

(3)AGV停放在充电区，直到分配调度命令，AGV在执行任务过程当中不会出现电量不足的情况；

(4)AGV的运行速度可以根据所分配的任务重量变化，每个任务对应一个独立的AGV速度，在运输过程中保持匀速；

(5) AGV执行时默认采用最短路径。最短路径距离是由AGV的起点和终点所决定，且不存在路径问题，碰撞、死锁或冲突等；

(6)AGV每次任务的装卸时间认为固定，包含在运输时间内，AGV可停留在装卸位置；

(7)每台AGV一次只能处理一个任务，每台AGV在同一时间只能执行一个任务，且单个任务中每个工作站只需要一台AGV；

(8)所述任务集为静态任务集，即在AGV处理任务的过程中没有任务新增和终止。

1.2 问题描述与模型

AGV进行物料运输主要包括2个阶段：第1个阶段是从当前位置前往物料所在的存储区，此时AGV处于空载阶段；第2个阶段是AGV在工作站之间运送物料，运到对应的工作站，此时是负载阶段。每完成一次运输，AGV会检查当前电量是否低于电量阈值，电量阈值设定为由当前工作站返回充电区所需最小电量，当电量充足时，AGV直接前往下一任务所在工作站；当电量不足时，AGV需要前往充电区充电，充电完成后再次执行任务。如此反复，直至所有运输任务执行完毕，最后返回充电区，为更加清晰的描述模型，相关参数义总结如表1所示。

本文所建数学模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

STi≥STj,∀i∈I

(7)

(8)

(9)

(10)

(11)

(12)

式中，式(1)～式(3)为模型的目标函数，分别代表最大完工时间最小、使用的AGV数量最小和AGV总耗电量最小；其中最大完工时间由AGV到达任务点所需时间、AGV完成任务所需时间(包括装卸时间)和执行充电任务所需时间3部分组成；式(4)～式(6)分别代表AGV是否参与任务、任务i是否由AGVa来执行以及AGV执行完任务i后是否执行任务j，两个变量均为0～1变量；式(7)为时间约束，表示下一任务开始时间晚于上一任务完成时间；式(8)计算的是AGV返回充电区域所需电量；式(9)表示AGV运行速度与其负载和电量的关系；式(10)为执行充电任务所需时间，当AGV的电量不足以完成任务时，AGV需要执行充电任务；式(11)决定了一个任务只能由一台AGV执行一次；式(12)是等式约束，分别表示AGV到达任务点所需的时间、完成任务所需的时间以及AGV的充电时间，由于AGV在处理自身任务时，会选择最短路径，且最短路径距离是由AGV的起始点和结束点唯一确定的，这3个变量都由AGV的速度决定。

2 改进算法设计

遗传算法通过对问题进行编码解码，适应于各类问题且易于操作，且对种群的遗传操作是并行的，因此算法具体较强的全局搜索能力，被广泛的应用到作业车间调度问题上，但是现有遗传算法存在初始解质量低和进化后期收敛速度慢两个方面的问题，针对此，本文提出了一种改进的自适应遗传算法，通过对初始种群和交叉变异概率自适应策略的优化，提高初始种群的质量和算法的收敛速度。

2.1 染色体表达与编码

遗传算法有很多种编码规则，包括二进制编码、浮点数编码以及实数编码等。针对本文所研究内容，采用了一种双层实数编码方法，每一条染色体代表一种任务分配计划，由不同的AGV配送任务组成，染色体的前半部分表示AGV编号i，后半部分染色体片段表示AGV执行任务时的速度。每台AGV在同一时间只能执行一个任务，因此，染色体上的基因编码可以表示AGV的序号，基因序列为任务集，需要找到可以完成该任务的最优分配方案，用以平衡3个优化目标。染色体如图1所示，图中代表任务1由2号AGV完成，AGV的速度为1.0 m/s。

图1 染色体编码

2.2 种群初始化

对于算法进化来说，初始种群的选择非常重要，传统遗传算法和现有的改进遗传算法在初始种群选择时大多采用随机生成的方法，以保证选择的随机性和初始种群个体的多样性，但初始种群的质量将直接影响到世代的进化，随机生成的种群可能会导致初始解的质量低下，从而增加迭代次数。为了保证初始种群的多样性并提高初始种群的质量，本文引入了种群熵，初始种群的创建步骤如下：

步骤1：根据可供调度的AGV数量，确定AGV的编号范围[1,M]；

步骤2：用创建任意离散随机种群的方法，对个体的每个基因位产生一个随机数ri，个体基因的位数等于车间中工作站的总数；

步骤3：为了提高种群多样性，引入种群熵，算法每隔几代根据当前种群内个体的适应值估计种群熵，更新控制参数，从而得到更优秀的种群；

步骤4：重复上述步骤N次，产生一个包含N个个体的初始种群。

该方法既继承了传统遗传算法在选择机器时选择的随机性，又大大提高了初始种群的质量。

2.3 适应度函数

对于多目标优化问题，由于目标之间一般是相互冲突的，因此需要寻求多目标之间的帕累托最优解，帕累托效率意味着资源以最有效的方式分配。因此，可对每一个子目标函数fi(x)赋予权重ωi，其中ωi表示相应的fi(x)在多目标优化问题中的评价函数，则整体适应度函数可表示如下：

f(x)=∑ωi·fi(x)

(13)

由于这是一个极小化问题，我们选择目标函数的倒数作为适应度函数，即：

(14)

在本研究中，设置3个目标的权重分别为0.6、0.24和0.16。为了使3个目标具有相似的变化范围，调整系数分别为1、30和20，从而得到整体适应度函数的表达式为：

(15)

2.4 交叉操作

图2 交叉操作

交叉操作是将两个配对的染色体部分基因交换从而形成两个新的染色体，该操作不能过多破坏个体中表现优良的编码串，交叉操作是为了产生不同多样的AGV任务分配方案，可以增大任务分配解空间的搜索范围。交叉方法采用子路径交叉(subtour exchange crossover)方法，假设父代1:α[p1]=a,b,c,d,e；父代2:α[p2]=c,d,e,b,a，从两代父染色体中随机选取基因a,b,e，位置可以不连续，但是两染色体被选基因相同，然后将这两个基因从中选取出来，并且在对应的子代中使它们与原父代中的位置一样，然后按照基因的出现顺序，交换两父代染色体中的位置，一次生成两个子代，具体操作如图2所示。

2.5 变异操作

为了增强遗传算法的局部搜索能力并且能够提高种群的多样性，变异操作将染色体编码串中的某些基因进行改变，从而使遗传算法以良好的搜索能力来完成最优化的过程。本文采用基因段两点变异法的变异模式，其具体操作过程如下：

步骤1：在父代基因序列parent1上随机产生两个变异点，此处随机取两个位置为变异点，如图3所示。

图3 两点变异法

步骤2：在子代染色体变异点对应的位置，将此处基因替换为其他的基因值，此处新替换的基因来源于对应任务的可选AGV集合。

步骤3：将父代基因序列parent1中除了变异点位置意外的所有基因值进行复制，遗传到子代中，保证其基因值和顺序与父代一致。

根据以上步骤进行变异，可以得到新的子代染色体基因序列offerspring1。

2.6 改进的自适应策略

遗传算法的交叉概率Pc和变异概率Pm是决定遗传算法性能好坏的关键，所以通过引入自适应策略，Pc和Pm就可以随适应度值自动改变，在保证种群多样性的同时，保证算法收敛性，这也是自适应遗传算法相对普通遗传算法来说的优点所在，Pc和Pm可以按照式(16)、式(17)进行调整：

(16)

(17)

式中，gmax为种群最大的适应度值；ga为种群的平均适应度值；g′为要交叉的两个个体中较大的适应度值；g为要变异个体的适应度值；k1、k2、k3、k4为4个常数，取值范围在0～1之间。

虽然传统的自适应遗传策略可以很好地保留优解，并且容易找到围绕局部最优解的全局最优解，但这种方法在进化的早期阶段并不理想。在早期阶段，优解的概率值非常小，因此它们的优秀模型无法有效分散，优解几乎保持不变状态，导致其在进化的后期，很难跳出原来的局部最优解，最终会导致算法的搜索速度非常缓慢，甚至停滞。

本文为了克服上述问题，在自适应交叉变异概率的基础上，提出了一种改进的自适应策略，利用3个加权参数Pc(m)min、Pc(m)max、Pc(m)mid使其在不同适应度之间具有约束，交叉概率可以根据种群进化情况进行连续自适应调整。在进化早期，为了避免在局部最优时过早收敛，通过调整参数，使交叉和变异概率偏高，提高了全局搜索能力，增加了种群的个体多样性。在进化后期，个体适应度值较高，如果算法仍然随机无目的搜索，则会导致收敛速度慢，此时通过调整加权参数来降低交叉和变异概率，以提高收敛速度。设置自适应交叉概率如下：

(18)

(19)

式中，Pcmin和Pcmax分别为交叉概率取值的最小值和最大值，交叉概率一般取值范围在[0.6,0.8]；Pmmin和Pmmax分别为变异概率取值的最小值和最大值，变异概率一般取值范围在[0.01,0.1]；Pc(m)mid为两者取值的中位数。

2.7 迭代终止

本文采用的终止条件是连续8代种群均值没有变化就停止迭代。通常GA迭代终止条件是连续数代目标值或最优解不发生改变就停止，但很多时候往往经过几次迭代种群中最优个体虽然未发生变化，种群均值却仍在变化,种群还在不断进化，此时迭代终止，会阻止更优解的产生。只有当种群均值数代不发生变化时，说明种群已经停止进化，最优个体已不会发生改变，才能终止迭代。

3 实例

3.1 车间布局及相关数据

图4 车间布局图

为验证模型的有效性，借鉴文献[9]和文献[11]，建立车间工作站模型，如图4所示，图中白色方块代表AGV完成所需任务所到达的工作站，每个工作站有各自的坐标，工作站与工作站之间的距离，可用曼哈顿距离来表示，由此可以得到AGV的移动距离，黑色代表物料储存区，AGV在装卸站卸下物料后，如果电量充足，可以继续进行下一个任务，否则需要返回充电区充电，充电区位置位于X轴上，坐标可表示为(5,3)。在本文的仿真试验中，假设有50个任务需要完成，可用AGV数量为20辆，AGV速度从0.5 m/s～1.5m/s不等，AGV驱动过程中单位载重电能系数α取0.001。

3.2 实验结果分析

假设车间中所有工作站都需要配送物料，本文通过一种改进的自适应遗传算法，在MATLAB环境下对多任务多AGV调度模型进行了仿真，算法参数的相关设置为：种群规模为100，最大迭代次数为200，选择率为0.5，初始交叉概率为0.8，初始变异概率为0.07。

图5 基于传统遗传算法的任务调度甘特图

图6 基于改进遗传算法的任务调度甘特图

表2 算法测试结果

传统遗传算法和改进自适应遗传算法迭代搜索过程分别如图7和图8所示，传统的遗传算法约在第125代收敛，改进的自适应遗传算法约在第68代收敛。

图7 传统遗传算法迭代过程 图8 改进自适应遗传算法迭代过程

可以看出，IAGA算法在收敛速度方面表现良好，且具有较强的全局搜索能力，因为IAGA的交叉率和变异率是基于个体的适应度值自适应调整的，如果个体适应度值较大，则交叉和变异的比率将较低，因此大的基因序列更自然地进入下一代而不被破坏。因此，IAGA的应用有助于快速找到合适的解决方案。

4 结束语

本文以作业车间中多AGV任务调度为研究对象，首先考虑AGV运行时在运载不同重量物料时的速度差异，同时在功耗中引入重量系数，建立了多目标调度模型，指导AGV在物料配送过程中的调度。然后，针对该模型，采用了一种改进的自适应遗传算法，通过引入种群熵改进初始种群质量，并提出了一种改进的自适应策略，使得交叉率和变异率在迭代的各个时期根据适应度值的变化进行合理地调整。最后，在MATLAB环境中进行了仿真试验，获得了多任务调度的近似最优调度，并对比了传统遗传算法与改进自适应遗传算法的调度结果以及迭代过程差异。仔细比较前后的数据，实验结果表明，在合适的速度下，使用较少的AGV可以完成所有任务的调度，从而缩短了完工时间，减少了AGV的使用数量，降低了总功耗。并且每个优化目标的值降低了25%，着重证明了模型和IAGA的有效性。