三载具AS/RS作业调度优化

王 婷，王洁慈

（陕西国际商贸学院，陕西 西安 712046）

0 引言

传统堆垛机只有一个货位，每次进出最多只能装载一个货物，这不仅极大的浪费了存取调度时间，而且加速了设备的损耗。随着社会需求的不断发展，这种一进一出的工作方式已不能满足企业仓储和配送的需求。为解决上述问题，提出一种新型的仓库，即多载具自动化立体仓库（multi-shuttle-automated Storage and Retrieval System）。三载具堆垛机作为多载具自动化立体仓库中常见的一种设备形式，一个子行程可以完成最多三个存货和三个取货任务，很好地解决了传统堆垛机一次只能装载一个货物的问题，提高了存储效率。单载具AS/RS 目前的研究成果已经不能满足新型AS/RS运作上的要求，故而研究合理调度策略以提高三载具AS/RS作业效率刻不容缓。

现有文献中，诸多研究仍为单载具AS/RS，卞和营，等详细分析了堆垛机出入库的作业方式，建立了数学模型，提出了一种基于改进遗传算法的路径优化方法；蔡安江，等以堆垛机执行任务所需总时间为评价标准，建立了一种基于混合命令序列的堆垛机调度模型；靳萌，等采用免疫遗传算法求解串列立体仓库的存取作业调度问题；李博文，等采用遗传算法优化的集束搜索对堆垛机运行路径进行优化，提高运行效率。Hachemi K，等以双倍命令周期时间最小对单载具AS/RS 的存取作业进行排序处理；Chung E，等将存取调度问题处理为广义的排序问题，并引入启发式方法进行求解，优化效果显著；文献[7-9]对单载具重力式移动货架存取调度作业进行研究，以旅行时间最小建立数学模型，并进行求解。上述文献均在单载具存取系统作业调度中取得了良好的优化效果，但对于三载具存取系统而言，要在单载具基础上考虑分组问题及子行程内部顺序问题。

关于多载具AS/RS 的研究，文献[10-11]和文献[12-13]分别以双载具和三载具AS/RS为研究对象，但主要对AS/RS的工作效率和绩效性能进行评价；Yang P，等研究双载具AS/RS进出库复合作业，并采用一种可变邻域搜索的方法进行求解。只考虑了单周期下的优化改进，并未对整个订单任务进行分析研究；Drazen Popovic，等在分类存储策略下，对三载具AS/RS的进出库调度问题进行求解，实例结果表明了遗传算法求解该问题的优越性；Tanaka S，等将给定货位的多载具AS/RS作业排序问题归纳为车辆路径（有载货量限制）问题并对其进行探究；文献[15-16]虽涉及多载具AS/RS存取货作业调度问题，但是忽略了作业分组配对，只是从作业排序角度进行了探究。

针对三载具AS/RS作业调度问题，根据其工作方式，本文在研究时不再局限于单周期下的优化而是针对整批订单，将问题转化为分组问题、模式问题以及顺序问题。且上述文献中，堆垛机均假设为匀速运动，而堆垛机在实际运行中，具有一定的加速度，本文以更加接近实际的角度考虑堆垛机行走过程中的加速度，建立数学模型，利用混合人工蜂群算法求解模型。并采用三种算法对实例进行优化比较。在此基础上，选用混合人工蜂群算法对单、双、三载具堆垛机的运行效率进行计算对比。

1 问题描述

三载具AS/RS 的作业调度是指堆垛机根据订单情况载入货物，以适合的进出库方式完成作业任务。由于三载具堆垛机一次可以同时载多个货物，在考虑整个订单存取顺序的同时，也要考虑堆垛机一个子行程内的存取顺序，完成合理配置，提高工作效率。

三载具AS/RS与单载具AS/RS相比，一个子行程可以完成最多三个货物的存货和取货作业。在三载具AS/RS 配置下，对于一个订单内的存取货复合作业，首先进行指令分组，分组后每个组就是一个子行程。为了提高堆垛机工作效率，每个子行程往往采取“满载”作业，即一个子行程可同时处理3个存货作业和3个取货作业，每个子行程相当于遍历6个位置的小型TSP问题。考虑到企业的实际操作情况，在入库时为了避免多次搬运造成的浪费，入库顺序一定，即采取先到先服务规则，而出库货位是由系统生成，出库顺序不定，由后续解确定最佳出库顺序。

本文研究三载具AS/RS的出入库联合作业，是指接收到出入库指令后，对出入库任务进行配对联合、划分任务组，使整个订单上的任务指令都以任务组的形式呈现，每组完成3个入库任务和3个出库任务，每组内的完成顺序需再进一步分析，直到完成所有任务组。在优化过程中，统一考虑订单任务分组、堆垛机行走模式以及行走顺序问题。

2 三载具AS/RS调度优化

传统单载具AS/RS的复合调度作业中，堆垛机一次行程载入一个货物同时载出一个货物，在行程中只考虑作业配对问题，而对于三载具AS/RS作业调度的优化还需考虑指令分组、堆垛机行走模式以及子行程内部顺序问题。

2.1 指令分组

指令分组是指三载具AS/RS 中对出入库任务进行划分任务组的过程，当出入库任务不相等时，以补充虚拟入库/出库点进行调整，使得拨次中的任务都以任务组的形式呈现，然后再对任务组内的行走顺序进行分析，计算行程时间。

对于三载具AS/RS而言，一个子行程要完成三个存货和三个取货任务，现以一个入库任务多于出库任务的订单为例，入库任务为（56，105，19，223，417，29，2，88，76，25，312，74），出库任务为（12，542，411，30，79，300，49，66，211，315），对于该订单任务，有多种分组方式，在不同分组下，有着不同的行程，将直接影响到整个行程时间。不同分组结果见表1。

表1 分组结果表

2.2 行走模式

对于已经分组后的子行程，每个子行程对应堆垛机的一次行走过程。堆垛机按照其行走模式完成各个子行程。堆垛机“满载”情况下，必须先存入一个货物后才有空载位存放要取的货物，根据载位的空、满状态可以得出存取货物的关系必须满足：存货先于取货，需有空载位可以存放要取的货物。

根据实际情况，三载具AS/RS中堆垛机子行程的可行行走模式有以下五种，如图1所示：S表示存货作业，R表示取货作业。L1：存→取→存→取→存→取，如图1（a）所示；L2：存→取→存→存→取→取，如图1（b）所示；L3：存→存→取→取→存→取，如图1（c）所示；L4：存→存→取→存→取→取，如图1（d）所示；L5：存→存→存→取→取→取，如图1（e）所示。

图1 三载具堆垛机行走模式图

2.3 行走顺序

2.4 数学模型

结合以上相关问题分析，提出模型假设：（1）给定拨次内，存取货指令已知，且对应货位信息已知；（2）入库顺序一定，不可调换；出库顺序可以调整；（3）堆垛机为匀加速运动；（4）货物装载时间忽略不计。

假设货架水平方向即列方向为，垂直方向即层方向为，可得堆垛机的实际运行时间，其公式为：

根据三载具AS/RS 的出入库作业方式建立数学模型，需要考虑分组、模式以及顺序问题。

对于每组的子行程而言，主要考虑行走模式和出库作业顺序问题，一个子行程内可以有多个可行解，不同模式下不同顺序造成三载具AS/RS 的子行程内的解具有多样化。设行走模式中出库任务为1，2，3，取值为{123} 并且1 ≠p2 ≠p3。则对于每个子行程，货物出入库的时间行程时间为

Z为决策变量，当Z=1时表示取货指令在第个子行程中被访问到，否则Z=0。式(6)表示每个指令对应的货位都会被访问；式(7)表示每个子行程执行三个取货任务。

3 混合人工蜂群算法

人工蜂群算法(Artificial Bee Colony，ABC)是由Karaboga于2005年提出的一种新颖的基于群智能的全局优化算法，蜜蜂根据各自的分工采蜜，并交流信息，从而找到问题的最优解。

蜜蜂执行搜索活动的过程可以概括为：

（1）采蜜蜂确定蜜源，对其进行开采并记录相关数据，寻找新密源并与观察蜂分享数据；（2）观察蜂在舞蹈区等待采蜜蜂分享的数据，并在临近处选择蜜源；（3）侦查蜂随机找一个有意义的新蜜源。

算法流程如图2所示。

图2 人工蜂群算法流程图

3.1 初始化阶段

初始化人工蜂群规模(2*SN)。蜜源代表了算法在搜索空间内的可行解，初始化搜索空间内的可行解依照式（8）随机产生。

3.2 蜂群搜索阶段

人工蜂群算法中采蜜蜂的搜索方程表达式为：

式中：V表示新蜜源；X为蜜源的第维位置，X为随机选择的不等于的蜜源的第维位置；ϕ控制X领域内蜜源的出现，为[-11]内的随机数。采蜜蜂对更新后的蜜源采用贪婪选择策略进行选取。观察蜂以概率值选择蜜源，表达式为：

式中：为解的适应度值；为种群中解得个数。

侦察蜂在其领域范围内搜索新蜜源，蜜源的搜索次数存在一个阀值lim it，当蜜源经过限定最大开采次数lim it 后，如果仍然没有改进，此时采蜜蜂转变侦察蜂，并按照式(8)进行随机搜索产生新蜜源，新蜜源将代替该蜜源。

ABC的寻优方式倾向于不断开发新的解，但开发效率低，为此，受到粒子群算法寻优方程的启发，提出混合人工蜂群算法（HABC），即将粒子群算法中的粒子不断向个体最优和全局最优粒子靠近的寻优策略代入ABC算法中，可以得出一个新的搜索方程：

式中：ψ为[0，1.5]之间的随机数；p为个体最优解；p为种群最优解。

个体最优解p是指个体经历位置变化后，计算得到的适应度值最优位置，种群最优解p是指种群中的所有蜜源的适应度最优位置。蜜源每更新一次，计算一次适应度值，并且通过比较新蜜源的适应度值和个体最优值、种群最优值的适应度值更新个体最优和种群最优位置。

3.3 编码方式、适应度函数

编码方式：采用十进制编码方式。

适应度函数：本文优化的目标是完成所有订单任务的出入库联合作业用时最小，其计算公式为：

4 实例仿真

4.1 算例数据与算法参数设置

本文以某汽车零部件公司仓库为实例分析对象，针对仓库中某一排货架进行实际数据统计。单排货架为12 层，60 列，共720 个货位。按照图3 的方式对货架货位进行编码。货格宽度和高度尺寸为1.2m×0.8m。堆垛机水平方向最大速度v=2m/s，加速度a=0.4m/s，堆垛机垂直方向最大速度v=0.4m/s，加速度a=0.08m/s。

图3 货架货位编号

在本文仿真实验中，分别对出入库任务对为30，60，90 的不同订单进行仿真分析。以30 个出入库任务的订单为例，其编码方式见表2。设置混合人工蜂群算法蜂群大小为200，其中采蜜蜂和观察蜂各为100，蜂群食源数量即解的个数为100，最大开采次数为20；遗传算法中取种群数n=100，变异概率Pm=0.05，交叉概率Pc=0.8。GA、ABC、HABC 算法的最大迭代次数均为6 000。

表2 出入库任务对应货位编码

4.2 算法性能与仿真结果分析

为了证明所设计混合人工蜂群算法（HABC）的有效性，采用GA、ABC和HABC算法进行求解分析。为验证所用算法的稳定性，将三种算法在30任务对、60任务对以及90 任务对等不同订单规模下分别运行100 次，利用统计学方法求得均值和平均偏差。表3给出了不同订单规模下的进出库作业时间的初始解，所用算法在不同订单规模下的进出库作业时间最优解、优化效率、计算精度和计算效率。图4给出了三种算法在不同订单规模情况下的收敛图。

表3 三种算法在不同规模问题下的实验结果对比

通过对表3 中三种算法的计算结果进行对比分析，得到以下结论：在不同作业规模下，HABC相较于ABC算法，虽然计算偏差较大，但是优化效率明显提高，平均调度时间最小；相较GA求解的运算精度及优化效果都有很大程度的提高。表明本文所采用的HABC算法在解决调度优化问题上具有很好的适用性与可行性。

分析图4中曲线可得，HABC求解得到的结果虽然收敛速度较慢，但是求解精度高，与GA对比，在迭代过程中，可以不断的跳出局部搜索，寻找最优解。

图4 不同算法收敛效果对比图

4.3 三载具AS/RS性能分析

本文研究对象为三载具AS/RS，为了说明其运作效率及其在工厂中更高的实用价值，利用HABC算法对单载具、双载具AS/RS在。处理同样订单规模时所需时间进行计算，对比分析三载具AS/RS 的性能状况。表4为三种订单规模下的单、双、三载具AS/RS的进出库时间对比分析表。图5为不同载具数AS/RS作业调度算法收敛图。

表4 不同载具数AS/RS运作效率对比表

图5 三种不同载具作业调度算法收敛图

通过对不同载具数AS/RS的运作效率进行对比，实例结果表明，三载具AS/RS较双载具AS/RS在同样订单规模下，其运作效率提升了14%左右；三载具AS/RS的运作时间远小于单载具，效率大大提升，在同样订单规模下，其运作效率提升了42%左右。

5 结语

本文从分组配对、行走模式以及行走顺序三个方面对三载具AS/RS的作业调度问题进行全面分析，建立了出入库联合作业的优化模型，并采用混合人工蜂群算法对模型进行求解，利用实例对算法性能进行分析，在30、60、90任务对的不同订单规模下，将三种算法性能进行比较分析，结果表明：混合人工蜂群算法的优化效果最佳，优化效率分别达到18.81%、18.27%和15.98%。通过与单、双载具AS/RS在处理同种规模订单下的处理时间进行对比，结果表明，三载具AS/RS性能远高于单、双载具AS/RS，具有更高的实用价值，可以有效缩短作业时间，提升运作效率，降低企业成本。