李彬璠，郭 丽，杨腾飞，石振鹏，汪锴狄

（1.北京机械工业自动化研究所，北京 100120；2.北自所（北京）科技发展股份有限公司，北京 100120）

0 引言

随着智能制造的加速推进，国内外智能仓储行业的发展日益迅速，大型物流仓储库区的出库效率问题逐渐成为研究热点。自动化立体仓库（Automated Storage/Retrieval System，AS/RS）是生产型企业加工与存储的交接枢纽，特别是在生产型厂内物流中，零件出库节拍要服从生产节拍。受限于仓库空间，输送线多采用交叉环线设计。多限制条件下的调度系统作为整个自动化立体库系统中最为核心的部分之一，对于出库效率的提升一直是研究的热点与难点。

由于智能调度系统支配整个立体库的运行，诸多学者对调度的智能化开展了深入探索研究。在国内，王厅长[1]针对双伸位的自动化立体库建立货架稳定与提升存取效率的模型，并通过Matlab对比普通遗传算法与病毒遗传算法的优劣。梁兴等人[2]针对货位分配问题进行升级创新，将Pareto最优解的方法引入调度环节中，与之前的GA算法进行结合，最终通过仿真验证了高效性。雷斌[3]通过运用遗传算法、布谷鸟搜索算法、禁忌搜索等机器学习的算法,在货位分配、作业调度等方面进行研究拓展。在国外，Lu ZHEN等人[4]使用设备互联、集成的方式，对自动化立体仓库进行升级改进，对调度分配地址问题进行了探索。Ahmed Mohammed[5]等人基于RFID的不确定性对自动仓储系统的设计并进行优化，不同于常见的是，他使用的是一种多准则模糊规划方法。Gianluca Nastasi[6]主要在基于遗传算法的多目标优化算法上，将作业的效率大幅提升。AS/RS调度的改进优化成为国内外诸多学者研究热点与难点，对智能仓储行业的发展提供了动力。

1 生产型物流出库效率问题简介

对于汽车制造企业来说，供件效率非常关键。该企业引入了自动化立体仓库，目的主要是为了节约空间、节省人力以及提升效率。立体库用来存放一些汽车零部件，通过发起出库订单来满足总装车间的要货需求，因此出库效率直接影响了总装车间的生产进度[7]。现阶段，对于效率要求高的自动化立体库存在如下问题：部分立体库前期布局规划不合理、入库时货物分类不清晰、WCS系统调度算法较为落后，仅考虑是否可以出库而并未考虑出库效率问题等。

针对上述问题，我们制定了一系列方案来提升出库效率，例如入出库口的南北规划、入库分配控制、紧急件非紧急件的物料定义分类设计等，最核心的部分是堆垛机的空闲停留策略和遗传算法的改进。这两部分决定了厂区自动化立体库的运行是否达到最高效率，减少不必要的资源浪费，从而满足生产车间对于零件出库的时效要求。

2 生产型物流出库效率优化设计

2.1 南北入出库口方案规划设计

在以往的项目中，自动化立体仓库的入库口、出库口设计在同侧或对侧，这样所有的货物出库都会经过同一路线，增加了出库等待时间。为更方便卸货及取货，提升立库总体入出库效率，在库区的南北侧均设计了入出库站台，对于出库来说，可以根据距离巷道的远近来选择南区或北区的去向，避免了高峰出库时段货物堵线；对于入库来说，提升了空间利用率，南北两侧均可以设计入库缓存区来减少货物积攒。南北规划的设计作为项目的初期规划环节，对于后期的调度策略以及环线控制有着关键作用，提高了整体的运行效率。

图1 整体规划布局图

2.2 入库分配控制及物料定义分类设计

由于本项目属于环线轨道，同时又对堆垛机的运行效率要求较高，为避免环线堵塞，影响出库效率，在入库时，调度系统会自动分配合理的巷道；同时，针对入库的物料，我们在定义时将其区分为紧急件和非紧急件，这样可以有效区分物料的种类，提高立库运行效率。我们在数据库中对当前每个巷道已有的库存量、所要入库的物料在该巷道的数量、空货位数量、该巷道所拥有的暂存量以及该物料的暂存量分别计数，通过数据库的筛查，来寻求最优入库分配方案，最大限度避免堆垛机资源浪费与过剩。

2.3 堆垛机及环式输送线调度方案设计

2.3.1 堆垛机停留策略分析与优化

为了提升堆垛机的运行效率，我们可以缩短堆垛机在启动时的时间消耗，对最后一条作业结束时堆垛机所停留的位置进行分析，共找出以下五种服务停留点的策略可供选择，通过计算堆垛机启动时所消耗的平均期望时间来寻求一种最优策略。

策略1：当堆垛机完成所有下发作业后，停在入库站台；

策略2：当堆垛机完成所有下发作业后，停在出库站台；

策略3：当下发的最后一条作业是入库作业时，堆垛机停留在完成入库作业的位置；当下发的出库作业是最后一条作业时，堆垛机停在出库站台；

策略4：当下发的最后一条作业是入库作业时，堆垛机停在入库站台；当下发的出库作业是最后一条作业时，堆垛机停在出库站台；

策略5：当最后一条作业是入库作业时，则堆垛机停留在货区中固定站台D1，出库作业是最后一条作业时，则堆垛机停在货区中的固定站台D2。

当堆垛机的第一条作业是入库作业时，显然堆垛机的最优停留点是第0列入库站台；当堆垛机的第一条作业是出库作业时，此时我们考虑最佳的停放位置自然是货架中的某个位置。通常，在下发作业之前，无法得知起始作业的类型。对于本项目而言，我们如果设定堆垛机按照作业下发的时间顺序来执行任务，从概率角度来看，入库作业与出库作业的可能性相同；但是从优化角度出发，堆垛机调度系统将更多的去执行多任务复合作业，那这样起始作业是入库作业的概率就会相对较大。因此，从长远来看是合理的。如图2所示，代表典型的任务系列执行顺序与过程，在此条件下有如下的结论：

图2 堆垛机的任务队列的执行图

我们优先分析前4种停留策略，假设他们启动时的平均期望时间为ES(i),(i=1,2,3,4)，则有以下结论：

其中，pr代表一个起始作业为入库作业的概率；pc代表一个起始作业为出库作业的概率；ETI/O代表堆垛机在货区的某个位置与巷道的入出库站台之间的平均期望执行时间；ETB代表堆垛机在货区的两个位置之间执行作业的平均期望时间；T0代表堆垛机在巷道的入出库站台之间伸收叉的交替时间。

类似的，我们可以得到ES(4)≤ES(3),利用做差比较法得出：

为使得上式最小，我们需要找到D1*和D2*,根据最优化得方向看，D1*=D2*，因此，在的情况下，

所以，在上述的分析与推导过程中我们可以得出，要使堆垛机减少空跑消耗的时间，可以进行调整堆垛机完成作业后的停留策略，如果从长远考虑，通过方案比较，我们得出提高效率最优的是第一种策略。

2.3.2 堆垛机入出库作业调度算法优化

1）模型的建立

针对于复合型作业调度，结合自动化立库的结构特点[8]，建立如下数学模型：

如果上位机共下发N条作业，其中入库作业与出库作业数目分别是n和m，即N=n+m。当收到每一条作业任务时，调度系统都会为其分配作业起始地址并且交叉完成入出库作业。显然，对于堆垛机来说，完成整套入库与出库作业耗费的总时间ti为：

tOA是执行入库作业所需时间，tOA=max{丨XA-0丨/vx,丨YA-0丨/vy}；tAB是堆垛机进行库内位置转换所需时间tAB=max{丨XA-XB丨/vx,丨YA-YB丨/vy}；tBO是出库作业所需时间tBO=max{丨XB-0丨/vx,丨YA-0丨/vy}。

当入库作业小于出库作业的数量时，我们可以认为堆垛机的作业有多次的复合作业循环过程，即单次循环的重叠，通常每个循环是由2～3次的单循环构成，对于出入库站台来说，属于所有循环的枢纽位置。我们通过分析可以得知，执行完所用时间Tk是我们控制堆垛机最优化的目标函数：

其中，k=max{m,n}代表循环总数。ti是在第i次堆垛机执行作业是所需要的运行时间，这其中包含了入库作业、出库作业以及空载运行的时间。

针对以上的模型假设，我们可以将问题转化为旅行商的类似问题。其本质是寻找最短路径问题，放在本实验中，我们可以认为堆垛机的调度路径即堆垛机的行驶路线是要求的结果，作业调度最优解就是堆垛机的最优路径，进而来提高运行效率。

3 引入遗传算法

对于堆垛机复合作业问题，我们转化成了旅行商求解问题，由于随着数据量增大，作业任务增多，常规方法较难寻求最优解，对与遗传算法本身来说，解决NP组合优化问题，有很大的优势。我们设置入出库作业共有N个，其中p个入库任务，q个出库任务。具体步骤如下：

1）进行编码：

根据入出库作业队列，我们将每条作业所在货位进行编码，显然，测试数据应在同一巷道。例如，我们假设共有6个入出库作业，作业地址分别为3-1-2，4-4-1，2-6-1，3-5-2，6-3-1，4-2-2，分别以1，2，3，4，5，6代表这6个货位点，即这六个货位点可以产生种组合路径，染色体（6，3，2，1，4，5）代表堆垛机先运行到6号货位，再运行至3号货位，最终到5号货位完成最终作业。

2）适应度函数的建立

适应度函数可以确定为，堆垛机从站台起始位开始按照染色体的顺序进行调度作业，所需要的总时间：

其中，I=(i1,i2,...,ip+q)表示任意一条循环回路。

3）产生初始种群

我们随机产生两个p*q的矩阵A与B,作为本次实验的初始种群，矩阵q列代表染色体长度为q，即q-1个货位地址；矩阵的p行代表种群规模为2p.矩阵每一行代表着堆垛机调度作业的执行顺序。

4）选择

选择操作顾名思义，即在种群进行交叉或变异操作之后，进行“优胜劣汰”，生成的染色体按适应度结果排序，最优个体将取代适应度最低的染色体，适应度高的染色体会保留下来，连续的迭代会一直进行筛选最优个体，提升了算法的收敛性，迭代操作终止时，会产生适应度效果最好的染色体，该染色体即调度方案的最优解。

5）交叉策略

在本实验中，若采用传统的交叉方式，将会产生无效错误的调度地址与路径，为了避免这种情况，我们采用非常规的交叉方法，即单点交叉。即在染色体中随机的进行基因交配，选择某处位置，对于他的下一代染色体而言，该位置之后的基因段由另一条染色体的不重复的基因构成，而该位置之前的基因段维持不变。例如：

选择的交配基因在第三个位置，对于子代A来说，4 2 1保持不变，剩下的四位与父代B进行交叉，将重合的基因进行替换，子代B进行同样的操作。

6）变异策略

传统意义上的变异操作是将染色体中的某个基因进行无规则变换，但在本实验条件下，如果进行随机变异，染色体所对应的基因编码会变化成无效的货位编号，导致该染色体为无效解。所以在本实验中，计划采用基因互换位置的变异方式，这样可确保解的有效性。

7）参数选择

参数主要有两个，一个是交叉操作，一个是变异操作，在交叉时我们说过，交叉操作在迭代次数够多的情况下，最终收敛的效果会相对较好，因为会逐步生成适应度更优的染色体。可以设置为Pj=0.8；对于变异操作来说，考虑到为避免会破坏染色体，变异概率不宜取值过大，设置为Pb=0.05。

8）终止条件

遗传算法的终止条件通常设置为在最大迭代次数内，如果染色体适应度基本保持平稳，将会终止算法。迭代次数过大过小均会造成较大误差，因此本实验将maxgen赋值为500.

4 实例应用

在建模与算法设计完成之后，我们在该汽车工厂自动化立体仓库中进行验证算法的可靠性与时效性。图3为自动化立库局部的监控俯视图，图4为现场设备运行的实物照。

图3 立体库局部俯视示意图

图4 堆垛机与输送线实物图

我们从WMS系统上随机下发了一批作业任务，在某巷道的作业队列中接收了7条作业。接下来本文对于该部分的验证实施方案做一个简要说明。任务序号1-7，由于本项目存在单伸堆垛机与双伸堆垛机，为避免偶然因素，我们取样单伸位堆垛机，减少因近远排产生的误差，计算时实际有效数据只有层与列。货位地址(Xm,Ym)（m=1,2,…,7）分别为4-6，14-3，40-5，47-2，49-3，51-1，59-6。当m=2，3，6时，堆垛机作业状态为出库；当m=1，4，5，7时，堆垛机作业状态为入库。

7个货位地址的堆垛机运行时间如上表1所示，倘若不进行算法优化，按照原本的调度逻辑应按顺序进行作业，即（1，2，4，3，5，6，7）。运算可得所消耗时间为268s.根据我们前文所设计的算法，进行迭代后，筛选出最优染色体，得到最优调度路径为（1，2，5，4，6，7，3），根据上表计算消耗时间为240s.显而易见，本实验所提出的调度方案效果显著，对于厂区来说是高效的，节约了堆垛机的运行时间，保障了立体库出库的效率，其算法优化效果通过Matlab呈现，如图5所示。

表1 7个货位地址的堆垛机运行总时间表

图5 算法优化效果图

图中种群均值我们可以看作平均适应度，所谓解的变化是指最优适应度，从图中可以看出，在迭代初期，种群均值、最优解变化起伏不定，适应度函数最优值与原调度逻辑所得时间差距不大，随迭代次数增加，种群均值趋向于收敛，适应度函数最优解达到收敛值240s，与之前的调度逻辑相比，效率提升明显。

5 结语

基于遗传算法的堆垛机调度策略可以从算法角度最大限度的提高堆垛机的运行效率，缩短出库所用时间，提高资源利用率。对于生产型物流而言，解决出库时效性问题，我们要从全局出发，从立库的设计规划起步，同时，环线的输送系统要求我们在入库时对物料定义、分配巷道等环节要加以调整来避免堵线，另外，我们建立了模型，设计了堆垛机空闲时的停留策略。本文通过对这几个要点问题优化分析，最终建立了一套相对效率较高的调度分配方案，并将其应用在该项目中，通过实验数据得出的算法运行结果符合预期设计，证明了研究成果的可行性。