魔方型智能仓储系统多AGV任务调度及优化

杨春霞 陈航慧 师浩森

摘  要：为探究针对魔方型仓储系统的多AGV调度问题，建立考虑倒箱因素的多AGV调度优化数学模型，设计改进的多层编码的遗传算法，有助于算法跳出局部最优并改善其局部搜索能力。通过设计不同算例，对比优化前后的AGV调度方案，验证改进算法的有效性和可行性，同时，对不同任务规模、AGV规模、仓储填充率、仓储立体规模和仓储平面规模五方面的工况进行探究分析，为魔方型仓储系统运行状况研究提供理论基础。

关键词：魔方型仓储；AGV任务分配；改进遗传算法

中图分类号：F406.5文献标志码：ADOI：10.13714/j.cnki.1002-3100.2024.11.045

Abstract： In order to explore the multi-AGV scheduling problem for the Rubik's cube storage system， establish a multi-AGV scheduling optimization mathematical model considering the factor of the box， and design an improved multi-layer coding genetic algorithm， which is helpful for the algorithm to jump out of the local optimum and improve its local search capability， through designing standard examples， comparing the AGV scheduling scheme before and after optimization， and verifying the effectiveness and feasibility of the improved algorithm. The working conditions are explored and analyzed， which provides a theoretical basis for the research on the operation status of the Rubik's cube storage system.

Key words： Rubik's cube storage; AGV task assignment; improved genetic algorithm

魔方型仓储系统是一种新型密集仓储系统，与传统仓储系统相比，有较大的区别。如图1仿真模型所示，货架整体呈现魔方型结构，每一纵列称之为一个货格，存储单元（白色货箱）依次放置其中；其次，拣选AGV在货架顶部水平移动，通过伸缩装置深入货格抓取货箱。这种模块化结构使得该系统具有存储能力强、拓展性强、自动化程度高等特点，适用于轻载仓储领域。

现阶段魔方型仓储系统主要以Auto Store系统为代表，与AGV调度相关研究主要体现在以下几个方面：王博[1]对Auto Store系统多AGV路径规划策略进行研究与仿真。王晓军等[2]通过双层路径规划将倒箱路径寻优嵌入多AGV多任务路径分配中。李沁[3]重点研究了翻箱策略方面，但该文没有进一步研究翻箱和目标箱调度问题。Xiang T R Kong等[4]提出蜂窝仓储模型，分析蜂窝仓储的形成、操作流程和应用场景，创建其物理仿模型作为进一步评估的试验台。H？覽v？覽s A K[5]对Auto Store的错误数据库进行分析，根据分析结果提出正确的维护措施。Tjeerdsma S[6]利用布局规划、产能规划和生产管理提高Auto Store生产线的性能，提出五种干预措施并通过模拟模型进行评估验证。

现有相关研究中，一部分完全不考虑倒箱因素对所研究问题的影响，另一部分虽然考虑倒箱因素，却只在宏观上提出倒箱策略，倒箱对其所研究问题产生了何种影响以及如何产生影响并没有明确的研究，更没有在考虑倒箱操作下的系统优化问题。

1  问题描述

在对Auto Store密集仓储系统任务调度优化中，拣选AGV每次只能搬运一个料箱。Auto Store系统的任务调度过程包含两个环节：一是把阻碍箱搬走，二是提取目标箱。

倒箱操作是为取出目标箱而将目标箱上方的阻碍箱依次搬走的操作。在探究倒箱作业的具体流程中，主要解决两个问题：一是谁来搬运阻碍箱，二是将阻碍箱放置在何处。本文选择AGV合用的方法来搬运阻碍箱，AGV合用即用同一个AGV进行阻碍箱的搬运和目标箱的提取。

AGV提取目标箱为传统意义上的任务调度，但AGV合用则将倒箱作业也由该AGV完成，即在传统任务调度中加入倒箱操作，需将倒箱作业视为任务调度中的一个环节，将其嵌入任务调度中。

因此，该问题可转为三个子问题：一是选择合适的倒箱策略以确定阻碍箱的落箱位置；二是探究多AGV任务调度数学模型及求解算法；三是探究倒箱作业与任务调度之间的联系，将倒箱作业模型嵌入任务调度模型，对Auto Store系统的运行状况进行分析。

2  多AGV建模

2.1  模型假设

在Auto Store系统拣选作业中，本文规定一个任务的起始时刻为拣选AGV移动到该任务所在存储柱的上方，结束时刻为拣选AGV移动到下一个任务所在存储柱的上方，因此每个任务包含三个阶段，第一阶段为倒箱作业，由拣选AGV在该任务所在存储柱的上方将阻碍箱放置到通过倒箱规则确定的相应落箱位上；第二阶段为出库作业，由拣选AGV将目标箱提取并搬运到工作台；第三阶段为任务间作业，拣选AGV从工作台到下一个任务所在存储柱的上方。

（1）只考虑拣货作业环节；（2）拣选AGV移动速度为匀速，即不考虑重量对AGV速度的影响；（3）每个存储货格均同形且为正方形；（4）设仓库底层左上方的货格为原点坐标1，1，1；（5）仓库堆存状态和货物位置已知；（6）作业台根据就近原则选择，即不考虑作业台的选择；（7）暂不考虑料箱在工作台的拣货时间，即其设为常量。

参数设置：

Z表示Auto Store系统的最大堆存高度；t表示拣选车水平方向移动单位距离所用时间；t表示拣选车垂直方向移动单位距离所用时间；o=X，Y表示第k辆AGV，o所在的初始位置；e=X，Y，Z表示Auto Store系统的作业台所在位置；g=X，Y，Z表示目标箱g即任务i所在的位置，I=1，2，…，i，…，a；a表示AGV任务列表内的商品个数；P表示第k辆AGV完成所有任务并返回初始位置的时间，K=1，2，…，k，…，n；P表示所有AGV完成所有任务并返回初始位置的时间的最大值；T表示第k辆AGV完成任务i所需的时间；T表示第k辆AGV从任务i到任务j走最短折线路径所需时间；T表示第k辆AGV从初始位置到任务i走最短折线路径所需时间；T表示第k辆AGV从任务j到初始位置走最短折线路径所需时间；T表示第k辆AGV任务i中目标箱g上存在b个阻碍箱时的倒箱作业时间；T表示第k辆AGV从任务i到作业台e走最短折线路径所需时间；T表示第k辆AGV从作业台e到达任务j走最短折线路径所需时间；u表示第k辆AGV执行任务i的次序，用于消除子回路。

决策变量：

2.2  目标函数与约束条件

式（1）为任务调度模型的目标函数，表示最小化n辆AGV的最长运行时间；式（2）表示选择运行时间最长的AGV的运行时间；式（3）表示第k辆AGV的总运行时间，分别包含完成任务的时间，任务间转移的时间，以及从初始位置到达第一个任务的时间和从最后一个任务完成到初始位置的时间四部分；式（4）表示第k辆AGV的任务i与任务j之间的运行时间；式（5）表示第k辆AGV从初始位置到达任务j的运行时间；式（6）表示第k辆AGV从任务i回到初始位置的运行时间；式（7）表示第k辆AGV对任务i的完成时间，包含倒箱作业时间，从目标箱到工作台时间，以及从工作台到下一个任务的时间三部分；式（8）表示第k辆AGV从任务i到作业台的运行时间；式（9）表示第k辆AGV从作业台到任务j的运行时间；式（10）、式（11）表示第k辆AGV的起止点约束；式（12）、式（13）、式（14）表示每个任务都被执行且只执行一次；式（15）表示第k辆AGV的线路流量平衡；式（16）表示第k辆AGV的消除子回路约束；式（17）、式（18）均表示决策变量约束。

2.3  倒箱策略

在上式中，T由倒箱策略求出。在本文中，倒箱策略主要有三点：

一是落箱位不能在订单内其他目标箱。

二是落箱位满足堆放约束，阻碍箱的落箱位必须为空，且当落箱位置不在第一层时，其下方相邻箱位不为空。

三是倒箱距离尽量短。倒箱距离为AGV水平行驶单位距离时间和垂直提升单位距离时间之和。

因此，倒箱位搜寻为一个简单的搜索，首先根据规则一、二确定可以选择的落箱位，其次选择行驶距离最短的位置。落箱位确定，既可得到单个阻碍箱倒箱时间。当目标箱上的阻碍箱不止一个时，将所有阻碍箱加起来即可。

3  改进遗传算法

本文提出基于多层编码改进的遗传调度优化算法，在随机生成初始解的基础上加入初始解差异评价因子，提高初始解在解空间分布的均匀性，提高算法收敛速度，加入进化逆转操作以改善其局部搜索能力。

3.1  个体编码生成设计

本文采用的染色体编码方式为整数编码，每个染色体代表每个AGV的任务执行顺序，当任务总数为n时，染色体长度为2*n。其中，染色体前半部分表示任务顺序，随机排列n个任务的顺序；后半部分表示AGV序号，因一个AGV只完成一个任务属于极劣解，所以每个AGV对应的任务个数至少为2个。当n=10时，如图2所示。

图2表示的解为AGV1的任务执行顺序17→16→12→15，AGV2的任务执行顺序4→9→13→19→2，AGV3的任务执行顺序7→5→3→1→20，AGV4的任务执行顺序10→8→18→11→14→6；1～10位为任务顺序，11～20位为AGV序号，且与前10位一一对应。

3.2  遗传操作设计

任务调度模型的目标函数是使任务全部完成的总时间最小，属于最小化问题。本文采取的是多层编码，所以交叉操作和变异操作均需将染色体分层之后再操作。

交叉操作采用整数交叉法，本文仅第一层编码为任务顺序编码，因此，只对第一层进行交叉操作，将染色体前半段的随机生成的两个位置进行交叉操作。如图3所示，交叉位置为7，只对染色体1和染色体2的前半部分即任务部分进行交叉；交叉后的结果可以看出，存在某些任务缺失，如染色体1中缺少的任务7和10，也存在某些任务多余，染色体1中多余的任务6和9，因此，需要将多余的任务改为缺失的任务。

变异操作采取随机选择两个点对换其位置的策略。本文采取多层编码的编码设计，因此需要分层进行变异操作，第一层，随机生成1，10范围内的随机整数R和R，将其所对应位置的任务号对换，如R=4，R=8；第二层的范围则是11，20，操作与第一层相同，如图4所示。

3.3  进化逆转操作设计

为改善遗传算法的局部搜索能力，本文在选择、交叉、变异之后，加入连续多次的进化逆转操作，“逆转”是指将种群中的每一个个体的每一层编码都进行逆转操作，“进化”是指只有逆转之后所得新个体的适应度值提高的会被保留，反之保持原先编码，即逆转无效。