考虑倒箱操作的AutoStore魔方型仓储系统自动引导车双层路径规划

AutoStore系统是一种新兴的紧致轻载仓储系统[1,2],它取消巷道，将标准化货格直接组合在一起，形成魔方型结构；用于存储货物的料箱规格统一，垂直堆存在每个货格中。自动引导车(automated guided vehicle, AGV)在货架顶层沿轨道移动，小车4个侧面各设有一组轮子，能实现前后左右4个方向的移动和转向，小车底部装有伸缩抓取装置。工作台设置在货架边缘，当存储或拣选任务产生时，由工作人员确定要存入或拣选的料箱，将指令发送至AGV管理系统。AGV接受到指令后，移动到目标箱位所在货格顶部，伸缩臂伸入货格将料箱抓取收入自己“腹”中，随后带着料箱移动到工作台顶部，并通过抓取装置将料箱放入工作台通道。待工作人员存入或拣选完货物后，调用AGV将料箱运回，至此，完成一次存储或拣选工作。

从上述工作流程看，AGV为该“货到人”系统的核心环节，对其进行研究能提高系统运行效率。AGV路径规划是生产调度领域的热点问题，中外已有较多研究成果：从问题研究范畴上，可分为静态调度、动态调度和联合调度[3,4];从研究方法上，可分为数学建模方法、仿真优化、智能优化和混合优化等[5,6]。然而，AutoStore独特的仓储结构使得AGV路径规划问题与传统研究有较大区别，主要体现在两个方面：一方面，AutoStore系统中AGV在顶层轨道实现水平方向移动，底部伸缩装置实现垂直方向移动，路径规划问题转变为三维空间路径寻优问题，传统平面路径寻优方法已不适用；另一方面， AutoStore系统中存在大量的倒箱操作，当目标箱不在货格顶层时，AGV需要将其上部的阻碍箱依次搬开直至目标箱处于顶层。这使得AGV除了要完成搬运目标箱的工作外，还需完成相应的倒箱工作。而倒箱的次数和具体位置是可变的，即任务数不确定，增加了路径规划的复杂程度。

现阶段针对AutoStore系统的研究大多关注生产线设计[7,8]、存储策略[9,10]及货位优化[11]。王晓军等[12]认为存储越深的目标箱需要倒箱的可能性越高，因此在AGV路径规划建模时将目标箱垂直提升时间乘以了一个系数，但该研究未考虑倒箱实际操作，本质上还是二维平面路径寻优问题。

考虑到AutoStore系统的倒箱和集装箱堆场倒箱(翻箱)操作有一定的相似处，文献[13,14,15]进行了分析。堆场倒箱主要发生在提箱环节，需要根据目标箱位置及当前堆场的实时状态来制定倒箱堆放策略。在倒箱限制及落箱位的选择上，所研究的内容与堆场倒箱的不同之处如下。

(1)堆场倒箱操作大部分在单贝位内进行，少部分能在相邻贝位进行，但在AutoStore系统中，AGV可带着料箱在整个货格顶层行走，落箱位置选择范围更大，造成倒箱规模复杂。

(2) AutoStore系统是具有自我调节能力的智能系统，产生倒箱操作的料箱不需再运回原处，慢慢地提取率高的料箱会处于货架上层，而提取率低的料箱会沉入下层。

(3)AutoStore大多采用订单批处理的策略，即一次需要提取多个目标箱，使得阻碍箱数量增多，且阻碍箱的落箱位置会相互影响，使得问题研究更为复杂。

考虑倒箱操作的AutoStore系统AGV路径规划需解决以下核心问题：一是建立适合该魔方型仓储拣选系统的倒箱策略；二是如何对能在三维空间活动的AGV路径问题进行建模和求解；三是倒箱和搬运都需要由AGV完成，如何将两者结合起来。

基于上述分析，首先在工作流程基础上对问题进行了界定，给出了建模方法及倒箱、提箱的作业规则；其次建立了AGV路径规划双层模型，内层模型用于求解阻碍箱的倒箱路径，以此为基础，外层模型对多AGV路径规划问题进行了分析；然后基于模型特点提出了嵌套启发式算法，最后通过算例对模型和算法进行了验证和比较分析。

AGV的指令均由工作台发出，根据目标箱与工作台的相对位置，可分为“目标箱出库”和“目标箱入库”两类指令。其中“目标箱出库”指将目标箱搬运至工作台，可分解成如下步骤。

步骤1 AGV接收任务，获取目标箱及其上方阻碍箱的位置信息。

步骤2 从当前位置空驶至目标箱货格顶层。

步骤3 依次搬运阻碍箱至相应落箱位，直到目标箱位于顶层。

步骤4 将目标箱搬运至工作台。

步骤5 出库指令完成，释放AGV。

工作人员在工作台对目标箱完成拣选或存储操作后，发出“目标箱入库”指令，调用最近的空闲AGV,将目标料箱搬运回货架，为了保持货架整体存储平衡，存入最深可用的货格。与“目标箱出库”相比，目标箱入库较为简单，属于起始位置确定且不涉及倒箱操作的AGV调用问题，用最短路径寻优即可解决，因此，主要讨论“目标箱出库”这一阶段。

在货到人工作模式下，存储和拣选的区别体现在工作人员对目标箱的操作及服务时间上，对AGV路径规划求解无本质影响，因此，将二者统一考虑。同时为与实际情况相符，设工作人员一次处理一批订单，订单内包含数个任务，但顺序无先后约束。综上，本问题可以简述为：有一系列待提取目标箱，初始位置和终点位置(工作台)确定，目标箱上面的阻碍箱数量及位置确定，有多个AGV,需要将阻碍箱倒箱及目标箱运输任务分配给各AGV,并指定执行先后顺序，选择最优运行路径。

AutoStore货架呈魔方型结构，在传统栅格法建模[16]基础上，采用栅格法进行三维建模。以货架左下角为坐标原点O,对行、列、层分别建立X、Y和Z轴。以料箱尺寸为基本单位，将货架划分成立体栅格，一个栅格代表一个箱位，用确定坐标(x,y,z)表示。

图1给出了4×4×4规模货架示意图。设货架所有箱位集合为M,根据箱位是否存放料箱又可分为两个子集合：被料箱占用的实箱位集合M1,如箱位a(1,1,4)∈M1;没被占用的空箱位集合M2,如箱位e(2,1,4)∈M2。

货架建模完成后，在顶层坐标(Zmax+1)处建立虚拟栅格区作为AGV移动区，如AGV1当前坐标为(3,1,5),则移动路径可以用一连串栅格坐标表示。AGV充电区设置货格顶层外侧，不影响货格正常存储，同时该区域也是路径规划的起始点和终点，如AGV2的坐标为(0,2,5)。工作台设置在货架外侧，规模尺寸为两个标准化货格，上部为运输通道，分为入库通道和出库通道，下部为人工操作台。AGV将入库目标箱放入入库通道即可离去，目标箱在通道内排队，按先到先服务原则接受服务。工作人员完成操作后，将目标箱推入出库通道底部，依次调用AGV。

同一波次订单达到后，首先对其进行汇总，将同类货品归类，获得待拣货品列表及其所需求数量。考虑到料箱尺寸较小，设定每个料箱只存放一类货品且不能超过料箱容积，同类货品可存储在多个料箱中。对待拣选列表中的任一货品，搜索所有存储该货品的料箱并确认库存，当需求量小于某个料箱现有库存量时，调用该目标箱；当需求量大于料箱最大库存量时，需将该货品订单拆分成两个订单甚至更多，直到每个子订单的需求能被单个料箱满足。对订单进行拆分能将订单任务与需要提取的料箱一一对应，确定目标箱集合N={1,2,…,n},n≥初始订单数。

目标箱确定后，其所在三维坐标系的位置也可以确定，则对应阻碍箱也可以确定。对于目标箱i∈N,存在阻碍箱集合Ei={1,2,…,ni},ni为目标料箱i上面阻碍箱的数目。同批次订单内，所有阻碍箱集合为E={E1,E2,…,En},共有m个阻碍箱，m=n1+n2+…+ni,i∈N。

倒箱操作需将目标箱上的阻碍箱依次转移到其他货格的空余箱位。如图1所示，若c(1,1,2)为目标箱，则b(1,1,3)和a(1,1,4)为阻碍箱，需依次搬运至其他空位。确定每个阻碍箱的落箱位是倒箱操作的核心环节，落箱位需满足当前时刻为空箱且下方为实箱位的条件，如图1中， g被占用，e下方为空，均不满足条件，f、i可作为落箱位。对于阻碍箱j∈E,设落箱位置集合为Dj={1,2,…,mj},其中mj为阻碍箱j的可落箱位置数目。对于所有阻碍箱，落箱位置集合为D={D1,D2,…,Dm}。

通过以上分析，AGV路径规划问题可转化为：将订单分解形成目标箱集合N,调用多个AGV,将阻碍箱集合E中的料箱搬运至集合D,将目标箱集合N中的料箱搬运至工作台W接受服务并返回，在满足相关约束的前提下，获得AGV行驶路径，以提高系统运行效率。

分析可知，AGV任务可分解成两类子任务：搬运阻碍箱和搬运目标箱。对搬运阻碍箱子任务，落箱位不确定，且当某一目标箱上面存在多个阻碍箱时，AGV需要多次返回倒箱；当多个AGV同时进行倒箱操作时，落箱位很容易出现冲突，因此，该任务求解的核心在于建立一个动态箱位状态数据库。对搬运目标箱子任务，需要AGV通过最短路径将目标箱搬运至工作台，问题的核心为多AGV任务指派。这两个任务既有一定独立性又有一定的顺序约束，根据AGV调用情况， 有两种策略可以选择：一是将目标箱和其对应阻碍箱安排给同一AGV,即AGV接收到任务后，行走到目标箱顶层，先进行倒箱，再搬运目标箱；二是将AGV分成两部分，一部分只负责倒箱，一部分只负责搬运。考虑到目标箱和相应阻碍箱都在同一货格，采用第二种方法容易产生冲突，因此，使用第一种策略。

为此，将AGV路径规划抽象成一个车辆路径问题(vehicle routing problem, VRP):给多个任务(包含倒箱和搬运目标箱)安排AGV,每个任务必须且只能被完成一次。AGV完成任务的时间分解成4部分：①从当前位置移动到目标箱顶层的空驶时间，由AGV路径规划确定；②倒箱时间，由阻碍箱数目及各自落箱位确定；③目标箱直提时间，由目标箱纵向坐标确定；④水平搬运至工作台时间，由AGV路径规划确定。

基于以上假设，可建立AGV路径规划双层优化模型，内层模型求解指定任务的倒箱时间，以此为基础，利用外层模型对多AGV路径规划问题进行分析。

倒箱路径优化问题可以转化成单AGV路径规划问题：调用AGV依次搬运阻碍箱，需确定落箱位，优化目标为完成时间最短。且为了与外层路径规划模型相匹配，在内层模型中，AGV初始位置和终点位置均为目标箱货格顶层。

对于任一阻碍箱i∈E,其落箱位包含两方面的信息：一是水平坐标，表示AGV要搬运至何处；二是纵向坐标，表示放入位置的深度。在求解落箱位前，先确定倒箱规则。

规则1 落箱位选择范围确定。为避免阻碍箱落在订单内其他目标箱上造成重复倒箱，需先行确定落箱位水平坐标范围。

设目标箱水平坐标为(x0,y0),除此之外所有货格平面坐标集合为GSW。但在GSW中，并不是每个货格都能作为落箱位使用，得排除掉以下两种情况：

①已存满料箱的货格，设货架中满载的货格水平坐标集合为FS。②同批次订单内其他目标箱所在货格，设目标箱所在货格水平集合为NS。以上两个集合可以通过判断货架存储状态确定。设可储存平面坐标集合为ASW,则有ASW=GSW-(GSW∩FS)-(GSW∩NS)。

规则2 落箱位满足堆放约束。阻碍箱的落箱位必须为空，且当落箱位置不在第一层时，其下方相邻箱位不为空。对箱位集合M中的箱位si,坐标为si(xi,yi,zi)。用θ(si)表示位置si的当前状态，若有箱，则θ(si)=1,否则=0。

对阻碍箱j,设落箱位集合为Dj,结合规则1,则有Dj={si|θ[si(xi,yi,zi)]=0,(xi,yi)∈ASW,zi=1或θ[s(xi,yi,zi)]=0,θ[si(xi,yi,zi-1)]=1, (xi,yi)∈ASW,zi≥2,si∈M。

根据1.2节所述集合，任取目标箱i∈N(N为所有目标箱集合),其箱位坐标为(xi,yi,zi),相应阻碍箱集合为Ei;任取j∈Ei,有落箱位集合Dj,满足式(1);对k∈Dj,设(Xk,Yk,Zk)为决策变量；为使得阻碍箱j的倒箱时间SDj最小，建立最小化AGV水平行驶和提升时间之和的优化目标，可表示为

SDj=min{(|Xk-xi|+|Yk-yi|)th+|Zk-zi|tv}, ∀k∈Dj(1)

式(1)中： th、tv分别为AGV水平行驶单位距离时间和垂直提升单位距离时间。

对i∈N,其上部所有阻碍箱倒箱时间Sdi,可表示为

Sdi=∑j∈EiSDj, ∀i∈NSid=∑j∈EiSjD, ∀i∈Ν (2)

外层模型以内层模型为基础，并满足以下假设：①考虑单一工作台；②初始仓库堆存状态已知，不考虑缺货无法满足订单需求的情况；③所有AGV匀速行驶，且不考虑重量影响；④对某一目标箱，阻碍箱倒箱和目标箱提取由同一个AGV完成，每AGV每次最多搬运一个料箱。

设N={1,2,…,n}为所有目标箱集合；设虚拟任务点集合A={0,1,2,…,n},0表示AGV初始化位置；K={1,2,…,m}为所有AGV集合；工作台坐标为(Work_X0, Work_Y0, Work_Z0)。

对目标箱i∈N,Si为目标箱i所需服务的总时间，由以下3部分组成：倒箱时间Sdi;从存储箱位提升到货架顶层的时间Sti;从货架顶层移动到工作台所需时间Sgi。

对小车k∈K,(AGV_Xk,AGV_Yk,AGV_Zk)为初始位置坐标，Tkijijk为AGV从目标箱i货格顶层移动到目标箱j货格顶层所需时间。

决策变量可表示为Xkijijk∈{0,1},∀k∈K,∀i∈A,∀j∈A时，表示小车k与目标箱的服务关系，若小车k服务完目标箱i后服务目标箱j,取值为1,否则为0;Zkiik∈{0,1},∀k∈K,∀i∈A,表示小车k与目标箱i的服务关系，若目标箱i被小车k运送，取值1,否则为0。

为保证出库作业快速完成，以最小化AGV最长作业时间为目标，包括前往目标箱的空驶时间与服务于目标箱的工作时间，目标函数的表达式为

与目标箱服务时间相关约束为

Si=Sdi+Sti+Sgi, ∀i∈N(4)

Sti=|(zmax+1)-zi|tv, ∀i∈N(5)

Sgi=(|xi-Work_X0|+|yi-Work_Y0|)th,∀i∈N(6)

式(5)为目标箱i所需服务时间Si计算方法，其中Sdi、Sti、Sgi求解分别如式(2)、式(5)、式(6)。

与AGV任务指派相关约束为

∑k∈K∑j∈A,j≠iXkij=1, ∀i∈N∑k∈Κ∑j∈A,j≠iXijk=1, ∀i∈Ν (7)

∑k∈K∑i∈A,i≠jXkij=1, ∀j∈N∑k∈Κ∑i∈A,i≠jXijk=1, ∀j∈Ν (8)

Zki=∑j∈A,j≠iXkji, ∀k∈KΖik=∑j∈A,j≠iXjik, ∀k∈Κ; ∀i∈A(9)

式(7)、式(8)表示每个目标箱都会被访问唯一一次，式(9)表示若小车k从目标箱j到目标箱i,则目标箱i被小车k服务。

与AGV空驶相关约束为

Tkijijk=(|xi-xj|+|yi-yj|)th, ∀k∈K;∀i∈N,∀j∈N(10)

Tk0j0jk=(|AGV_Xk-xj|+|AGV_Yk-yj|)th,∀k∈K,∀j∈N(11)

Tki0i0k=(|xj-AGV_Xk+|yj-AGV_Yk|)th,∀k∈K,∀i∈N (12)

∑j∈NXk0j=1, ∀k∈K∑j∈ΝX0jk=1, ∀k∈Κ (13)

∑j∈NXkj0=1, ∀k∈K∑j∈ΝXj0k=1, ∀k∈Κ (14)

式中：Tkijijk为小车从目标箱i顶层移动到目标箱j顶层需要的时间，等于货架之间的折线距离乘以小车行驶单位距离时间；Tk0j0jk为小车从初始停靠点到目标箱j顶层所需的时间；Tki0i0k为小车从目标箱i顶层返回初始停靠点所需的时间；Xkojojk、Xkj0j0k分别为小车从初始停靠点出发、最终返回初始停靠点。

根据魔方型仓储结构及优化模型的特点，算法需解决以下5个核心问题。

通过三维栅格法建成货架结构后，可根据实际情况依次设定存有料箱的箱位。但为了提高算法适用性，能多次重复进行不同规模的试验，建立仓储状态随机生成子系统，主要步骤为：①确定需生成的存储比例；②在所有空余箱位中，随机生成一个料箱；③判断该料箱是否满足堆存规则，即除了在第一层，下层不能为空，满足则留下该料箱，否则删除；④重复②,直到料箱数量/总箱位数达到要求的存储比例。

倒箱和移箱不仅会使得相应箱位状态发生变化，更会影响随后的决策。建立一个箱位状态数据库，在提取和存入等关键节点及时更新。路径寻优过程中，均在当前箱位状态下进行。

多AGV同时作业属于多线程并行问题。在已有多AGV路径规划研究中，该问题的求解一般分为两步：首先不考虑时间线，将多AGV依次分配给多个任务，得到数条初始规划路径；其次，考虑每段路径的起止时间约束，将所有路径安排在同一时间轴上，得到可执行路径。在所研究的AGV路径规划问题，除了将目标箱搬运至工作台外，还需要接受入库指令，入库指令的时间取决于工作台的服务状态，无法通过计算式直接求解。因此，采用仿真模拟的思想，在路径规划时就引入时间线，建立AGV实时并行系统，一步生成路径方案。

多AGV多任务指派的核心在于确定目标箱提取顺序和AGV调用策略。考虑到同波次订单已经在目标箱生成中被打乱顺序，按到达时间顺序提取意义不大。在魔方型仓储中，压箱会造成过多的倒箱，因此，设定提取原则为：目标箱提取顺序与其阻碍箱数目成反比，当阻碍箱数目一致时，越靠近货架底层的越先提取，以减少后期被压箱的可能性。

确定目标箱提取顺序后，依次将任务安排给AGV。AGV安排策略有两种，先完成先分配和轮流分配。先完成先分配能减少在货格顶层移动的AGV数目，减少冲突，因此采用此策略。

将某个目标箱任务指派给某AGV后，该AGV的路径生成可以分解成3个阶段：①从接收到指令时的当前位置移动到目标箱顶层，用最短折线路线法生成行驶路径；②倒箱路径生成，首先根据倒箱路径优化模型求得最优落箱位，其次采用最短折线路线法生成倒箱路径；③将目标箱提升到顶层后，通过最短折线路线法生成到工作台的路径。

采用Python语言编写算法程序。算法从结构上可以分为内外两层，两层互相嵌套互相影响。外层求解多AGV指派多个任务问题，需要建立两个列表，待执行任务列表和空闲AGV列表，从任务列表中依次提取目标箱，将其分配给AGV列表中的小车，过程中需满足上节所述任务安排及AGV调用策略。外层主要结构如图2所示。

外层结构中的单AGV路径规划方案需调用内层算法求解。内层算法的已知条件为将小车I配置给了目标箱i,目标箱位置为(x,y,z),包括4个步骤：①确定阻碍箱列表；②确定有效空位列表；③依次将所有阻碍箱搬运至最优空位；④搬运小车至工作台。内层算法结构图如图3所示。

AutoStore系统中，仓储规模、存储率、AGV数目、目标箱数目4个参数会直接影响AGV路径寻优的结果。先通过一典型工况对算法的有效性进行分析；再对不同参数取值进行对比，以分析算法的效率及适应性。

设典型工况基本参数为：仓库规模为10×10×10;仓储率为75%;AGV数目为5台；随机生成20个目标箱位；同时AGV水平行驶速度为3格/s, 垂直提升速度为2格/s。算法随机生成的仓储系统如图4所示。

通过嵌套式启发式算法进行求解，可得到每个AGV的任务分配方案及行走路径。首先以2号AGV为例，进行路径分析。图5中，目标箱位置为(10,2,8),上面有一个障碍箱(10,2,9),小车的当前位置在(4,1,11)。小车的路径一共分为以下5步：①从当前位置水平移至目标箱货格顶层(10,2,11);②伸缩臂伸入货格提取障碍箱至顶层；③通过倒箱路径寻优模型，找到最近的倒箱位置(8,2,10),将障碍箱放入；④返回至目标箱顶层；⑤将目标箱搬运至工作台(10,10,11)。

所有AGV路径方案统计如表1所示。AGV遵循轮流分配策略，每台车服务的目标箱数目均为4台，总服务时间差别不大。倒箱服务存在大量的往返操作，因此，各AGV空载和负载时间也相差不大。对此工况，算法求解效率较高，仅为0.12 s。

AutoStore系统一般布置在室内，考虑到空间高度，一般层数为10～20层。为使研究更为普遍性，仓储规模为10×10×10、15×15×15、20×20×20,仓储率为75%,5台AGV,20个目标箱工况下，统计AGV作业时间和运算效率，如表2所示。仓储规模增大后，目标箱分散度增加，单AGV和所有AGV作业时间大幅度增加。运算时间也大幅度增加，但绝对值不高。

对4.1节工况增加AGV数，即仓储规模10×10×10,存储率75%,20个目标箱对应计算结果如表3所示。AGV数量翻倍后，单个AGV分配的目标箱只有原来的1/2,因此作业时间也相应减少。相应的，等待AGV的时间也有所减少，使得总作业时间减少。求解效率影响不大。

仓储率会影响倒箱位置和垂直提升距离，在仓储规模为15×15×15,5台AGV,20个目标箱，仓储率分别为50%,75%,90%工况下计算结果如表4所示。当仓储率发生变化时，受目标箱位置随机分布的影响，最长AGV作业时间变化不明显。总作业时间随着仓储率增加而增加，通过分析具体路径发现，当仓储率高时，阻碍箱数目增加，倒箱次数增多。运算效率随仓储率提高而提高，主要是因为当仓储率较高时，落箱位的选择性变少，更容易找到倒箱位置。

在仓储规模为20×20×20,仓储率为75%,5台AGV的工况下，计算对比结果如表5所示。随着目标箱增多，单个AGV服务时间增加，总时间增加，呈较明显的正相关关系。考虑到目标箱生成的随机性，运算效率变化规律在此不明显，但绝对值都不高。 表5 目标箱变化下AGV方案及求解效率对比

(1)AGV双层路径规划模型能将倒箱路径寻优与多AGV任务分配及寻优进行结合，符合AutoStore系统的工作特性，算例中的AGV路径方案也证明了在三维空间探索的有效性。

(2)根据模型特点给出了嵌套式启发式算法，通过Python编写算法程序，重点解决了仓储状态随机生成子系统、箱位状态数据库系统、多AGV并行系统、AGV任务分配系统及路径生成系统等核心问题。

(3)不同工况的算例结果表明：仓储规模增大后，目标箱分散度增加，AGV作业时间大幅度增加；AGV数量和作业时间负相关；仓储率提高会增加倒箱几率，增加作业时间；目标箱数目变化与AGV作业时间正相关。在求解效率方面，主要受目标箱随机生成位置和仓储率影响，但绝对值也仅在10秒左右。

(4)需说明的是，仅研究了将目标箱移动至工作台这一阶段，在下一步工作中，会与目标箱返回相结合。同时因货格顶层行走路径较多，未特意设置冲突解决策略。在实际求解中，当两车需同时占用一个节点时，随机选取其一为优先级高的车，让其先行，另外一辆车等待即可。