多深度四向穿梭车仓储系统调度优化

占翔南，徐立云+，凌旭峰，陈 晨

(1.同济大学 机械与能源工程学院，上海 201804;2.上海师范大学天华学院 人工智能学院，上海 201815)

0 引言

多深度四向穿梭车仓储系统是一种集仓储、配送、管理等功能于一体的新型智能仓储系统，具有空间利用率高，鲁棒性强，响应速度快等优点，受到企业的广泛关注。四向穿梭车作为该系统的作业搬运设备，可以在多深度储货区的主干道及储货巷道中移动，其运行效率对出入库订单交付具有直接影响。多台四向穿梭车同时作业，一方面容易引起四向穿梭车冲突死锁问题，另一方面会加大整个仓储调度的复杂性，因此，如何制定合理的任务调度策略以提高系统运行效率是亟待解决的关键问题。

目前，为适应自动化立体仓储系统的发展与应用，国内外学者对仓储系统作业调度开展了相关研究。方彦军等[1]研究了自动小车存取系统的复合作业问题，将自动小车存取系统中的三维路径进行拓扑建模，采用改进的人工狼群算法求解，验证了算法的有效性；杨玮等[2-3]针对子母式穿梭车及双载式多车穿梭车仓储系统作业调度问题进行了研究，分别采用混合粒子群和混合植物繁殖算法对相应的数学模型进行求解；WU等[4]则以任务完成时间及资源利用率为目标建立多目标作业调度模型，采用改进遗传算法进行求解，并通过Java语言构建任务调度仿真平台对调度实例进行仿真分析；ZHAN等[5]对双深度多层穿梭车仓储系统作业调度问题进行了研究，以出库时间、等待时间和系统碳排放最小为目标建立了多目标作业任务调度模型，并采用带精英策略的非支配排序遗传算法对其进行求解，通过实例验证了模型及算法的有效性；YANG等[6]研究了双货位堆垛式自动化立体库中堆垛机执行出入库任务过程中的作业调度问题，建立了以作业时间最小为目标的整数规划模型，并通过仿真分析发现出入库任务次数对求解效率有较大的影响；鲁建厦等[7]对跨层穿梭车仓储系统复合作业问题展开研究，通过分析提升机与穿梭车的实际作业流程，建立出入库复合作业模型，并采用改进人工鱼群算法进行求解。然而，上述仓储系统作业调度问题的文献均以单台搬运设备为研究基础，缺乏对多台搬运设备同时作业的研究和优化。

沈博闻等[8]针对仓储系统中车辆集群调度进行了研究，首先将仓储系统中的车辆运行环境进行网格划分，在考虑车辆运行时序的基础上使用A*算法解决了车辆寻路及多车避碰的问题；刘二辉等[9]则采用改进的灰狼优化算法解决了多AGV(automated guided vehicle)作业路径问题，并使用MATLAB开发工具搭建了仿真平台，验证了模型和算法的有效性；LI等[10]针对仓储系统中的多车任务调度问题，考虑任务的执行时间窗及任务执行距离进行建模，并采用改进蚁群算法进行求解；GHASSEMI等[11]针对分布式的多车调度系统进行了研究，提出一种三阶段的分布式多车调度算法，旨在解决随着问题规模(车辆/任务数量)的增加而导致的计算成本激增的问题，算法将模糊聚类、二分图及最大权重匹配3种方法进行组合，最后使用不同的案例验证了算法的有效性。

为解决多台穿梭车同时作业导致的冲突死锁问题，LI等[12]和ROY等[13]均采用了区域控制法，将仓储系统划分为互不重叠的区域，且每个区域只允许一台四向穿梭车执行任务；LEE等[14]构建了基于Cyber-Physical系统，用于检测仓储系统状态并获取实时数据，采用最短路径算法为每台穿梭车提前规划好路径，并使用时间窗方法检测穿梭车的冲突，通过一定的规则调整穿梭车的运行速度和路径，最终得到无冲突的调度方案；刘元[15]在时间窗的基础上，针对多AGV仓储系统中的冲突死锁问题提出了等待算法、路径重规划算法和综合调度算法3种解决方案，其中综合调度算法能够根据实际情况灵活选择路径解决方案，鲁棒性更强。

综合以上研究，已经有学者从自动化立体仓储系统及其相关问题出发，对作业任务调度进行研究，并应用于工程实践，但仍存在以下不足：①目前研究的仓储系统储货区均为单深度或双深度，没有考虑多深度储货区对作业调度的影响，当多个出入库任务出现在同一储货巷道，则系统会发生堵塞，影响作业效率；②冲突死锁问题中，区域控制法和预测控制法会增加作业任务的中间环节，限制穿梭车作业范围，从而降低仓储系统作业效率；③实时调度对仓储设备要求响应速度要求极高，且会加大调度系统的瞬时工作量，从而影响系统的稳定性。

本文以多深度四向穿梭车仓储系统为研究对象，对多台四向穿梭车同时作业的调度问题进行研究。针对上述问题，首先采用图论方法解决多台穿梭车同时作业导致死锁问题，根据Hopcroft-Tarjan算法深度优先搜索特性，依次访问系统中每个储货点获取路径方向，生成四向穿梭车在多深度储货区的定向作业路径，用于解决多车路口冲突和相向冲突，从而避免四向车穿梭车任务死锁问题。然后，在此基础上建立出入库复合作业调度优化模型，设计了一种改进混合遗传算法进行求解，对编码方式的调整和变异修复机制进行改进，并提出基于任务顺序的多位置邻域交换法，能够克服迭代过程中易出现非法解的问题，增加解空间的多样性，从而有效提升收敛速度和全局搜索能力。

1 布局与假设

1.1 布局描述

多深度四向穿梭车仓储系统由多深度高密度存储货架、四向穿梭车、输送系统及控制系统组成。多深度存储货架用于货物存储，每个储货巷道有多个空格代表多个存储货位，同一储货巷道只能存放同一类货物；四向穿梭车用于实现货物的水平运转；输送系统位于该仓储系统的入库口和出库口，用于实现货物的进出转运；控制管理系统负责整个仓储系统的设备监控和作业任务调度。

如图1所示为多深度四向穿梭车仓储系统的布局图，位于中间主干道上方的称为上储货区，位于中间主干道下方的称为下储货区。在该仓储系统中，每层的布局均相同，出入库提升机分别位于出库口和入库口。四向穿梭车可以沿着储货巷道及货架横向和纵向行驶。当四向穿梭车处于空载状态时，可以在存有货物的多深度巷道中自由穿梭，到达仓储系统的任意存储货位；当四向穿梭车处于载货状态时，只能在空闲的多深度巷道及主干道上行驶。同一层中放置多台四向穿梭车同时进行出入库作业，以提高系统的灵活性。

1.2 作业流程

在多深度四向穿梭车仓储系统中，四向穿梭车入库作业流程如下：

(1)当入库任务产生时，任务对应的货位状态发生改变，表示该货位将有货物入库，不再产生其他的入库任务；

(2)接收到该入库任务的四向穿梭车从当前位置运行至入库口，从入库口处取得货物，此时四向穿梭车从空车状态变为载货状态；

(3)以目标货位所在的储货巷道入口为目的地，根据路径定向策略，为四向穿梭车规划行驶路径；

(4)四向穿梭车进入目标货位所在储货巷道，到达目标货位放置货物，并更新该货位的货位状态，入库任务结束。

四向穿梭车出库作业流程如下：

(1)当出库任务产生时，任务对应的货位状态发生改变，表示该货位将由货物出库，不再产生其他出库任务；

(2)接收到该入库任务的四向穿梭车从当前位置运行至目标货位，从目标货位处取得货物，此时四向穿梭车从空车状态变为载货状态；

(3)以出库口为目的地，根据路径定向策略，为四向穿梭车规划行驶路径；

(4)四向穿梭车运行至出库口，放置货物，并更新该货位的货位状态，出库任务结束。

当系统完成任务分配，如何使多台四向穿梭车合理配合，高效完成作业任务是多深度四向穿梭车系统调度优化的目的。因此，需要对多台穿梭车的作业路径进行规划，而建立合理正确的复合作业模型是调度优化的关键。

1.3 假设与符号

为建立合理正确的调度优化模型，需对模型的主要假设条件和参数符号进行说明。同时为了研究方便且不失一般性，进行如下假设：

(1)四向穿梭车服从终点停靠策略(Point-of-Service-Completion，POSC)，即四向穿梭车会停靠在当前任务结束的位置；

(2)货物先进先出原则，为保证仓储系统货物先进先出，储货巷道内的货物采用先进先出的操作方式，即只从储货巷道一端入货，从另一端出货；

(3)该系统内同时存在入库任务和出库任务，四向穿梭车服从单一作业模式；

(4)四向穿梭车为匀速行驶，不考虑加速度；

(5)四向穿梭车执行任务是状态稳定，保证有充足电量完成任务。

本文用到的主要参数如表1所示。

表1 主要参数说明

2 系统建模

2.1 多深度储货区路径策略

在多深度四向穿梭车仓储系统中，当多台四向穿梭车同时作业时，主干道交叉口及多深度储货巷道内可能出现四向穿梭车冲突与死锁现象，将导致储货区堵塞，使出入库任务无法正常执行。因此，如何避免四向穿梭车冲突与死锁问题是解决作业调度的关键内容之一。本文针对该问题，采用Hopcroft-Tarjan算法对多深度储货区制定路径定向策略，在运行规则上避免四向穿梭车冲突死锁问题，从而可以实现全区域作业，减少作业任务中间环节，提升作业效率；另一方面，采用该方法可以降低调度系统的实时调度压力和设备实时响应的要求，增强仓储系统的稳定性。

对多深度储货区的交通网络进行建模，将其建模为图G={V(G),E(G)}，将主干道和储货巷道抽象成图G的边，将交叉路口抽象成图G的顶点。对多深度储货区中的交通网络进行路径定向，实际是设定图中每条单向边的方向，使其成为具有强连通性的有向图。对于不含割边的连通图G，采用Hopcroft-Tarjan算法求得G的强连通定向图的步骤如下：

步骤1任取G中的一个顶点v，令l(v)=1，L={v}，U=V-{v}，R=∅；

步骤2在L中取顶点u，使得l(u)最大且满足在U中存在与u相邻的顶点，然后从U中取一个与u相邻的顶点w，使得边uw成为有向边u→w，同时令l(w)=l(u)+1，L=L∪{w}，U=U-{w}，A=A∪{u→w}；

步骤3若L≠V，转步骤2，否则执行步骤4；

步骤4对当前还未定向的边ab，按照以下方法进行定向：若l(a)>l(b)，则指定方向后的边为a→b，否则边为b→a。

上述步骤中，R为已经确定方向的边的集合，L为已经给出标号的顶点集合，U为还未给出标号的顶点集合。

根据罗宾斯定理，图G会出现多种强连通定向图，需要结合仓储布局及出入库原则，确定最终路径定向策略。为保证最终定向结果有利于仓储系统的高效运转，应优先满足如下条件：

(1)由于入库口位于左上角，应将X方向上靠近入库口位置的1#主干道的方向设定为从左至右的方向；

(2)由于入库口位于图的上方，应将储货巷道的入口处放置在1#及2#主干道上，以便实现储货巷道中货物的先进先出，因此储货巷道的方向应由上至下。

根据上述优先满足条件，采用Hopcroft-Tarjan算法，将多深度储货区交通网络定向图与出入库口路段结合后，最终得到的路径定向图如图2所示。

2.2 作业调度模型

在多深度四向穿梭车仓储系统中，通过对四向穿梭车作业过程分析，可将多深度四向穿梭车仓储系统调度问题转化成柔性车间作业调度问题。柔性车间作业调度问题可以描述为：多个工件需要在多台机器上进行加工，每个工件均有多个加工工序，每个工序的加工时间在不同工况的机器上不同，且同一个工件的工序之间具有先后约束，需要合理分配每台机器上的加工工序，并确定工序的先后执行顺序，最终得到一个使得加工时间最短的分配方案。对于多深度储货区四向穿梭车调度问题来说，不同出入库任务可视为待加工工件的不同工序，同时作业的四向穿梭车可以视为并行运行的加工机器，不同出入库任务可由不同穿梭车执行，以完成所有作业任务的最短时间为目标进行求解，最终得到四向穿梭车的多车任务分配及任务执行顺序方案。

ki>0,i∈[1,m]；

(1)

(2)

(3)

(4)

Aq∩Aw=∅,∀q,w∈[1,m]。

(5)

其中：(1)表示每辆四向穿梭车至少分配一个任务；式(2)表示四向穿梭车在空载阶段运行时间不能为负值；式(3)表示四向穿梭车在装载阶段运行时间必须为正值；式(4)表示四向穿梭车将执行所有任务；式(5)表示一个任务只能由一辆四向穿梭车执行。

根据以上约束模型，构建如下目标函数：

funC=min(max(Ti))。

(6)

最小化多台四向穿梭车完成出入库任务时间最大值，即完成所有作业任务的总时间最短。编号为i的四向穿梭车完成ki个任务的作业时间如下：

(7)

四向穿梭车的作业时间由具体任务决定，且车辆的起始点及货物位置有关，根据上述路径定向策略规划车辆路径，进行相应作业时间计算。对于入库作业任务，四向穿梭车首先从起始点运行至入库口装载货物，然后根据多深度储货区路径定向策略，制定相应的路径，从入库口运行至目标货位，入库任务作业示意图如图3所示，其空载阶段运行时间为：

(8)

满载过程运行时间为：

(1)当目标货位位于上储货区时，

(9)

(2)当目标货位位于下储货区时，

(10)

对于出库作业任务，四向穿梭车首先从起始点运行至目标，然后根据道路定向策略，制定相应的路径，从目标货位运行至出库口，出库作业示意图如图4所示，其空载阶段运行时间为：

(11)

满载过程运行时间为：

(1)当目标货位位于上储货区时，

(12)

(2)当目标货位位于下储货区时，

(13)

3 算法设计

遗传算法(Genetic Algorithm,GA)是一种通过模拟自然进化过程搜索最优解的方法，非常适用于处理传统搜索算法难以解决的复杂优化问题。遗传算法具有较强的全局搜索能力，但局部搜索能力较弱。为解决多深度四向穿梭车仓储系统作业调度问题，本文将模拟退火算法(Simulated Annealing algorithm,SA)较强的局部搜索能力引入到遗传算法的搜索过程中，构建一种改进混合遗传算法(Improved Hybrid GA,IHGA)，该算法兼具遗传算法的全局搜索能力和模拟退火算法高效的局部搜索能力。为进一步优化改进混合遗传算法的性能，通过编码方式的调整和变异修复机制的改进有效避免迭代过程中易出现非法解的问题，避免算法过早收敛和局部早熟，并提出一种基于任务排序的多位置邻域交换法，有效增加解空间的多样性，进而提高算法搜索性能。

3.1 算法流程

IHGA的工作原理为：首先利用GA对初始种群进行遗传操作，以达到进化种群的目的，再通过模拟点火算法的Metropolis抽样过程对遗传算法进化得到的结果进行抽样判定，而抽样得到的结果又会成为遗传算法进行下一代进化操作的初始种群，算法流程如图5所示。

IHGA算法基本流程如下：

步骤1设置相关参数，主要包括：种群规模N，交叉概率Pc、变异概率Pm、最大迭代次数G、退温控制值d、退温速率λ；

步骤2根据约束条件，生成规模为N的初始种群P；

步骤3计算每个个体适应度并排序，根据精英保留策略，选择一定比例的最优个体进行保留；

步骤4通过锦标赛选择法选择种群中适应度高的个体进入下一步操作；

步骤5采用自适应交叉和变异算子，对种群进行交叉和变异操作；

步骤6根据任务排序的多位置邻域交换方法产生新解，若符合Metropolis准则，则接受新解，否则保留原始解，由此产生模拟退火后的新种群P′；

步骤7判断当前是否满足算法终止条件，若满足，则结束算法流程并输出最优方案，否则转步骤3。

3.2 算法实现

(1)构造个体

为同时描述出入库任务分配及四向穿梭车作业顺序，采用如图6所示的双段染色体编码方式，其中：第一段代表作业任务的编码，称为任务码；第二段代表四向穿梭车执行任务数的编码，称为车辆码，每条染色体对应一个调度方案，用于描述每辆四向穿梭车分得任务及任务执行顺序。

如图6所示，当任务码为[6,3,7,8,5,1,2,4,9,10]，车辆码为[2,1,3,4]时，经过解码可知，1号四向穿梭车任务数为2，执行顺序为[6,3]；2号四向穿梭车任务数为1个，为7；3号四向穿梭车任务数为3，执行顺序为[8,5,1]；4号四向穿梭车任务数为4，执行顺序为[2,4,9,10]。

(2)适应度函数

由于目标函数值均大于1，选择目标函数值的倒数作为个体的适应度值，当完成所有任务的时间越大时，适应度函数值越小。适应度函数如式(14)表示：

(14)

式中Tmax表示四向穿梭车执行任务的最大完成时间。

(3)选择算子

本文采用锦标赛方法进行个体的选择操作，每次从种群中选取2个个体进行适应度比较，将适应度值高的个体放入交叉池，循环操作得到数量为N的种群。同时，使用精英保留策略将优秀个体进行保留，提高算法的全局收敛性。

(4)自适应交叉和变异

标准遗传算法使用固定的交叉率和变异率来确定染色体是否进行交叉和变异操作，会存在两个问题：①概率取值过小时会导致搜索效率较低，不利于寻找到全局最优解；②概率取值过大时则有可能破坏较优个体，导致较优方案的丢失。因此，本文采用自适应交叉与变异方法进行操作，避免算法出现早熟和局部收敛问题。

(5)交叉算子

考虑到编码方式的特殊性，个体如按照标准遗传算法的交叉会产生非法解，因此仅对任务码进行交叉，对车辆码进行保留。本文采用两点交叉方式对任务码进行交叉，如图7所示。对于第二段车辆码部分，如果使用两点交叉法进行交叉操作会使得四向穿梭车执行分得任务数量变化较大，不利于进一步产生更优方案，因此在该阶段第二段车辆码直接保留到子代。

(6)变异修复

对于第一段任务码进行变异操作。采用交换变异的方法，如图8所示，随机选择两个变异点，交换父代选定的变异点得到新的子代。

对于第二段车辆码进行变异操作时，随机选取数个车辆，采用邻值变异法对车辆对应的任务数量进行变异操作。在变异操作过后，检查当前得到的染色体是否符合约束条件，对不符合约束条件的染色体进行修正。修正方法如下：如图9所示，当父代为[2,1,3,4]，选中[1,3,4]进行邻值变异操作，变异结果为[0,4,3]，此时2号车分得的任务数量为0。为了修复0值基因，从当前基因最大值上减1，给0值基因加1，得到经过0值基因修复后的子代[2,1,3,3]，此时任务数量总和为9，小于变异前的任务数量总和10，将该差值加到基因最小值上，得到经过修复总和操作的子代[2,2,3,3]，该子代满足所有约束条件。经过改进的变异方式不会产生非法解，有利于可行解的搜索效率。

(7)控制参数的初值设置

控制参数t的初值设置直接影响算法的局部搜索能力和搜索速度。初值越高，算法最终获得高质量解的概率越大，但搜索时间越长；初值越低，搜索速度越快，但局部搜索能力越低。本文中控制参数的初值按照式(15)确定：

(15)

式中：fmax和fmin为当前群体中最佳个体和最差个体的适应度；Pr为控制参数t的初始接受概率。

(8)邻域交换

本文提出了一种基于任务排序的多位置邻域交换法，能够有效增加解空间的多样性。其交换过程可以描述为：对于要交换的个体i，随机产生[1,40]区间内的k(k≤40)个不同的整数：x1,x2,…xk。 依次对个体i第xi(1≤i≤40)位置的部分染色体进行多位置邻域交换。首先，算法随机产生一个[1,max]区间的整数len，len是进行交换的长度，max为设置的最大值，本文中取值为10。然后，从当前的部分染色体中随机选择两端长度为len的染色体段，进行标准邻域交换。最后，检验交换后的个体i′是否满足约束条件，若不满足约束条件，则取消交换。重复上述过程，直到k个部分染色体交换完毕后，输出交换后的个体i′，其流程图如图10所示。

(9)退温函数

在改进混合遗传算法的模拟退火理论部分，要求控制参数t的值能够以一个适中的速度下降，否则会影响算法的局部搜索能力和解的质量。在算法搜索过程中，若产生的可行解数量较多，那么t的下降速度较快，本文按照式(16)对控制参数进行降温操作。

t(k+1)=λtk。

(16)

式中:λ为常量，λ∈[0,1]，λ的值越小，t的下降速度越快。

(10)新解的接受机制

新解的接受机制是改进混合遗传算法实现全局搜索的关键，本文采用Metropolis接受准则作为新解的接受机制。

4 案例研究

电商仓储系统具有时效性强，订单波动大等特点，高峰期日均订单量是平时的几十倍，甚至几百倍，因此对仓储系统的柔性要求非常高。本文以某电商单层多深度四向穿梭车仓储系统为例，对出入库任务分配及四向穿梭车作业顺序进行优化。该仓储系统分为上、下两个储货区，其中每个储货区货位深度为6，巷道数量为32。该层有5辆四向穿梭车，在某一时间窗口内有40个出入库任务需要被执行，各车空闲时的坐标位置点如表2所示，出入库任务如表3所示，其中任务起点为(0,0)点的任务表示入库任务，任务终点为(0,14)点的任务表示出库任务。

表2 四向穿梭车起始位置坐标点

表3 40个出入库任务坐标点

首先，需要对该单层多深度四向穿梭车仓储系统制定路径定向策略，将该仓储系统建模为图G={V(G),E(G)}，将主干道和储货巷道抽象成图G的边，将交叉路口抽象成图G的顶点，得到图G共有67条边，102个顶点。采用Hopcroft-Tarjan算法求解该仓储系统路径定向策略的步骤如下：

步骤1将图G的边依次从1到67开始编号，将图G的顶点依次从1到102开始编号；

步骤2取图G中编号为1的交叉路口v，令l(v)=1，L={v}，U=V-{v}，R=∅；

步骤3在L中取交叉路口u，使l(u)最大并且满足在U中存在与u相邻的交叉路口，然后从U中取一个与u相邻的交叉路口w，使得路径uw成为有向边u→w，同时令l(w)=l(u)+1，L=L∪{w}，U=U-{w}，A=A∪{u→w}；

步骤4若L≠V，转步骤3，否则执行步骤5；

步骤5对当前还未定向的路径ab，按照以下方法进行路径定向：若l(a)>l(b)，则路径ab的方向为a→b，否则为b→a。

根据上述求解步骤，得到多种强连通路径定向图，因此需要结合仓储布局及出入库原则，确定最终路径定向策略。由于入库口位于图G左上角，将靠近入库口的水平主干道的路径方向设定为从左至右，将储货巷道的入口放置在储货巷道的上方，以便实现储货巷道中货物的先进先出原则，因此储货巷道的路径方向为从上至下。

根据Hopcroft-Tarjan算法的求解结果，并结合该仓储系统布局特点，最终得到该单层多深度四向穿梭车仓储系统的路径定向策略。

本文通过与区域控制策略对比来验证路径定向策略的有效性。区域控制策略的思路是根据出入库任务分布，将该仓储系统划分为5个区域，每台穿梭车负责一个区域内的出入库任务。计算程序在MATLAB 2016b平台上运行，计算机配置为Intel(R) Core(TM) i7-7 700HQ CPU @2.80 GHz, 8.00 GB RAM。

根据程序运行得到两种策略下的四向穿梭车任务执行顺序的结果，如表4所示。在区域控制策略下，5台穿梭车的作业时间分别为364.36s、460.87 s、516.45 s、551.29 s和597.42 s，由于5台穿梭车同时作业，任务完成总时间为597.42 s。在路径定向策略下，5台穿梭车的作业时间分别为512.34 s、497.21 s、522.87 s、501.46 s和516.27 s，作业任务完成总时间为522.87 s，如图11所示。由此可知，路径定向策略的优化效率为14.3%。

表4 2种策略下穿梭车分配的作业任务及执行顺序

由图11结果可知，在区域控制策略下，5台穿梭车任务完成时间差距较大，最短任务完成时间为364.36 s，最长任务完成时间为597.42 s，任务完成总时间为597.42 s；由于区域控制策略是根据出入库任务分布，按照区域划分确定穿梭车执行任务范围，导致离出入库口近的任务完成时间短，离出入库口远的任务完成时间长，因此1号穿梭车任务完成时间最短，5号穿梭车任务完成时间最长。在路径定向策略下，5台穿梭车任务完成时间差距较小，最短任务完成时间为497.21 s，最长任务完成时间为522.87 s，任务完成总时间为522.87 s；采用路径定向策略可使得穿梭车在整个仓储系统内执行任意作业任务，不受区域限制，从而提高穿梭车利用率，提升作业效率。

为进一步验证算法的有效性，将GA算法、SA算法和IHGA算法分别对作业任务规模为40,80,120的情况各重复进行100次实验，每个作业任务规模下的货位都是随机产生的，在控制参数的选择上，参考文献[4，16-17]，算法参数如表5所示。

表5 GA,SA和IHGA算法参数设置

经过MATLAB仿真计算，得到3种算法实验结果如表6所示，IHGA相对于GA和SA而言，算法的精度和稳定性都有较大的提升，且减少了求解时间，表明IHGA算法是一种有效的求解算法。随着任务规模的不断增大，出入库任务分配和四向穿梭车执行顺序更复杂，相比于GA和SA算法，IHGA算法的求解精度和稳定性的优势不断扩大，优化效果更为明显，出入库任务分配和四向穿梭车执行顺序更合理，任务完成时间提升更大，系统作业效率更高，从而表明该算法更适用于求解大规模的调度优化问题。

表6 3种算法实验结果对比

如图12所示为GA、SA和IHGA三种算法在不同任务规模下的算法收敛图。GA算法前期全局搜索能力较强，算法收敛速度快，但局部搜索能力弱，从而导致求解的精度不高；SA算法搜索能力强，具有较好的搜索能力，但是算法需要较长的搜索时间，收敛速度慢；IHGA算法结合GA算法和SA算法的优点，充分利用GA算法的全局搜索能力，使得算法前期快速收敛，又结合了SA的局部搜索能力，提高了求解精度，使得改进后的算法具有更好的全局搜索能力及更快的收敛速度。相对于其他两种算法，IHGA算法在求解精度和收敛速度上都有一定的提高，更适合本模型的寻优。

当任务规模为40时，经过IHGA算法优化后得到5台四向穿梭车作业任务执行顺序，如表7所示，5台四向穿梭车的作业时间分别为425.74 s、424.59 s、431.63 s、437.06 s和429.48 s，作业任务完成总时间为437.06 s。优化后得到第4台穿梭车作业路径图如图13所示，第4台穿梭车作业路径顺序为(2,12)→(0,0)→(7,3)→(0,0)→(9,1)→(31,1)→(0,14)→(0,0)→(5,11)→(0,0)→(7,5)→(0,0)→(15,11)→(16,3)→(0,14)→(16,2)→(0,14)。

表7 优化后四向穿梭车分配的作业任务及执行顺序

由上述结果可知，采用Hopcroft-Tarjan算法可以有效制定路径定向策略，从运行规则上避免了多台穿梭车同时作业交叉路口冲突和相向冲突，能够有效解决多台穿梭车全区域作业死锁问题，从而提升作业效率。通过对混合遗传算法编码方式和变异修复机制的改进，能够克服迭代过程中易出现非法解的问题，增加解空间的多样性，提升算法的收敛速度和全局搜索能力。

5 结束语

本文针对多深度四向穿梭车仓储系统调度优化问题开展研究。根据Hopcroft-Tarjan算法提出一种多深度储货区的路径定向策略，在此基础上建立以最小作业时间为目标的调度优化模型，并设计了改进混合遗传算法来优化该仓储布局下的任务调度。实验结果说明，本文提出的路径定向策略可以有效解决四向穿梭车冲突与死锁，提升系统作业效率。为了说明所设计算法的性能，在不同任务规模下，将IHGA算法与GA算法、SA算法的计算结果进行了比较，实例结果表明IHGA算法具有更好的寻优能力和更快的收敛速度，且能较大幅度地提高系统作业效率。下一步，将在此基础上对多层多深度四向穿梭车仓储系统调度优化问题进行研究。