穿梭车自动存取系统任务调度算法适配性研究

刘 刚 ，王艳艳，黄 珂 ，满荣军，吴耀华

(1.山东大学 深圳研究院，广东 深圳 518000；2.山东大学 机械工程学院，山东 济南 250061；3.山东大学 控制科学与工程学院，山东 济南 250061)

1 问题的描述

电商的快速发展为企业带来“海量”订单的同时，也带来了巨大的挑战，消费者的需求逐渐趋于多样化和个性化，如何在配送中心快速处理具有小批量、多批次、高时效特点的“海量”碎片化订单成为电商企业亟待解决的难题，也成为提高电商企业核心竞争力的关键。多层穿梭车自动存取系统(Shuttle-Based Storage and Retrieval System，SBS/RS)以其存储容量大、作业效率高、响应速度快等优点，成为电商企业打造智慧配送中心的理想选择[1]。

多层穿梭车自动存取系统由提升机、穿梭车、立体货架等设备及各种管理控制软件组成，如图1所示，多个设备并行作业，以缩短订单拣选作业时间，提高系统作业效率。在设备资源有限的条件下，优化出库任务调度效率，可缩短设备的空闲等待时间，减少资源浪费，提升订单履行效率，为企业带来十分可观的经济效益。但是穿梭车的并行作业为自动化设备的合理调度带来了挑战。因此，确定合理的穿梭车、提升机任务执行顺序是提高系统作业效率的关键。

目前国内外学者通过求解分析模型或验证仿真模型对此类问题进行了大量研究。YU等[2]提出并使用最短边出库优先权法对多层穿梭车自动存取系统的一组存储和出库任务进行排序，其处理时间比先到先服务策略的处理时间减少了20%～70%；WAUTERS等[3]分解了多层穿梭车自动存取系统的出库调度问题，构建了货位选择模型与货位排序模型，根据出库任务规模分别采用精确算法和启发式算法求解模型。罗键等[4-6]通过模拟退火算法、遗传算法等智能算法求解多层穿梭车自动存取系统中的货位分配和提升机任务调度等问题，实验结果证实了算法有效性；唐猛[7]根据自动小车立体仓库系统的作业特点建立了穿梭车和提升机联合任务调度模型，使用改进人工鱼群算法求解模型；WANG等[8]针对SBS/RS中提升机与穿梭车协同并行作业的特点建立了以最小化穿梭车和提升机等待时间、任务完成时间为目标的任务调度模型，采用NSGA-II多目标遗传算法求解模型；SUI等[9]考虑了提升机和穿梭车在作业时的加减速特性，以提升机的行走时间评估了提升机的运动模型，采用遗传算法改进的粒子群算法进行计算，证明改进算法的效果优于两种基本算法；于巧玉等[10]在任务调度模型中考虑了出库期限因素，提出一种蚁群算法与粒子群算法相结合的智能算法，求解任务调度问题；张晓清[11]研究了双载位多层穿梭车自动存取系统的任务调度问题，模型考虑分区倒货策略，利用改进的模拟退火算法证实了系统中的平均出库效率可提升10%，同时可减少不必要的倒货次数；杨玮等[12-13]将入库与出库任务组合成存取任务对，分别对双载式多层穿梭车系统、子母式穿梭车仓储系统的作业时间建模，建立以总作业时间最短为目标函数的模型，并分别使用遗传算法混合植物繁殖算法和改进粒子群算法求解，并通过30、50、100三种规模算例证明算法有效性；黄珂[14]建立了以出库时间为目标的出库任务调度模型，并通过改进蚁群算法求解，同时建立了能耗与能量再生模型研究了系统的参数配置问题；于皎[15]以出入库时间最短为目标，根据跨巷道和跨层作业条件建立了4种作业模式下的动态调度模型，并通过仿真证明了基于分类随机仓储策略的三维调度策略效率最高；汤洪涛等[16]建立了以最小化最大任务时间为目标的数学模型，使用人工蜂群算法求解跨层跨巷道穿梭车系统的作业优化问题；鲁建厦等[17]将出入库混合作业看成三阶段的流水作业调度问题，改进人工鱼群算法求解模型，并通过实验证明了改进算法对出入库复合作业具有有效性；何昕杰等[18]采用遗传算法求解了以订单出库顺序为变量、系统出库时间为目标函数的四向车系统订单排序优化模型。以上研究构建的模型和求解方法均能有效提高系统作业效率，但是没有针对问题规模提出合适的求解方案，没有对精确求解进行必要的探索。

由此可以看出，大多数研究以任务完成时间最小为优化目标构建任务调度模型，求解方法侧重于启发式算法的改进，缺少对问题进行精确建模和精确求解的探索。SBS/RS以拣选作业为主，货物出库时间是影响订单拣选效率的重要因素，因此本文的研究对象是基于单指令模式的出库任务调度问题。以出库任务完成时间最小为优化目标，在深度剖析和抽象穿梭车和提升机协同作业流程的基础上，建立基于混合整数规划(Mixed Integer Programming, MIP)的出库任务调度模型，使用改进蚁群算法求解模型，并分析问题规模和精确求解算法的适配方案，优化出库任务，提高出库效率。

2 多层穿梭车自动存取系统

2.1 布局介绍

在SBS/RS中，每条巷道两侧各有一排货架，货架每层设置多个存储货位。货架上的存储容器是周转箱，一个周转箱存放一个存储单元(Stock Keeping Unit，SKU)。穿梭车接收管理系统的指令，在货架导轨上往返运行。小车由电能驱动，通过激光导引[19]或电磁导引等先进技术实现精准定位，通过货叉的推拉动作实现料箱取放。SBS/RS使用的往复式提升机可在I/O站台和货架层间往返运送货箱，是系统执行出入库任务的核心设备。一般情况下，I/O站台设在巷道口，与输送系统直接相接。同时，I/O站台可与货架一层相接作为缓存位使用，故货架第一层的出入库任务无需提升机参与。SBS/RS的结构图如图2所示。

2.2 作业流程

SBS/RS有两种作业模式，即在同一时间段内只出库或入库的单指令模式，以及出入库并行的双指令作业模式。SBS/RS作为以拣选为主的系统，货物出库顺序和出库时间会影响订单拣选效率，因此，本文研究单指令模式下的系统出库任务调度问题，构建以出库任务完成时间最小为目标的任务调度模型并求解。多层穿梭车自动存取系统的单指令模式工作流程如图3所示。

执行出库任务时，提升机和穿梭车都遵循“先到先服务”原则[20]。接收到新的出库任务后，任务分配给空闲穿梭车，穿梭车行走至对应货位取货。另外，提升机并行移动至穿梭车所在层后交接货箱，穿梭车任务完成。然后，提升机携带货箱返回至I/O站台，待货箱离开提升机后，整个出库任务完成。执行出库任务时，设备并行作业易出现两种空闲状态，即穿梭车等待提升机响应的空闲状态与提升机等待穿梭车完成任务的空闲状态[21]。

2.3 设备服务时间分析

穿梭车和提升机在执行出入库任务时，必然有加速和减速过程，该过程可简化为加速度为a的匀加(减)速运动[22]，其运动规律如图4所示。

如图4所示，任务距离D较短时，只有匀加速和匀减速两个阶段，此时的最大速度记为vtop。当距离D足够长，设备加速至最大速度vmax做匀速运动后匀减速至静止；假设设备做匀加速和匀速运动的时间为t1和t2，

(1)

(2)

因此，穿梭车由货架第0列运动到第k列，提升机由货架第1层运动到第i层的作业时间分别可由式(3)和式(4)计算:

(3)

(4)

式(3)和式(4)中所需的参数及硬件设备参数值如表1所示。

表1 系统硬件设备配置参数表

上述服务时间的计算如下：

(5)

pij=τL(|i-j|)；

(6)

p″ij=τL(i)+τL(j)；

(7)

ti0=t0i=τs(i)；

(8)

tij=τs(|i-j|)；

(9)

t″ij=τs(i)+τs(j)。

(10)

3 SBS/RS任务调度建模

3.1 问题描述

任务调度研究的问题是利用有限资源完成指定的任务。若将SBS/RS看作车间生产系统，提升机和穿梭车看作生产设备，待出库的货物相当于待加工工件，则出库作业可分为提升机序列执行出入库任务和多个穿梭车并发执行取放货任务两个阶段。而不合理的出库顺序可能导致设备互相等待，从而延长订单履行时间，影响作业效率。

3.2 出库任务调度模型

3.2.1 模型假设

针对出库调度模型，假设如下：

(1)运行期间不考虑设备故障；

(2)系统运行期间，硬件配置参数保持不变；

(3)系统启动时，穿梭车在每层货架第0列，提升机在第1层；

(4)在系统调度过程中，提升机和穿梭车总是停在最后一个已完成任务所在的位置；

(5)货位采用随机分配策略且货位信息已知。

3.2.2 模型参数定义

(1)参数定义

N为货架层数；

C为货架列数；

M为出库任务数；

Q为待出库货位的集合；

Qi为货架i层的任务所在列的集合；

Zn为任务数大于n的货架层数；

Si为货架i层的任务数；

IM为所有任务编号集合，IM={1,2,3,…,M}；

IN为任务所在层集合；

IS为所有层中任务数最大的任务集合，IS={1,2,3,…,maxSi}，i∈IN；

tm为提升机开始执行任务m的时间；

rin为穿梭车完成货架i层的任务n的时间；

T为正整数，防止陷入子循环。

(2)决策变量

3.2.3 模型构建

(1)目标函数

设出库任务调度问题的优化目标为最小化系统总出库时间RT:

f=min(RT)。

(11)

出库任务开始时刻记为0时刻，总出库时间RT为提升机完成第M个出库任务的时间,

(12)

式中p′i表示提升机从第i层货架行走到I/O站台耗费的时间。

(2)约束条件

1)任务连续性和唯一性约束。

货架i层的穿梭车出库任务与提升机出库任务数应相等，确保提升机任务的连续性：

(13)

同时，任意提升机出库任务的目标出库层唯一。

(14)

穿梭车任务数大于n的层数应等于提升机任务数大于n的层数，即

(15)

提升机的第n个出库任务在所有提升机出库任务中唯一，如式(16):

(16)

式(17)和式(18)分别约束了同一层的任务执行顺序及存储位置的唯一性。

(17)

(18)

2)单一设备连续作业。

(19)

(20)

每层穿梭车的任务完成时间ri1需大于等于该车往返行走与取货耗费的时间和：

(21)

若提升机的任务m-1、m分别在i、j层，任务i、j的时间差应大于设备交接时间与提升机服务时间p″ij之和：

(22)

连续两个穿梭车任务的时间差应大于小车取放货与行走耗费的时间和：

(23)

3)多设备协同作业。

若提升机的任务m是第i层货架的任务n，tm应大于穿梭车完成任务n的时间和交接时间：

(24)

若提升机的任务m是i层货架的任务n-1，rin应大于tm与任务n的穿梭车运动时间之和：

(25)

若提升机的任务m是i层货架的任务n，提升机的任务m-1的目标层是j层，rin应大于tm-1与任务m-1的提升机运动时间之和：

(26)

4)决策变量取值。

为保证模型的非负性，决策变量和辅助变量的取值范围分别如式(27)和式(28)：

ymi,zmn,xink∈{0,1}；

(27)

∀i∈IN,∀m∈IM,∀n∈IS,∀k∈Qi,tm,rin≥0。

(28)

4 模型求解方法设计

4.1 融合禁忌搜索的改进蚁群算法TS-ACO

蚁群算法是DORIGO等[23]根据蚁群觅食行为提出的一种群智能算法。每只蚂蚁在觅食过程中会释放信息素，通常情况下，路径越短，信息素浓度越高。而蚂蚁更倾向于选择距离更短、浓度更高的路径，同时自身也会释放信息素，这将形成一个正反馈机制。在该机制下，大多数蚂蚁会选择浓度更高的路径作为最短路径，这条路径就是最优解。但是蚁群在初始时，由于没有充足的信息素提供启发式信息，蚂蚁走过的路径可能杂乱无章，同时行走过程中信息素信息不明显，从而造成搜索效率较低。通过改进算法，可以提高求解效率和精度，减少陷入局部最优的概率。

禁忌搜索(Tabu Search, TS)算法使用禁忌表保存最近搜索的局部极值，使得下次迭代时可以避开该值，有效跳出局部最优解的限制[24]。这种记忆能力扩大了搜索区域，可有效搜索全局最优解。使用禁忌搜索算法对每次蚁群算法的迭代结果进行二次优化，使用优化解优化信息素矩阵，可扩大解空间的搜索范围，提高解的质量。

一个出库任务货位可使用(货位号，货位层，货位列)表示。为便于计算，将所有货位按照实数编码，设某组任务的货位为{(100,1,30), (200,2,60), (300,3,20)}，则可以直接使用实数{100,200,300}代表出库货位和货位顺序，即一个可行解。设定蚁群算法中的蚂蚁数量为m，则蚁群算法搜索得到的序列为每一代蚁群的最优出库任务顺序。根据任务货位信息以及可行解中对应位置直接解码得到任务调度结果{xink,ymi,zmn}。基于以上编码规则，利用融合禁忌搜索的蚁群算法(Ant Colony Optimization based on Tabu Search, TS-ACO)来解决出库任务调度问题(如图5)，具体步骤为：

步骤1初始化参数。初始化蚁群数量、信息素挥发系数、信息启发式因子、期望启发式因子、禁忌表、禁忌长度、蚁群算法与禁忌搜索迭代次数等。

步骤2初始化参数信息素矩阵。本问题中的出库任务调度问题可以抽象为旅行商问题，即寻找最优路径(料箱出库顺序)。信息素τij定义为出库任务j在出库任务i之后的期望值，则蚁群的初始信息素矩阵元素为：

(29)

步骤3初始化蚂蚁种群，为排除随机性，搜索起点在搜索解空间中需均匀分布。根据信息素更新与状态转移机制蚁群算法遍历解集，得到第k代的最优路径，即最优出库任务顺序。

(1)信息素更新机制 信息素不断指引蚂蚁找到更优的解，其浓度会随着蒸发而减少，也会随着新的释放而增加，每完成一次迭代寻优，则需要更新残留信息素浓度。由全局信息素更新规则可知，只有全局最优解才能进行更新，更新规则由式(30)和式(31)表示。

τij(t+1)=(1-ρ)τij(t)+Δτij(t)；

(30)

(2)状态转移机制 状态转移是根据当前出库任务i选择下一出库任务j的概率。将第t次迭代寻优过程，蚂蚁自出库任务节点i出发到出库任务节点j的路径对应的信息素记为τij(t)，则选择该路径的概率

(32)

式中:α和β分别代表信息启发式因子与期望启发式因子，表示信息素与启发信息的重要程度；JK(i)是蚂蚁k下一步可以选择的任务节点的集合；τij为出库任务节点i至出库任务节点j路径残留信息素；ηij(t)为第t次迭代的启发式信息，表示蚂蚁从出库任务i到出库任务j的期望程度,

(33)

式中Tij为候选的任务节点预估的设备等待时间。

步骤4将第k代蚂蚁搜索后得到的出库任务序列I={i1,i2,…,ii,…，ij,…，im}作为禁忌搜索算法的初始解并记录当前最优解。

(1)采用2-opt策略计算初始出库任务序列I的邻域解，从中选择若干候选解。随机选取不同位置上的出库任务进行交换：

I={i1,i2,…,ii,…，ij,…，im}；

I′={i1,i2,…,ij,…，ii,…，im}。

(2)将候选解解码，得到任务执行位置{xink,ymi,zmn}，代入优化模型计算该候选解下的总出库时间。检查禁忌特赦规则，若最佳候选解优于当前最优解，保存最佳候选解的货位交换记录(禁忌对象)，则更新最优解；否则，更新当前最优解取值和禁忌表。

(3)满足迭代条件后输出禁忌搜索后的最优结果。

步骤5判断蚁群算法终止条件，若满足，则转步骤5，否则，根据式(30)和式(31)更新信息素，转步骤2。

步骤6根据解码规则解码得到最终出库任务调度顺序。

4.2 融合遗传算法的改进蚁群算法GA-ACO

传统蚁群算法中的信息素矩阵的初始值一般设为固定值，这样会造成蚁群算法寻优前期启发式信息的匮乏，使得收敛速度较慢。遗传算法是模拟自然界的遗传变异来寻找最优解，使用按概率随机选择的方法，该方法通常能避开局部最优问题。利用遗传算法生成一组较优解，根据优化解初始化蚁群的信息素矩阵，可提高蚁群算法搜索前期的寻优速度。

若是算法开始运行或某次迭代过程中的较优解为S，则信息素矩阵的初始化规则如下：

(34)

(35)

其中：τij为节点i到节点j之间的信息素初始化浓度；τ为信息素基础浓度；n为遗传算法得到的出库任务序列中经过i-j序列的优化解数；RT为根据优化模型计算得到的每一个优化解的总出库时间；Q为适应度调整系数；N为遗传算法得到的出库任务顺序总数。

融合遗传算法的改进蚁群算法(Ant Colony Optimization based on Genetic Algorithm, GA-ACO)如图6所示。

通过遗传算法为蚁群算法提供优化的初始解，可以加快蚁群搜索速度，得到更优质的求解结果。具体求解步骤如下：

步骤1初始化遗传算法迭代次数，种群规模，变异概率以及交叉概率等参数。

步骤2利用遗传算法为蚁群算法提供充足的启发式信息，优化蚁群算法的效率。

(1)初始化解空间。采用贪婪算法初始化种群所有个体，确保两个连续任务处于不同层可减少穿梭车等待时间。

(2)选择。计算个体适应度。通过“轮盘赌”选择子代用于产生下一代个体。

(3)部分映射交叉。在父染色体上随机选择两个任务点，以两点中间区域作为匹配区来构建映射表；交换父代匹配区并依据映射表处理重复编码得到子代个体，具体如图7所示。

(4)变异。为实现变异操作，随机交换个体的两个任务的位置。

(5)改进适应度函数。为区分个体差异，使用式(37)代替总出库时间的倒数作为适应度函数：

(36)

(37)

式中：RT(k)为个体k的总出库时间;Max和Min是所有个体总出库时间的最小值和最大值的倒数；ξ使较差个体也有几率被选中，是一个较小的正数。

(6)若满足算法终止条件，输出最优解；否则转步骤2。

步骤3将优化解带入式(34)和式(35)初始化信息素矩阵。对优化解中的节点路径适当增加信息素浓度，可有效降低寻优过程中陷入局部最优的概率。

步骤4蚁群算法迭代。根据式(30)和式(31)更新蚁群算法信息素矩阵，根据式(32)计算蚁群算法状态转移概率，计算优化值。

步骤5检查蚁群算法的终止条件，满足条件后输出结果，否则转步骤4。

步骤6根据解码规则解码得到最终出库任务调度顺序。

4.3 启发式算法与Gurobi融合求解

数学规划求解工具Gurobi可用于求解线性、二次型、混合整数二次型和混合整数线性等问题[25]。Gurobi能以极快的速度精确求解小规模实例，大规模实例的解空间复杂，求解效率较低。Gurobi求解MIP问题时可以为其设置初始解。因此使用启发式算法求出的模型较优解作为Gurobi的计算初始解，可提高Gurobi求解效率和解的精度。具体求解步骤如下：

步骤1设定合理的迭代次数，通过启发式算法迭代计算，得到出库任务调度的较优的取货顺序，缩小解空间搜索范围。

步骤2将取货顺序解码，得到模型决策变量组合{xink,ymi,zmn}，作为Gurobi计算程序的初始值。

步骤3根据MIP优化模型以及给定的较优的初始值迭代求解，使用Gurobi求解模型，经过若干次迭代后输出最优解结果。

步骤4根据模型决策变量xink,ymi,zmn确定出库任务执行顺序。

5 实验验证与分析

5.1 实验方案设计

根据本文提出的3种算法，设计3组不同规模的实验来验证算法有效性：

(1) 分析Gurobi在本模型下的性能。验证出库任务MIP模型的正确性，比较不同规模的求解效率，分析Gurobi性能瓶颈。

(2) 分析混合启发式算法在本模型下的性能。针对不同的任务规模，分别使用ACO、TS-ACO和GA-ACO求解模型，分析3种智能算法的求解精度和求解效率与任务数的关系。

(3) 分析Gurobi融合启发式算法的性能。通过实例分析Gurobi融合算法的有效性、算法瓶颈和结果精确程度。

5.2 使用Gurobi求解出库任务调度模型

假设货位信息已知，任务数量为10，随机生成10组数量为10的出库任务作为测试数据。小规模出库调度问题可以使用穷举法求解。将排列组合所有出库顺序求出的总出库时间最优的仿真实验结果与根据构建的模型使用Gurobi计算的结果进行比较，结果如表2所示。

对比仿真穷举求解结果(最优出库顺序)，Gurobi求解结果的误差为0，即本文建立的出库任务调度模型能正确输出最优取货顺序，且Gurobi可以用于求解该模型。为分析Gurobi求解瓶颈，测试多组不同的出库任务数量M时的求解情况，图8描述了不同任务数量下求解时间和出库时间的变化趋势。

表2 仿真与Gurobi求解结果对照表

由图8a可以看出，当任务量M<18时，Gurobi可在1 min内求解得精确解；当任务量M>18时，求解效率快速降低;M>50时，求解模型的时间超出1 h，效率极低，难以满足实际拣选需求。经过分析，当14

5.3 使用改进蚁群算法求解任务模型

随机生成20组待出库任务，设置任务数M=10,20,…,200，每组实验分别使用ACO、改进TS-ACO、改进GA-ACO算法求解模型，算法相关参数如表3所示。

表3 改进算法的参数设定

求解效率用平均求解时间(Average Time)评价，记为AveTime。求解精度用平均相对误差(Average Relative Gap)评价，记为ARG,

(38)

式中:Vlb为目标函数的最优下界，即根据提升机总服务时间计算得到的平均相对误差；Vopt为算法最优解。

设B-ARG表示最小的平均相对误差以评价算法的精度；A-ARG表示ARG平均值；ΔARG表示B-ARG和A-ARG的差值，用于评价算法的稳定性。根据表3设定的参数求解，3种求解算法对应的B-ARG、ΔARG、A-ARG、AveTime值与任务规模之间的关系如图9所示。

由图9a可知，当任务数M<50时，3种算法的B-ARG值差值较小，均小于1%，算法优化程度较高，求解误差小；随着任务数的增加，ACO算法的B-ARG值变化明显，在[3%, 7%]区间内波动，其平均相对误差明显超出TS-ACO和GA-ACO算法。TS-ACO算法与GA-ACO算法的B-ARG值在[1%, 4%]内波动，同时 TS-ACO算法的平均相对误差略优于GA-ACO算法。

由图9b可知，ACO、TS-ACO、GA-ACO算法的ΔARG 均在 5%以内，说明平均相对误差的平均值与最小值差距较小，算法求解稳定性良好。TS-ACO算法的结果波动较小，其次是GA-ACO算法， ACO算法波动较大，稳定性较差。

由图9c可知，当任务数M<50时，GA-ACO算法的A-ARG值最小；当任务数M>50时，TS-ACO明显更有优势。整体来看，TS-ACO算法的A-ARG值优化效果较好，GA-ACO次之，ACO最次。在求解大规模问题时，文献[26]在相似模型的调度问题中使用了多种智能算法求解，ACO算法表现优于其他算法。其中，ACO算法的平均相对误差小于16%。而本文改进的蚁群算法将平均误差限制在8%以内，由此可见，两种改进算法在求解精度上有较大提升。

由图9d可知，TS-ACO算法求解时间最长，ACO算法求解时间最短。随着任务量的增加，TS-ACO算法的求解时间快速增长，接近ACO算法的3倍。当任务数M=200时，TS-ACO算法的求解时间接近GA-ACO算法的两倍，需要600 s左右才能收敛。ACO算法的求解效率优于GA-ACO算法，GA-ACO算法优于TS-ACO算法。

为深入分析算法收敛速度，进行20组出库任务数为100的算例实验，并绘制最优求解结果的收敛曲线，如图10所示。

当迭代次数小于20时，3种启发式算法快速收敛，都能有效地跳出局部最优。ACO算法在第20次迭代时陷入局部最优，第60次迭代才跳出局部极值，其目标函数值较高，优化程度较低；TS-ACO算法的搜索效果较好，10次迭代的优化结果和ACO算法100次的迭代优化结果一致，可见禁忌搜索算法弥补了ACO算法易早熟的缺陷。GA-ACO算法初始目标值最小，收敛速度快，但后续迭代过程中多次陷入局部最优值，收敛速度较慢。

根据优化结果以及收敛过程分析，TS-ACO算法性能优于GA-ACO算法和ACO算法，其稳定性好，优化程度高，平均误差约为3.5%，在求解时间可接受的范围内可使用TS-ACO算法求解大规模出库问题。GA-ACO算法的误差约为5.5%，两种算法综合性能均优于ACO算法，可用于解决出库任务调度问题。

5.4 使用Gurobi融合算法求解任务调度模型

根据上述分析，两种改进蚁群算法的误差约为8%。为进一步提高求解精度，同时兼顾求解效率因素，将启发式算法计算的结果设置为Gurobi的模型初始解，使用Gurobi求解器对上文的27个算例再次求解，结果如图11所示。

由图11可知，任务数M=130时，融合求解算法的求解超过10 min；任务数M=160时，约20 min才能求得最优解，效率显著较低。为排除随机因素干扰，重新计算2组实例，结果如图12所示。

由图12可知，使用启发式算法为Gurobi提供初始解的求解方案提高了求解效率。经过Gurobi优化后，3组算例的求解效率趋势一致，没有明显的波动，可以排除随机因素影响，因此，算法对任务调度问题的优化具有普遍性。当任务数M<20时，融合算法效率高，求解精确；任务数2080时，解空间过大，最优解搜索缓慢，求解效率差。

因此，在求解中小规模出库任务调度问题时，采用启发式算法和Gurobi结合的混合求解方案，能在可接受时间内求得较优的总出库时间和出库任务顺序。同时，出库任务数量的求解瓶颈约在[70, 90]之间，超出后求解效率明显降低。

5.5 问题规模与算法适配性分析

从上文可以看出，任务规模越大，求解时间越长，相应的效率会呈现降低趋势，为分析任务规模与求解算法的适配性，对本文提出的3种求解方案的求解时间进行比较，如图13所示。

由图13a和图11可知，当任务数M<8时， Gurobi求解时间最低，解的质量高，效率高；当任务数880时，融合算法求解时间急剧增加，求解效率远低于3种智能算法。

根据任务规模与算法求解精度等因素之间的联系，提出算法与问题规模的适配方案：

(1)当任务数M=10时，选择Gurobi求解精度高，求解速度快；

(2)当10

(3)当20

(4)当任务数M>80时，从解的精度来看，推荐使用融合禁忌搜索的改进启发式算法(TS-ACO)求得较优解，也可根据需要灵活选择算法GA-ACO、ACO或其他启发式算法求解。

6 结束语

本文研究了多层穿梭车自动存取系统的出库任务调度问题，在深入研究系统运行状态和设备运动规律的基础上，计算了设备服务时间，建立了以出库任务完成时间最小的出库任务调度模型。为提高启发式算法的计算精度和效率，使用禁忌搜索、遗传算法改进蚁群算法的信息素矩阵，实验结果证明，蚁群算法的精度有较大提升。同时，本文提出一种Gurobi与启发式算法融合的算法，可用于中小规模问题的精确求解。通过数值实验，使用ACO算法与3种改进算法计算一系列不同规模的出库任务，比较算法精度、计算时间、稳定性等指标，综合各类算法的表现，提出了SBS/RS任务调度问题求解算法的适配性方案。

但是，本文只考虑了单作业指令的多层穿梭车自动存取系统，对于双指令作业周期的任务调度优化问题有待于进一步研究。