AGV作业调度模型及改进的DE算法研究

杨锋英，刘会超

YANG Fengying1,LIU Huichao2

1.黄淮学院 信息工程学院，河南 驻马店 463000

2.黄淮学院 网络信息管理中心，河南 驻马店 463000

1.School of Information Engineering,Huanghuai University,Zhumadian,Henan 463000,China

2.Center of Network Information Management,Huanghuai University,Zhumadian,Henan 463000,China

1 引言

随着信息化的深入，许多企业建立了自动化立体仓库系统（Automated Storage and Retrieval System，AS/RS），用于对生产物料和产品进行集中化的管理和配送。和传统仓库相比，AS/RS实现了货物存储的立体化、自动化和智能化。而自动化搬运系统在其中扮演了重要角色。常用的自动化搬运设备有堆垛机、传送带（轮）和自动导航小车（Automatic Guided Vehicle，AGV）等。不同规模的仓库会根据功能需求采用不同的搬运设备组合。随着柔性制造需求的不断增长，AS/RS与企业生产环节逐渐相互融合，出现了集成生产的AS/RS系统。在集成生产环境中，AGV是连接仓库和生产车间的重要纽带，成为AS/RS中不可缺少的重要组成部分。

AS/RS系统的运行效率与出入库作业的优化调度效果密切相关。作业调度的任务是对用户提交的多个作业进行重新排列并分配到合适的自动化搬运设备执行，使作业的整体运行时间最少。作业调度是一种逻辑层次的全局调度，具体调度过程要依据底层自动化搬运设备的运行状态信息。在由多种设备构成的搬运系统中，一项作业的执行时间是各个设备运送时间的累加，作业调度具有管理和协调各种搬运设备的作用。若搬运系统只有一种搬运设备，则作业调度等同于直接对搬运设备的调度。在集成生产的AS/RS环境中，AGV运行最为耗时，对整个自动化搬运系统的效率具有决定性影响。因此，可将集成生产环境中的作业调度问题简化为AGV的作业调度问题。

在关于AS/RS的各种优化研究中，关于巷道分拣系统的存取优化[1]和AGV小车在自由空间移动时的路径规划优化[2-5]的研究比较多，也比较成熟。关于作业调度的研究则比较少。甘剑锋等[6]用排队论理论对AGV调度系统进行建模，得到了一个M/G/1模型，并用该模型对AGV调度效率进行了分析。金芳等[7]用排队论理论对AGV调度系统建立了一个M/M/1模型，并对调度效率进行了分析。雷定猷等[8]从柔性制造的一般环境出发对AGV调度系统建立了一个多AGV多请求的一般优化模型，并提出了一种求解的遗传算法。文献[9-10]简化了AGV调度的相关约束，建立了一个简化的优化模型，并分别提出用遗传算法和PSO算法来进行求解。但总体来说，目前对AGV作业调度问题的研究还很不成熟。

差分演化算法（DE）是模拟大自然的演化过程而提出的一种基于种群的随机搜索算法[11-12]。自提出以来，其优异的优化性能已经得到了普遍的认可，并应用在很多优化领域[13]。本文首先对AGV作业调度问题进行了分析，建立了问题的优化模型，并分析了模型的特点。AGV作业调度问题可以抽象为一种带约束的多重TSP问题，也是一种NP完全问题，当前并不存在可在多项式时间内确定求解的算法。为此，本文针对优化模型提出了改进的差分演化算法，引入了新的两段编码方法和基于生存时间的个体重置机制。模拟实验结果验证了改进算法的有效性。

2 AGV作业调度问题

2.1 问题描述

在集成生产的AS/RS环境中，用户在生产车间通过管理系统发出货物的出入库请求，而AGV的任务就是接收管理系统的调度在仓库和工作间之间运送货物。因此，AGV是联系仓库和工作间的重要纽带。当用户提交的作业较少时，AGV只需要依次执行各个作业即可，不涉及调度问题。但当用户提交的作业远大于现有AGV数量时，AGV按不同的顺序执行作业对系统的运行效率有很大影响，因此需要合适的优化调度算法来决定如何向AGV分配作业以及让AGV按什么顺序执行这些作业[10]，这就是AGV的作业调度问题。

AGV系统是一个涉及多个环节的复杂系统，作业调度优化的效果也会受到多方面因素的影响。为更好地探讨问题的本质和求解策略，有必要对问题进行必要的简化和说明。

（1）AGV作业调度贯穿于仓库运行的整个过程，因此，实际的AGV作业调度问题属于典型的动态调度问题，这类问题往往难以求解。为降低求解难度，可假设整个调度过程由一系列的调度周期组成，在每个调度周期内待调度的作业数量是稳定的。这就可将复杂的动态调度问题转化成一系列离散的静态AGV作业调度问题。

（2）在度量一个作业的执行代价时，需要计算AGV在执行作业时所经过路径的距离。在某些应用环境中，AGV的运行路径无法事先预知，需要专门的路径规划功能动态确定，这已超出了本文的讨论范围。故此处假定所有AGV的运行路径都是已知且稳定的。

（3）某些仓库环境中，AGV执行完一项作业后，必须回到驻点才能执行下一项作业。此种情形下，作业优化调度的效果有限。故本文假定AGV执行完一项作业后直接执行队列中的其他作业，只有在作业队列为空时才会回到驻点。

（4）为了问题表述的方便，假设AGV的运行速度是恒定的，其运行时间与路径长度成正比。

2.2 作业执行过程

AGV执行一项作业需要经历两个阶段。假设有一台AGV初始停靠在驻点处。当接收到执行作业命令时，AGV要先从驻点出发到达作业的起始点。这是作业执行的第一阶段，此时AGV处于空载状态，并不实际运送货物，是作业的准备阶段，花费的时间称为作业准备时间(tp)。接下来，AGV将作业起点处的货物装载，并运送到作业指定的目的地，完成作业。这是作业执行的第二阶段，属于作业的执行阶段，花费的时间称为作业执行时间(te)。此时，如果还有其他待执行的作业，AGV直接移动到下一项作业的起点，然后将货物送达作业指定的目的地。如此反复，直至所有作业执行完毕，AGV返回到驻点等待。

作业执行阶段是作业执行的重要组成部分，但其时间是直接可预测的。一旦作业的起点和终点确定，不论作业的调度次序如何变化，作业从其起点到终点需要的运行时间相对稳定，与两点间的执行路径距离成正比。当仓库和生产车间的布局结构确定后，布局内点到点的路径会随着系统的持续优化而趋于稳定，因此，可将不同的路径抽象为一个带权图（权为两点间的距离）存储在系统内。由于AGV的运行速度是已知的，则AGV在两点之间的运行时间te可由公式（1）求出。

其中，dmn为两点m和n之间的距离，v是AGV运行速度。作业执行的准备时间与AGV的当前位置密切相关。除了AGV在驻点的情况，AGV的当前位置是前一项作业的终点，会随着作业执行顺序的变化而不同。因此，AGV需要执行哪些作业以及按什么顺序执行这些作业都将影响到作业的执行效率。这也正是AGV作业调度主要任务。AGV作业调度是集成生成环境下仓库管理系统的重要功能之一。采用合理的作业调度策略来优化AGV的执行作业过程，对提高自动化仓库的运行效率起到至关重要的作用。

2.3 调度优化模型

设有m个AGV和n个待执行的作业。用Ai(i=1，2，…，m)表示第 i个AGV，Ji(i=1，2，…，n)表示第 i个作业。AGV执行作业Ji需要的总时间ti为：

其中tpi是AGV从前一作业的终点移动到当前作业起点所花费的时间，是执行作业Ji的准备时间；tei是AGV从当前作业起点运送到作业终点所花费的时间，属于作业的执行时间。

在大多数情况下，AGV总是连续地执行多个作业。设将作业队列中的个作业分配给 Ai，则 Ai执行si个作业需要的总时间Ti为：

当有多个AGV时，每个AGV并行执行所有的作业。m个AGV并行执行完所有作业的总执行时间为：

此外，每项作业还可能存在完成时间的约束。设作业Ji的请求时间为tqi，限定的最迟完成时间为tci。在每个AGV执行队列中，作业Ji的执行完成时间tri为：

则作业Ji的约束条件满足程度ei可定义为：

则所有n个作业的总体约束条件满足情况E为：

作业调度的最终目标就是找出最优的作业执行序列和分配方案，使得所有作业总的执行时间最小且满足所有约束条件。即

2.4 模型分析

当环境中只有一个AGV时，AGV作业调度问题只需合理安排作业的执行顺序，不涉及作业的分配问题，此时，该问题等价于一个带时间约束的TSP问题。在实际的生产过程中，AGV数量一般有多台。此时，AGV作业调度问题可近似为带时间约束的多重TSP问题。由于TSP或多重TSP问题已被证明是NP完全问题[11]，显然AGV作业调度问题也是一个NP完全问题，当前还找不到可以在多项式时间内求解该问题的确定性算法。

在不考虑约束的情况下，AGV作业调度问题的求解空间非常巨大。将n个作业分配给m个AGV有mn种组合。设每个AGV被分配si(i=1，2，…，m)个作业，则每个AGV执行所有作业的顺序有si!种不同选择。设s=max(si)，则AGV作业调度问题的搜索空间为：s.mn。可见，随着作业和AGV数量的增加，问题求解空间呈指数增长。

3 改进的差分进化算法（IDE）

3.1 差分进化算法简述

差分进化算法是由Storn和Price于1995年提出的一种基于种群的随机搜索算法[11-12]，其主要原理是模拟自然界“优胜劣汰、适者生存”的进化法则。DE算法具有迭代过程简单，控制参数少，寻优能力强等特点，自算法提出以来，就得到了广泛的关注和快速的发展。研究者已针对不同的问题提出了多种DE变体。当前，除了传统的函数优化领域外[14-15]，DE在组合优化、约束优化以及众多实际工程领域都得到了成功应用[13]。

和遗传算法类似，DE的基本操作也包括：变异、交叉及选择三种操作。在计算迭代中，算法随机选择两个不同的个体向量相减产生差分向量，然后将差分向量赋予权值后与另一随机选出的个体向量相加，从而生成变异向量。变异向量与目标个体向量进行混合交叉，得到测试个体向量；然后测试个体与原目标个体进行一对一竞争，择优生成新一代的种群。

变异操作是DE算法的核心操作，这也是其与遗传算法的主要区别。在DE算法中，变异操作将父代种群中多个个体进行线性组合生成变异向量，其中最基本的变异成分是父代个体的差分向量。以广泛使用的DE/rand/1变体为例，变异向量vi定义如下：

其中，{xr1，xr2，xr3} 是在父代种群中随机选择的三个个体，且 r1≠r2≠r3≠i，NP为种群规模，且满足 NP≥4，F为缩放因子。

交叉操作的目的是产生测试向量，并通过变异向量和目标向量各维分量的随机重组以提高种群个体的多样性。常用的交叉操作有二项交叉和指数交叉。通过指数交叉产生测试向量如式（10）所示。

其中 n，L∈[0，D-1]，D为问题维度，n为随机选择的正整数，L的生成由交叉因子Cr∈[0,1]控制，通过循环累加获得表示求模函数，D为模数。

DE算法的选择操作采用精英保留模式，当且仅当测试向量ui的个体适应值比目标向量xi的适应值更好时，ui才会被种群接受。否则xi仍将保留在下一代的种群中。在最小化问题中，选择操作如式（11）所示。

其中，t为当前演化代数。通过父代和子代的竞争和优胜劣汰，子代种群总是优于或等于父代种群，从而使种群始终向最优解的方向进化。

3.2 算法改进策略

虽然DE算法及其变体在求解各类优化问题时表现出了优异的性能，但并不存在可以求解所有优化问题的统一算法。针对不同的问题，DE算法要在编码方式、变异策略、控制参数等方面需要作出必要的调整和改进。由于AGV作业调度问题的优化结果既要确定作业集的分组方式，并把每个分组恰当地分配给特定的AGV，又要确定每个分组内作业的执行顺序。这是传统的个体编码方式所无法解决的，需要设计新的个体编码方式。而编码方式的改变必将导致算法在种群初始化、交叉变异策略及适应值评估方式等方面的变化。

3.2.1 两段编码方式

传统的单序列个体编码方法无法同时解决AGV作业调度问题中面临的作业集分组优化和作业执行顺序优化两个问题。为此，本文设计了一种新的两段编码方法。如图1所示。

图1 两段编码方式示意图

每个个体的编码由两段构成。第一段为作业段，由所有作业 Ji(i=1，2，…，n)的编号排列构成，包含了所有作业的分组分配和执行顺序信息。分组分配信息要结合后面的分配段来确定。分配段由m-1个位置指针Pi(i=2，3，…，m)组成，指针 Pi的值表示第 i个AGV需要执行的作业子序列在作业段的开始位置，同时也表示第i-1个AGV执行的作业子序列的结束位置。第1个AGV执行子序列的开始位置默认为0，结束位置为指针P2的值。若系统中只有1个AGV设备，则编码中的分配段省略。

采用两段编码方式后，每个个体的元素由n+m-1位整数构成。若将n个作业依次用0，1，…，n-1表示，则个体中每个元素的取值范围均为：[0，n-1]，且段内元素互不重复。采用相同的取值空间便于后续演化操作的实现。两段编码方式可以看作是传统单序列编码的扩展，既有效解决了AGV作业调度问题中的优化信息表示问题，又简洁易于实现。

3.2.2 种群初始化

采用两段编码方式后，个体由具有不同意义的两部分构成，因此，初始化操作也要针对每个部分单独进行。按均匀分布随机初始化个体是最常用的种群初始化方式。因此，对于个体作业段部分的初始化仍采用传统的随机初始化方式，同时要保证作业序列中不存在重复作业。

由2.3节的优化模型可知，若要取得较好的优化调度结果，所有AGV应该相对均衡地承担所有作业，防止出现AGV空载或负荷过重的情况。为此，分配段部分的初始化要采用区间均衡随机初始化方法。假如系统中有m台AGV，则需要构建由m-1个元素组成的分配段（首元素默认为0）。首先将n个作业构成的分配空间均分为m段，则分割点集为：。然后，分配段中每个元素的值就可依次以分割点为均值，并按高斯分布 N(π，σ)生成，其中。采用区间均衡随机初始化方式既保证了分割点是一个递增序列，又实现了初始分配的均衡性。

3.2.3 变异交叉操作

变异交叉操作是DE算法的核心操作算子，是保证算法搜索性能的重要手段。由于AGV作业调度问题是一种组合优化问题，在搜索过程中保持优良的搜索模式是非常必要的。由于DE/rand/1/exp变异模式已在众多文献中得到应用，显示了优良的搜索性能和收敛速度。因此，本文对于个体作业段部分也采用DE/rand/1/exp变异模式。具体实现方式见式（9）、（10）。

为了保持分配段的相对稳定，分配段采用遗传算法中常用的算术交叉方式。如式（12）所示。

其中，α为交叉因子，r1，r2，r3为随机选择的3个父个体的位置。

算法在变异交叉操作时会产生一些无效个体向量，如存在重复元素等。当出现无效个体向量时，直接将之丢弃，并根据前述方法重新生成新的个体向量，直至个体合法。

3.2.4 适应值评估及选择

演化出新个体之后需要对其适应值进行评估。首先将个体中分配段的值按从小到大进行排序，然后依据分配段的值将作业段中的作业序列划分为m个子序列，每个子序列的大小为 si(i=1，2，…，m)。将每个子序列依次分配给AGV进行执行，并按照公式（3）计算出每个子序列的执行时间Ti，然后按公式（4）求出所有子序列的最大执行时间 f即为该个体的适应值。同时，可按照式（5）～（7）求出个体的约束满足值E。

在AGV作业调度中，作业的时间约束并不是十分严格。为便于迭代及选择操作，定义如下择优标准：

其中Ii和Ij表示两个个体，f和E表示个体的适应值和约束值。按照式（13），当测试向量优于目标向量时替代目标向量，否则目标向量继续保留在种群中。

3.2.5 基于生存时间的种群多样性增强机制

DE算法采用精英保留策略，父代和子代直接进行竞争、优胜劣汰，种群的选择压力比较大，算法容易早熟收敛或陷入局部最优。为了提高种群的多样性和算法的搜索能力，本文引入了一种新的基于生存时间的种群多样性增强机制，该机制类似于人工蜂群算法（ABC）[16]中侦察蜂的机制，但并不限制每代淘汰个体的数量。在ABC算法中，侦察蜂可以增强算法搜索能力已得到广泛认可。

种群中每个个体都增加一个生存时间（life）属性，并在初始化时置为0。当个体经过一代演化后若适应值没有被更新，则life值增加1。若个体已被新个体取代，则life值重置为0。算法设置了一个新的最大生存时间（MaxLife）参数。每经过一代演化，系统检查每个个体的life值。当个体的life值大于MaxLife时，则表示个体经过了MaxLife代仍没有更新，个体已经丧失了搜索能力。若该个体不是种群中最优个体则将其从种群中删除，并按3.2.2节中方法重新初始化一个新的个体加入种群。该机制可以淘汰种群中的局部最优点，随机生成的新个体可以增强种群的多样性，提高算法的搜索能力，防止算法陷入局部最优。

4 仿真实验及分析

为验证改进算法的有效性，本文设计了一组模拟实验。实验以一个实际应用的场地布局为参照，共设置了22个站台。为了对算法进行全面的评估，实验设计不同的AGV数量和AGV负荷的情况。结合实际应用情况，将AGV数量 m分别设为1、2、4、8四种情况，将AGV的平均负载情况ld分别设为5、10、20三种情况。每次实验根据m和ld，随机生成m×ld个待执行作业，然后分别用先来先服务（FIFO）算法和改进的差分演化算法（IDE）及其简化版本（不含种群多样性增强机制）（SIDE）依次对生成的作业进行调度。为了更清晰地考察算法的寻优能力，各组实验没有考虑作业的时间约束问题。

差分演化算法的参数设置如下：

种群大小（NP）为 50，最大评估次数（MaxFEs）为100000，缩放因子（F）为0.5，交叉因子（Cr）为0.8，最大生存时间（MaxLife）为5。

优化调度结果如表1～表3所示。标记为FIFO、SIDE和IDE的行表示分别采用FIFO算法、SIDE算法和IDE算法调度后AGV执行完所有作业所用的时间（s）；S/F行表示SIDE算法相对于FIFO算法优化提高效率的比率；I/F行表示IDE算法相对与FIFO算法提高效率的百分比。

表1 负荷ld=5时的优化调度结果

表2 负荷ld=10时的优化调度结果

表3 负荷ld=20时的优化调度结果

从表3可以看出，在三种算法中FIFO算法的调度时间总是最差，SIDE算法居中，而IDE算法总能取得最好的调度结果。这说明本文提出的算法改进策略是有效的。另一方面SIDE和IDE的性能差异并没有确定的规律可循，当ld=10时，IDE性能优化提高率是SIDE算法的5倍，当ld=5时这一比率约为2。此外，在负载较大时，IDE可以普遍提高效率20%左右，而SIDE算法在各种情况下的效率提高均不超过10%。这些差异是由基于生存时间的种群多样性增强机制造成，说明该机制确实可有效增强算法的搜索能力，提高算法的寻优效率。当模拟作业数量(m×ld)小于20时，模拟数据的波动较大，这主要是由于场地的AGV站点多于作业数量时，随机生成的作业无法对各站点进行均匀覆盖所致。

图2显示了当AGV数量为1，负载为20时的演化收敛曲线。可以看出，两种算法都有较快的收敛速度。虽然IDE算法在演化早期收敛速度较慢，但其搜索过程可以持续发现更优解，使搜索得到较好的最终解。SIDE算法的早期收敛速度比较快，但其发现新解的能力较差，容易陷入局部最优。

图2 演化过程收敛曲线（m=1，ld=20）

5 结束语

AGV作业调度问题是集成生产环境中的一类典型的调度优化问题，其对AS/RS系统的执行效率具有重要影响。由于问题本身的复杂性，相关的研究还比较少。经过对问题进行必要的简化，去除了问题的动态特性，并抽象出了AGV作业调度的静态优化模型。可以看出AGV作业调度问题实质是带约束的多重TSP问题，是一个NP完全问题。并且具有巨大的求解空间，当前还无法找到具有多项式时间的确定算法能对其求解。本文针对AGV作业调度的特点，提出了一种改进的差分演化算法，设计了新的两段编码方式，并对DE算法中的交叉、变异、评估及选择操作进行了改造，以适合问题的求解。同时，还提出了新的基于生存时间的种群多样性增强机制，用以提高算法的搜索能力，防止算法陷入局部最优。仿真实验表明IDE算法可以有效求解AGV作业调度问题，且具有较快的收敛速度。

[1]姜山，季业飞.GASA混合优化算法在自动化立体仓库堆垛机作业调度问题中的应用[J].制造业自动化，2010，32（10）：63-64.

[2]刘国栋，曲道奎，张雷多.AGV调度系统中的两阶段动态路径规划[J].机器人，2005，27（3）：210-214.

[3]李莉，张立明，詹跃东.求解AGV路径优化问题的遗传算法参数优化[J].昆明理工大学学报：理工版，2006，31（4）：26-31.

[4]夏谦，雷勇，叶小勇.遗传算法在AGV全局路径优化中的应用[J].四川大学学报：自然科学版，2008，45（5）：1129-1136.

[5]任小龙，温浩宇，李华.无向Petri网的多AGV最优路径方法研究[J].西安电子科技大学学报：自然科学版，2008，35（3）：517-521.

[6]甘剑锋，周晓光.基于排队论的自动化立体仓库AGV调度效率分析[J].计算机测量与控制，2004，12（7）：657-659.

[7]金芳，方凯，王京林.基于排队论的AGV调度研究[J].仪器仪表学报，2004（4）：844-846.

[8]雷定猷，张兰.AGV系统的调度优化模型[J].科学技术与工程，2008，8（1）：66-69.

[9]柳赛男，柯映林.自动化仓库系统AGV小车优化调度方法[J].组合机床与自动化加工技术，2008（6）：23-25.

[10]边培莹，李德信，包宝军，等.粒子群算法在生产物流调度中的应用研究[J].计算机工程与应用，2010，46（17）：220-223.

[11]Storn R，Price K.Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces，tech.rep.TR-95-012[R].Berkeley，CA，1995.

[12]Storn R，Price K.Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997，11：341-359.

[13]Das S，Suganthan P N.Differential evolution：a survey of the state-of-the-art[J].IEEE Trans on Evol Comput，2011，15（1）：4-31.

[14]Qin A K，Huang V L，Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Trans on Evol Comput，2009，13（2）：398-417.

[15]Wang H，Wu Z J，Rahnamayan S.Enhanced oppositionbased differential evolution for solving high-dimensional continuous optimization problems[J].Springer J Soft Comput，2011，15：2127-2140.

[16]Karaboga D.An idea based on honey bee swarm for numerical optimization，technical report-TR06[R].Computer Engineering Department，Engineering Faculty，Erciyes University，2005.