跨层跨巷道穿梭车仓储系统复合作业路径优化
2022-07-07汤洪涛程晓雅李修琳鲁建厦陈寿伍
汤洪涛，程晓雅，李修琳，鲁建厦，陈寿伍
(1.浙江工业大学 机械工程学院，浙江 杭州 310023；2.浙江工商大学 管理工程与电子商务学院，浙江 杭州 310018)
0 引言
跨层跨巷道穿梭车仓储系统(Tier-to-Tier and Aisle-to-Aisle Shuttle Based Storage and Retrieval System, TTAASBS/RS)是在多层穿梭车基础上发展起来的快速存取、检索系统，其主要依靠巷道口垂直方向上的提升机、垂直于巷道的转载车和巷道内穿梭车配合完成调度任务。作业方式包括单一入库作业、单一出库作业和复合作业。与传统的每层一台穿梭车仓储系统相比，穿梭车可以多层共用；与跨层穿梭车仓储系统相比，跨层跨巷道穿梭车又增加了水平方向自主运行，实现多排共用，增加了系统的灵活性。出入库复合作业因贴合实际作业模式，常被用于TTAASBS/RS，然而穿梭车跨层跨巷道的特点大大增加了调度的复杂性，有必要采用合理的调度策略来提高系统的吞吐性能，其中出入库复合作业路径对吞吐性能的影响举足轻重。
多层穿梭车仓储系统是近年来发展起来的新型自动化立体仓库，而且受到越来越多的关注。针对多层穿梭车仓储系统研究，牟善栋[1]首先对多层穿梭车建立多目标任务调度模型，提出将多层穿梭车数学模型类比到流水线作业模型；王璐瑶等[2]指出影响多层穿梭车性能的主要因素为拣选台前端输送线，提出基于Robot的输送系统，并运用开环排队网络验证其有效性；鲁建厦等[3]对跨层穿梭车复合作业任务调度时间最小化进行研究，利用改进人工鱼群算法求解最优作业路径；杨玮等[4]对子母式穿梭车立体仓库三维路径规划问题进行研究，利用混合粒子算法求解一台子母车作业路径;鲁建厦等[5]在子母穿梭车三维复合作业的基础上考虑碳排放因素和作业时间对任务调度的影响，设计混合智能水滴算法求解模型，优化子母车作业路径；马文凯等[6]对跨巷道多层穿梭车系统的性能进行研究，利用进化算法优化跨巷道多层穿梭车仓储系统的存储容量和拣选效率；LERHER[7]研究跨巷道穿梭车仓储系统，建立了单、双指令情况下穿梭车的行程时间模型，并对时间模型进行性能分析。以上跨层/跨巷道研究一般以单巷道/单层为研究对象，本文综合考虑跨层跨巷道作业特点，开展多层多巷道研究，使其更贴合实际作业方式。
仓储系统中的三维调度、货位优化、资源配置等问题均被证明属于NP难问题[8]，因为采用精确算法求解时效率低、耗时长，所以越来越多的智能优化算法被用于求解复杂问题。人工蜂群(Artificial Bee Colony, ABC)算法于2005年由KARABOGA提出[9]。该算法具有包含参数少、邻域搜索和全局搜索能力平衡、收敛速度快等优点，在组合优化问题上得到了较广泛的应用，如混流装配线作业排序问题[10]、分布式柔性作业车间调度问题[11]、模糊柔性作业车间调度问题[12]等；另外，将ABC算法应用于求解车辆路径问题(Vehicle Routing Problem, VRP)也有较多研究[13]，例如利用ABC算法求解考虑交通堵塞和重复路径策略的VRP[14]、考虑碳排放策略VRP中的交叉对接配送问题[15]及考虑车辆管理和多仓库路径优化的多仓库VRP等[16]。通过上述分析可知，虽然ABC算法在求解组合优化问题方面具有优势，但是在求解密集存储系统路径规划问题方面的应用较少，因此本文采用改进的ABC算法求解路径规划问题数学模型。
本文以TTAASBS/RS出入库复合作业为研究对象，从作业任务顺序、作业路径等角度对其路径优化进行研究。穿梭车既跨层又跨巷道的作业方式可以节约系统成本、提高系统作业效率，但是大大增加了调度的复杂性。本文在考虑穿梭车、转载车、提升机加减速度的情况下，以系统最小化最大任务完成时间为目标，考虑TTAASBS/RS实际作业过程建立复合作业数学模型，基于改进ABC算法求解不同出入库作业任务数量的订单行程时间，在贴合实际作业环境的情况下最小化出入库作业的最大完成时间，提高存取效率。另外，分别与基本ABC算法、遗传算法(Genetic Algorithm, GA)、改进的蚁群算法、改进的人工鱼群算法在优化效率、稳定性等方面进行综合对比，验证本文算法的有效性。
1 问题描述和数学模型
1.1问题描述
现有的TTAASBS/RS由垂直提升机、巷道转载车、穿梭车、轨道式存储货架、仓库管理系统(Warehouse Management System, WMS)和仓库控制系统(Warehouse Control System, WCS)等组成，其垂直于巷道方向，由转载车搭载穿梭车进行跨巷道作业，穿梭车在巷道内进行出入库作业，垂直方向则由提升机完成货物跨层运输。TTAASBS/RS平面如图1所示。
图2所示为TTAASBS/RS三维示意图。图中：x方向为垂直巷道方向，表示转载车的运动方向；y方向为巷道布置方向，表示穿梭车的运动方向；z方向为提升机方向，提升机在z方向做上下运动。(x，y，z)对应货架的排列层。
一次完整的出入库复合作业任务由取货指令、出库指令、入库指令3次指令完成，其中取货指令和出库指令配合完成出库作业。结合具体的出入库任务，该TTAASBS/RS示意图如图3所示，作业流程如图4所示，具体操作如下：
(1)取货指令 当有出库指令下达时，判断穿梭车当前位置是否与出库货位同层。
1)若同层，则：①穿梭车运行至巷道首处，调用转载车；②转载车搭载穿梭车至目标巷道口；③转载车释放穿梭车(若取货货位在同巷道则不需要调用转载车)，穿梭车运行至出库货位进行取货作业。
2)若不同层，则：①穿梭车运行至巷道首处，调用转载车；②转载车搭载穿梭车至提升机站台调用提升机；③提升机搭载穿梭车运行到出库货位所在层，调用转载车；④转载车搭载穿梭车至目标巷道口处；⑤转载车释放穿梭车，穿梭车运行至出库货位进行取货作业。
(2)出库指令 ①穿梭车完成取货任务后运行至巷道口调用转载车；②转载车搭载穿梭车前往提升机站台调用提升机，并等待提升机；③提升机搭载穿梭车前往原点，调用转载车并等待；④转载车搭载穿梭车至I/O点；⑤穿梭车在I/O口卸货并载货。
(3)入库指令 ①穿梭车在I/O口完成取货任务后运行至巷道口，调用转载车并等待；②转载车搭载穿梭车前往提升机站台调用提升机，并等待提升机；③提升机搭载穿梭车至入库货物所在层，调用转载车并等待；④转载车搭载穿梭车前往入库货位所在巷道口；⑤穿梭车运行至入库口，进行入库任务。
出入库复合作业的简单表示如图3a所示；当进行连续出库/入库作业时，考虑任务补齐，将I/O点和初始位置(在初始位置进行一个虚拟入库作业)重合进行连续出库作业，如图3所示；当连续入库任务的I/O点和初始位置(在初始位置做虚拟出库作业)重合时，相当于系统只执行单指令入库任务，如图3c所示。在图3b和图3c中，灰色部分为虚拟作业。
系统接收到任务分配后，如何使提升机、转载车、穿梭车高效完成出入库任务，是建立TTAASBS/RS任务调度的关键。因此，需要合理规划提升机和转载车、穿梭车的作业路径，而建立合理正确的复合作业调度模型是研究路径规划的关键。
如图4所示为系统出入库复合作业流程图，系统一次完整的出入库复合作业任务调度分为出库作业和入库作业两部分，两部分又可以拆分为取货指令、出库指令、入库指令3次指令变化，并将出库作业和入库作业拆分为3次节点变化过程，每一次节点变化都需要穿梭车和转载车或穿梭车和提升机配合完成：①穿梭车由当前位置运行至出库货位所在位置；②穿梭车由出库货位所在位置运行至出入库节点(I/O口)；③穿梭车由出入库节点(I/O口)运行至入库货位所在位置。
TTAASBS/RS出入库复合作业的3个指令，均可表示为穿梭车从起始位置经过转载车、提升机的配合运行至目标位置的过程(如图3)，按照穿梭车的初始位置和目标位置是否同层同巷道，将该过程分为4种情况，其中穿梭车与目标任务同层同巷道、不同层同巷道的调度过程相同。
(1)同层同巷道 ①系统接收任务指令，并调度穿梭车；②穿梭车直接从当前位置启动运行到目标位置。
(2)同层不同巷道 ①系统接收任务指令，并调度穿梭车；②穿梭车从当前位置运行至巷道首处，调用转载车；③转载车搭载穿梭车前往目标巷道，转载车释放穿梭车；④穿梭车运行到达目标位置。
(3)不同层同巷道/不同层不同巷道 ①系统下达指令给穿梭车，穿梭车从当前位置运行至巷道首处调用转载车；②转载车搭载穿梭车前往提升机站台，调用提升机；③释放穿梭车，提升机搭载穿梭车至作业任务目标层，调用转载车；④转载车搭载提升机至目标巷道，释放穿梭车；⑤穿梭车运动到目标位置。
1.2 数学模型
根据跨层跨巷道多层穿梭车仓储系统运行情况，提出如下假设：
(1)巷道两侧货物随机存放，采用随机存储原则，一次进出复合作业中的入库与出库货物位置已知。
(2)考虑垂直提升机、穿梭车、转载车加减速运动，为方便计算，假设加(减)速度相同，且设备空载和负载时的移动速度相同。
(3)穿梭车和转载车均为单负载，即穿梭车一次只能携带一个货物，提升机在一段时间只能搭载一辆穿梭车。
(4)系统中的穿梭车、转载车和提升机均采用“上次完成任务处停靠”的停靠策略，即穿梭车、转载车和提升机完成任务后会停留在原地，不会主动做空行程运动。
(5)当一个巷道有穿梭车进行出入库作业时即锁死该巷道，不再允许其他穿梭车进入。
(6)穿梭车或提升机执行任务时不允许中断，只有在该任务完成之后，才能开始下一个任务。
(7)作业过程中不考虑设备故障及后续的重调度问题。
为了更好地描述TTAASBS/RS的作业流程，定义数学模型中用到的主要参数，如表1所示。
表1 参数定义汇总表
已知1次出入库复合作业任务可以转化成3次节点的改变，因此将3次节点变化转化为3次任务操作，分别为取货任务、出库任务(在出入库节点先卸货又再次取货)、入库任务。货物出入库作业单元编号为n=(1,2,3,…,N)，因此第n个作业单元又可拆分为第3n-2个任务、第3n-1个任务和第3n个任务。记b为作业任务序号，b=1,2,3,…,3N-2,3N-1，3N。设s为操作阶段的代号，s=1,2,3,4,5，一个复合作业可以转化为5个阶段：①穿梭车从当前位置至巷道首处；②转载车搭载穿梭车至提升机处；③提升机搭载穿梭车运行至目标层处；④转载车搭载穿梭车至目标巷道；⑤转载车释放穿梭车，运行至目标位置处进行存取货作业。因此，本文研究的问题可以转化为五阶段混合流水线调度问题。其中：m1=m5=Q，且穿梭车作用在第1阶段和第5阶段。m2=m4=3，当进行跨层/跨巷道不跨层运动时，调用两个实际转载车，第3个设备为虚拟运行的转载车；当进行不跨层不跨巷道运动时，调用虚拟转载车。例如s=2,k=1表示任务的第2阶段采用实际运行的转载车。m3=3，当发生跨层运动时调用的设备m1和m2为实际提升机，m3为虚拟提升机，选择m3表示只进行同层作业。wbb′sk为s阶段机器k操作的两个连续任务b和b′之间的准备时间，即转载车和提升机的空载时间都只发生在m1和m2实际设备中。
因此，TTAASBS/RS复合作业调度模型表示如下：
minCmax。
(1)
s.t.
(2)
tbsk≥0，b=1,2,3,…,3N,s=1,2，3,4,5;
(3)
tbs≥t(b-1)s，b=3n-1,3n,
n=1,2,…,N，s=1,2,3,4,5；
(4)
tbs+pbs≤tb(s+1)，
b=1,2,3,…,3N,s=1,2，3,4,5；
(5)
xb1k=xb5k，b=1,2,…,3N,k=1,2,…,Q；
(6)
xb3k=1，xb2k=1，
b=1,2,…,3N,k=1,2，3；
(7)
xb3k=1，xb2k≠xb4k，
b=1,2,…,3N，k=1，2;
(8)
xb1k=x(b-1)1kb，b=3n-1,3n,
n=1,2,…,N，k=1,2,…,Q;
(9)
xb33=1，xb2k=x(b-1)2k，b=3n-1,3n,
n=1,2,…,N，k=1,2，3;
(10)
xb3k=1,xb2k≠x(b-1)2k，b=3n-1,3n,
n=1,2,…,N，k=1，2;
(11)
tb′3-wbb′3k-(tb3+pb3)≥G(ybb′3k-1)，
b,b′=1,2,…,3N,k=1,2;
(12)
tb′1-(tb5+pb5)≥G(ybb′5k-1)，
b,b′=1,2,…,3N，k=1,2,…,Q；
(13)
tb′2-wbb′4k-(tb4+pb4)≥G(jbb′k-1)，
b,b′=1,2,…,3N,k=1，2；
(14)
tb′s-wbb′sk-(tbs+pbs)≥G(ybb′sk-1)，
b,b′=1,2,…,3N,k=1，2,s=2，4；
(15)
s=1,2,3，4,5,k=1,2,…,ms；
(16)
s=1,2,3，4,5,k=1,2,…,ms;
(17)
Cmax≥tb5+pb5,b=3n,n=1,2,…,N；
(18)
(19)
(20)
(21)
其中：式(1)为复合作业模型的目标，即最小化最大任务完成时间；式(2)在任何阶段都只有一台设备执行任务；式(3)保证任务开始时间的有效性；式(4)确保前一任务与后一任务之间的执行顺序，穿梭车不会从初始位置直接进行到入库作业；式(5)表示当前任务的完成时间早于下一任务的开始时间；式(6)表示一个任务的第1阶段和第5阶段由同一设备完成；式(7)表示k=1,2时对象为实际转载车，同一任务的第2和第4阶段为一实一虚转载车进行不跨层跨巷道运动，k=3时对象为虚拟转载车，同一任务的第2和第4阶段为同一设备进行不跨层不跨巷道运动；式(8)表示同一任务的第2和第4阶段由不同设备完成，此时为跨层作业；式(9)表示一次完整的出入库复合作业的先后任务的阶段1由同一穿梭车完成；式(10)表示同一作业单元的前后任务的阶段的设备由k决定，对象为转载车，当k=3时不跨层运动由同一设备完成，对象为虚拟转载车，当k=1/2时为跨层运动，对象为实际转载车；式(11)表示跨层时同一作业单元的前后任务的第2阶段由不同设备完成，对象为实际转载车；式(12)表示提升机前一任务结束时间早于后一任务开始时间，规定了任务的前后作业关系；式(13)表示穿梭车前一任务结束时间早于后一任务开始时间，规定了任务的前后作业关系；式(14)表示执行同一任务过程中，第2阶段的转载车作业时间早于第4阶段的转载车作业时间；式(15)表示前后任务作业关系中，前一任务第2阶段的转载车作业时间早于后一任务的第2阶段转载车作业时间；式(16)和式(17)表示作业设备连接作业任务，每一作业设备都有紧前工序和后接任务；式(18)表示Cmax的作业时间超过每一次出入库复合作业时间；式(19)～式(21)为变量申明定义。
2 算法描述
2.1 基本人工蜂群算法
ABC算法[17]是一种较新的优化算法，其基本思想与自然界中蜜蜂的觅食行为类似。在ABC算法中总共有雇佣蜂、观察蜂和侦查蜂3类蜜蜂，算法的搜索过程也分为3个阶段，①雇佣蜂阶段，主要负责寻找新的蜜源并记住蜜源信息，及时与观察蜂分享蜜源信息，包括运动区域的位置和蜜源的花蜜量；②观察蜂阶段，决定根据雇佣蜂提供的信息选择更好的食物来源，然后继续在所选择的食物源周围寻找其他食物源，与花蜜较少的蜜源相比，花蜜越多的蜜源被观察蜂选择的可能性越高[18]；③侦查蜂阶段，在蜜源附近随机寻找下一个有价值的蜜源[19]。
ABC算法的具体操作如下：
i∈[1,SN]。
(22)
(2)雇佣蜂阶段 雇佣蜂在其食物源附近确定新的蜜源，并识别和评估蜜源的质量。如果新蜜源的质量优于前一个蜜源，则从记忆中删除前一个源信息，将新源的信息存储在记忆中；否则，保留之前蜜源的信息。该阶段被雇佣的蜜蜂用式(23)确定新蜜源，Xkj为第k个个体在第j维上选择的位置，Vij只有在优于Xij的情况下才会采用该位置。Vij为第i个个体在第j维上的当前位置，
Vij=Xij+φij(Xij-Xkj)。
(23)
式中：φij为在[-1,1]之间选择的随机数；k为一个取[1,SN]之间随机值的整数。通过改变Xij的一个参数即可找到Vij源。
(3)概率计算 所有雇佣蜂完成搜索后，会与在运动区域等待的观察蜂分享信息。观察蜂评估雇佣蜂传递的蜜源信息，并根据概率值选择新的蜜源。同样，如果新源的适应度更优，则将之前的位置信息从记忆中删除，将新源信息保存在记忆中。观察蜂对新源的选择与pi概率值有关，
(24)
式中fitnessi为被雇佣的蜜蜂对第i个解的适应度值的评价。
(25)
式中：fi为优化问题所特有的目标函数值；abs为绝对值函数，文中fi≤0的情况不出现。
(4)观察蜂阶段 一旦在(3)中选择了一个蜜源，观察蜂更新方程将会采用与式(23)相同的更新方式进一步挖掘新蜜源[21]，然后ABC算法将用贪婪选择方案在观察蜂及其子代之间选择一个更好的。
(5)侦查蜂阶段 引入预定的参数limit来决定是否放弃某一蜜源[22]。如果该蜜源不能被开发，则被抛弃，并将对应该蜜源的雇佣蜂转化为侦查蜂去开采下一蜜源。
2.2 改进的人工蜂群算法
ABC算法在后期容易陷入局部最优且收敛速度较慢[23]，因此进行如下改进：①在初始种群阶段改进了随机生成个体和加入策略生成个体的生成方式，使初始种群多样化；②在雇佣蜂阶段引入重复优先交叉操作(Repeat Precedence Operation Crossover, RPOX)交叉算子和变异算子，提高雇佣蜂阶段搜索可行解的效率；③在观察蜂阶段引入动态邻域搜索；④设计了侦查蜂阶段的食物源更新机制。图5所示为改进后的ABC算法流程图。
2.2.1 初始种群生成
ABC算法的初始种群为随机生成，其优劣差异较大，种群质量难以保证，而初始种群的质量又会对种群的收敛速度和最终结果产生影响。因此本文提出随机生成和策略选择相结合的方式生成初始种群，即初始种群中35%的个体采用原始的随机生成方式，15%的个体采用规则选择，即每一次出库任务和入库任务优先选择距离较近的进行匹配，构成一次复合作业任务；剩余的50%个体采用策略选择方式，即穿梭车在选择出入库复合作业任务时，尽量选择距其最近的任务对先进行作业，以缩短穿梭车空跑时间。
2.2.2 雇佣蜂操作
(1)交叉操作
传统的ABC算法中，雇佣蜂主要在发现的食物源周围搜索可行解，并采用贪婪法则更新蜜源，产生的无效搜索较多，在一定程度上影响了算法的搜索效率。因此，改进雇佣蜂的重点应放在如何提高搜索效率，即提高雇佣蜂的有效搜索次数[24]上。本文设计了一种基于改进的RPOX交叉算子[25]来改进雇佣蜂操作阶段，如图6所示，其中以10对出入库复合作业任务对为例：
步骤1随机产生一组出入库任务数对0 步骤2随机选择两个父代个体p1和p2，从p1中选择k个出入库任务对组成集合N1，在p2中拣选剩余的n-k个出入库任务对组成集合N2。 步骤3分别将N1和N2对应的复合作业任务对从父代p1和p2复制子代，复制过程中保证对应的编码不变。 步骤4C1和C2剩余位置的出入库位置编码做以下规定：出库作业任务由后往前推，第2个位置补到第1个位置；入库作业任务补位规则由前往后推，p1的第1个位置补到C1的第2个位置；穿梭车补位规则与出库作业任务相同。 (2)变异操作 改进的变异操作应用到ABC算法可以使雇佣蜂搜索食物源的范围更广，本文设计一种适用于3层编码的变异操作能够增强ABC算法的搜索能力，减少非法解，如图7所示。 步骤1本文出库作业与入库作业一同构成一次复合作业任务，因此变异针对的主要是穿梭车编号，随机选择穿梭车编号中的任意两点位置，并从穿梭车集合中挑选可供替换的穿梭车序号。 步骤2将原穿梭车编号替换成新的穿梭车编号。若被替换的穿梭车处于被占用阶段，则视为非法解，替换为其他合法穿梭车。 2.2.3 观察蜂操作 在算法迭代过程中，ABC算法搜索最优蜜源的本质是蜜蜂执行邻域搜索的过程，观察蜂会逐渐向蜜源丰富区域靠近，在编码中表现为雇佣蜂搜索范围受限导致蜜源质量优化幅度有减弱的趋势。为了使ABC算法每次迭代均有效，采用改进动态邻域搜索算法来增强观察蜂阶段的搜索能力，具体如下： (1)变换邻域结构 在个体的出入库作业编号和穿梭车作业编号随机指定两个位置进行交换，得到新的出入库作业任务顺序。 (2)插入邻域结构 将某一随机出入库作业编号插入个体的出入库作业向量指定的位置。 (3)分配邻域结构 将指定出入库任务随机分配到就近的穿梭车进行作业，以减少空跑时间。 (4)变异邻域结构 采用锦标赛选择的方式，通过个体竞争决定此时需完成的出入库任务由哪辆穿梭车执行或是否由该穿梭车执行[26]。 基于动态邻域操作改进观察峰的搜索操作过程如图8所示，具体为：在一次邻域结构操作结束之后，比较子代个体与父代个体的适应度值。若子代个体适应度值优于父代个体，则保留子代个体，结束邻域搜索；若子代个体仍劣于父代个体，则继续进行下一邻域操作，直到得到更优个体。 2.2.4 侦查蜂操作 侦察蜂在蜂巢的主要任务是搜索新蜜源，对侦查蜂阶段的改进主要集中在如何避免算法陷入局部最优以及新蜜源的更新机制。设置公告栏并在侦查蜂搜索之前调用公告栏，以便公告栏记录当前最优蜜源对应的解和出入库作业任务时间。结合路径规划问题对侦查蜂进行如下改进操作： (1)单一对比 利用初始种群规则初始化侦查蜂蜂群，将初始化后的食物源适应度值与全局最优解对比，若全局最优解劣于初始化后的食物源，则考虑更新旧食物源。 (2)全局对比 初始化后的食物源再与所有食物源集合的解对比，如果优于食物源最差解，则直接替换食物源最差解部分。经过两次对比，即可保留较好的食物源并记录在公告栏。 ABC算法的设计和具体问题关系密切，下面对ABC算法求解TTAASBS/RS出入库库复合作业的关键技术进行说明，并给出算法流程。 2.3.1 编码 利用ABC算法求解出入库复合作业任务调度问题时需对问题进行编码，合适的编码方式有助于简化问题。基于TTAASBS/RS模型特性，采用出入库混合整数编码，编码序号表示出入库任务的编号和穿梭车作业编码。假设有S对复合作业任务，则存在S个入库任务和S个出库任务，其中将S个出库任务随机编码为1～S，S个入库任务随机编码为S+1～2S，当出库任务数≠入库任务数时，考虑任务补齐，将I/O点(0，0，0)位置做为虚拟的出库(入库)作业位置，相当于系统只执行单指令出/入库任务。 确定了穿梭车的任务序号就确定了转载车的任务序列。其中穿梭车的数量为4个，分散在整个仓库系统。穿梭车的任务配比不固定，只确定每辆穿梭车的最小任务数量，若其出现故障，则改变最小作业数量，并保留浮动任务数量，具体任务匹配数量由实验得出。例如，4辆穿梭车处理40个任务，在求解过程中，将求解问题看作多旅行商问题，每个穿梭车分配的最小任务数为8，剩余8个任务作为浮动任务随机分配。若车辆有故障，则只调整穿梭车的最小作业任务数量，例如由3辆穿梭车进行出入库作业，将最小任务数调整至12，剩余4个作为浮动任务随机分配给3个穿梭车。出入库编号确定转载车的编码，如表3所示，出库作业编号为2，对应的出库位置为(5,7,4)，位于第4层，采用编号为4的转载车；入库作业编号为33，对应的入库位置为(7,20,12)，对应编号为12的转载车。 图9所示为ABC算法编码方式，其中采用4个穿梭车执行20对出入库复合作业任务，穿梭车1执行12→36→20→31→16→33→1→23→17→32→15→38,穿梭车2执行14→27→5→30→19→21→6→25,穿梭车3执行8→28→3→22→4→34→13→37→2→29,穿梭车4执行9→26→11→24→18→38→7→40→20→39。 2.3.2 适应度函数 本文以完成所有订单内复合作业的调度总时间最小为优化目标，则适应度函数可表示为 fitness=T=minCmax。 式中：T为完成订单内所有出入库作业的时间；Cmax为人工蜂群代表的完成所有任务的最大完成时间。 2.3.3 算法步骤 步骤1初始化蜜蜂种群，包括最大迭代次数MaxCycle、蜜源和总群规模SN，以及蜜源改善的最大搜索次数limit。 步骤2采用随机选择和规则选择进行种群初始化，种群规模为蜜蜂的个数。 步骤3评价所有蜜源适应度并进行排序，排名靠前的成为雇佣蜂，排名靠后的为观察蜂，一般雇佣蜂和观察蜂的数量为SN的一半。 步骤4雇佣蜂阶段。雇佣蜂通过局部搜索寻找新的蜜源，结合设计的雇佣蜂阶段交叉变异产生的新解重新计算适应度函数值，然后根据贪婪准则选择更好的适应度函数值所对应的蜜源。 步骤5观察蜂阶段。引用动态邻域搜索增强观察蜂搜索操作，观察蜂根据适应度值判断是否跟随雇佣蜂前往蜜源。 步骤6侦查蜂阶段。如果雇佣蜂和观察蜂在蜜源搜索次数超过limit时仍未找到更佳蜜源，则视为放弃该蜜源，对应蜜蜂转化成侦查蜂。 步骤7记录当前迭代次数的最优适应度值并记录在公告栏，判断是否满足停止准则，若满足则停止算法，否则转步骤3。 核心伪代码如下： Begin 1 %初始化算法 2 对初始种群、雇佣蜂、观察蜂、蜜源、侦查蜂最大搜索次数等参数进行初始化； 3 初始化路径,x,y,z分别对应转载车、穿梭车、提升机运行方向； 4 %开始迭代人工蜂群 5 While(iter≤MaxCycle) 6 %雇佣蜂模式 7 for i=1:Foodnumber %Foodnumber为雇佣蜂数量为蜜源的一半 8 对雇佣蜂阶段进行交叉变异操作； 9 FitnessSol=calculateFitness(route_next); %计算新蜜源的适应度函数 10 if(FitnessSol >Fitness(i))%若能找到更好的蜜源，则搜索次数清零； 11 trial(i)=0； 12 else 13 trial(i)=trial(i)+1;%若超过设定的limit次数，则雇佣蜂变为侦查蜂； 14 end 15 end 16 i=1； 17 p(1)=fitness(i)/sum(fitness(i))； 18 for i=2:Foodnumber 19 p(i)=p(i-1)+fitness(i)/sum(fitness(i))； 20 end 21 %观察蜂模式 22 for i=1:Foodnumber 23 if(rand 24 改进后雇佣蜂对第1个蜜源进行开采； 25 FitnessSol=calculateFitness(route_next); %计算新蜜源的适应度函数 26 if(FitnessSo1>Fitness(i)) %若能找到更好的蜜源，则搜索次数清零； 27 trial(i)=0; 28 else 29 trial(i)=trial(i)+1； 30 end 31 else 32 for i=2:Foodnumber 33 if(p(i-1) 34 改进后雇佣蜂对第i个蜜源进行开采； 35 FitnessSol=calculateFitness(route_next); %计算新蜜源的适应度函数 36 if(FitnessSo1>Fitness(i)) %若能找到更好的蜜源，则搜索次数清零 37 trial(i)=0; 38 else 39 trial(i)=trial(i)+1; 40 break 41 end 42 end 43 end 44 end 45 end 46 ind=find(Fitness==max(Fitness))；%记录此时更优的解 47 %侦查蜂阶段 48 ind=find(trial==max(trial)); 49 ind=ind(end); 50 if(trial(ind)>limit) %若搜索次数超过极限值，则进行随机搜索产生新的解 51 trial(i)=0； %表示产生了新解，未被开采 52 对侦查蜂进行最优值对比操作； 53 %程序运行完一次，记录这一次的最优时间 54 end 55 end 56 可视化视图 End 为验证改进的ABC算法在求解TTAASBS/RS路径规划问题的有效性，采集和设计自动化立体仓储中设备的性能参数，以满足TTAASBS/RS的存储规格。货架层数为18，排数为14，深度为40列储位，穿梭车数量为4，转载车的数量为货架层数18，提升机的数量为2，其余TTAASBS/RS的参数设置如表2所示。 表2 TTAASBS/RS参数表 用程序分别随机生成20对复合作业任务，为了使实验结果真实有效，又增加30对和50对复合任务对分别进行仿真研究。表3所示为20个复合作业任务对，分为出库任务与入库任务。 表3 出入库任务表 根据穿梭车是否跨层跨巷道将复合作业时间分为3类，分别为跨层作业(跨巷道和不跨巷道)、不跨层跨巷道作业和不跨层不跨巷道作业，假定出库货位a和入库货位b的坐标分别为(xa,ya,za)和(xb,yb,zb)，则穿梭车以上一入库作业位置(xb-1,yb-1,zb-1)为初始位置开始作业，完成一次完整的出入库作业任务所需要的时间为 (26) 一次完整的出入库作业任务示意图如图10所示。 图10和式(26)中：t1，t8，t14，t18为穿梭车单独运行时间，t3，t7_1，t7_2，t13为穿梭车结合转载车运行时间，t5，t11为提升机结合穿梭车运行时间，虚线表示未发生实际运动，以上运动时间与设备运行距离以及速度、加减速度有关；t2，t6，t9，t12为穿梭车等待转载车的时间，t4，t10为等待提升机的时间，在图中已标出；t15为提升机装(卸)穿梭车时间，t16为转载车装(卸)穿梭车时间，t17为穿梭车装(卸)货物时间，t15，t16，t17为定值。 采用程序为各穿梭车分别随机分配一组出入库复合作业任务顺序：穿梭车1为12→36→14→40→20→39→8→28，穿梭车2为16→33→9→26→19→21→11→24→1→23→5→30，穿梭车3为3→22→6→25→17→32→4→34→18→35，穿梭车4为13→37→15→38→7→40→2→29→10→39。最终花费时间为792.4 s。 采用基本ABC算法为穿梭车分配如下出入库复合作业任务顺序：穿梭车1为7→22→14→27→2→26→10→35；穿梭车2为18→38→4→28→15→31→17→30→11→39，穿梭车3为3→40→8→37→12→25→20→24→1→33→6→23，穿梭车4为19→32→13→34→16→21→5→29→9→36。最终花费时间为664.2 s。 采用改进的ABC算法进行优化，根据文献[27]对ABC算法参数进行分析，设置改进后的ABC算法参数为：初始蜜源SN=80，Foodnumber=SN/2，侦查蜂蜂群搜索最大搜索次数limit=100，MaxCycle=500，并采用相应的交叉变异操作。优化后的作业顺序如下：穿梭车1为3→27→14→40→7→34→17→33→15→36，穿梭车2为8→26→10→29→18→30→6→21→1→24，穿梭车3为5→39→9→25→13→35→2→31→11→28，穿梭车4为4→32→12→22→19→37→16→39→20→23。最终花费时间为633.5 s，结果如表4所示。 表4 原始作业任务与改进后作业任务对比 如表4所示，当原始路径随机分配时，穿梭车分配任务数量不均衡，任务序列未优化，导致完成所有任务所需的时间较长；基本ABC算法在一定程度上优化了任务完成时间，但是单个穿梭车分配的任务个数相对不均衡；改进的ABC算法优化了穿梭车的作业任务数，使单个穿梭车分配的任务数量更加均衡，进一步缩短了作业任务总时间。 为验证算法有效性，将本文算法分别与基本ABC算法、GA、改进的蚁群算法[28]、改进的人工鱼群算法[3]对出入库复合作业调度进行实验对比。给定GA的交叉、变异规则，规定采用部分映射交叉，交叉概率pc=0.8，选用非均匀变异，变异概率pm=0.1，种群规模size=500；对5种算法进行综合比对，分别记录5种算法求解的最优值和解的标准偏差，以20对复合作业任务对为实验基础，采用MATLAB 2017编程，运行30次，并在每次迭代100次不改变最优值时记录该最优值，结果如表5所示。 表5 5种算法针对20个任务对的实验结果 图11所示为算例的5种算法各独立运行30次的平均收敛过程曲线。 由表5和图11，结合本文问题分析可知：GA因收敛较慢且容易陷入局部最优，导致求解精度差、效率低；基本ABC算法具有较强的全局搜索能力，然而由于随机邻域搜索导致雇佣蜂搜索能力低，以及观察蜂更新形式具有局限性等问题，使得求解精度较差；改进的蚁群算法虽然能够较快接近最优解，但是在求解复杂问题时存在局限性，跳出最优解的能力较弱且求解时间较长，需要迭代更多次数才能达到相对最优解，求解精度劣于改进人工鱼群算法；改进的人工鱼群算法在求解最优值方面相对其他3种算法虽然在寻优上具有一定优势，但是相对本文改进ABC算法，求解精度较低、算法运行时间更长。本文改进的ABC算法，通过改进初始种群生成以及雇佣蜂阶段的交叉变异操作，使算法的全局搜索能力更优，而且在观察峰阶段采用邻域搜索及时跳出局部最优去搜索更优解，较其他4种算法具有更强的全局搜索能力和跳出局部最优解的能力，相对于改进的人工鱼群算法具有更强的最优值求解能力。 在不同任务量下，改进ABC算法较其他5种算法均表现出更优的稳定性和求解效率。为更进一步验证算法有效性，增加复合作业任务对数，求解结果如表6所示。 表6 5种算法在不同规模下的实验结果 30个任务对和50个任务对的作业规模算法迭代如图12和图13所示。 从表6、图12和图13可见，随着任务量的增加，5种算法的优越性更加明显，其最优解均值都不同程度地小于随机生成解的均值。然而对比5种算法可以发现，改进后的ABC算法的求解精度和优化效率均高于其他4种算法。改进的蚁群算法在前期求解质量较好，后期跳出局部最优的能力不足，且求解稳定性不如其他改进算法，求解效果不如改进的人工鱼群算法；改进的人工鱼群算法在求解效率上明显弱于ABC算法，由于求解的任务量增大，改进的人工鱼群算法为确保求解精度导致收敛速度较慢，以至于后期求解效果不佳;而改进后的ABC算法在求解复杂的仓储调度问题方面能够保证求解精度和求解稳定性，证明了其在求解该类问题时具有优势。 本文对TTAASBS/RS复合作业路径进行研究，为提高TTAASBS/RS的出入库复合作业效率，对该系统复合作业三维路径进行研究；为贴合实际仓储系统的运行规律，考虑穿梭车、转载车和提升机的加减速度，将设备运行规律类比到混合流水线模型，并建立了三任务五阶段的复合作业调度模型；而且设计了改进的ABC算法对该模型进行仿真求解，并通过实验与其他改进算法进行对比。 实例仿真结果表明，改进的ABC算法在求解跨层跨巷道复合作业路径规划问题上具有优越性，其算法效率较基本GA、基本ABC算法、改进人工鱼群、改进蚁群算法有较大提升，能够提高算法效率，优化作业路径。 TTAASBS/RS复合作业路径优化涉及多方面要素，可以进一步研究的方向如下： (1)穿梭车、转载车和提升机三者之间存在能力匹配问题。实际工程应用中穿梭车数量的配置比较灵活，当任务规模变大时，首先可以考虑提高每辆穿梭车的最小作业任务数量，其次考虑不超出提升机能力的情况下增加穿梭车数量。若超出提升机的能力，则考虑增加提升机数量来缓解瓶颈，此时需要重新调整模型结构。 (2)本文案例研究中，穿梭车、转载车和提升机三者之间能力平衡。为了降低模型的复杂度，本文模型假设“一旦穿梭车进入某一巷道，就锁死该巷道”，避免了同一巷道出现两辆穿梭车的情况。然而，理论上存在两辆穿梭车在同一巷道执行任务的情况，可进一步深入研究。 (3)本文未考虑穿梭车运行过程中发生故障后剩余任务的分配问题，可作为继续研究的内容。 (4)本文转载车的数量设定为每层一台，未来可结合跨层跨巷道仓储系统的资源配置进行深入研究，使转载车的数量最少，并研究最优的转载车和穿梭车数量配比。
2.3 改进人工蜂群算法设计
3 仿真实验研究
4 结束语
