某型自动化立体仓库储位优化算法研究

陈俭新，黄予洛，宁蒙，李冠峰

郑州机电工程研究所，河南 郑州 450015

0 引 言

随着物流行业的发展，自动化立体仓库正在逐步取代传统仓库成为物资存放的主要形式。自动化立体仓库储位优化问题是物资仓储领域研究的热点之一。朱杰等[1]从货物出入库时间、同组货品距离以及货架重心等方面建立自动化存取系统货位分配优化模型，比较了改进遗传模拟退火算法、标准粒子群算法、人工鱼群算法的优化求解效果；冯爱兰等[2]从减少订单分批和最小化作业时间两方面建立了自动化立体仓库货位分配优化模型；张贵军等[3]以货架重心低、出入库频率高、货物离出入库口近等为原则建立了货位分配模型，使用基于精英多策略的方法优化货位分配；陈月婷等[4]考虑货架的稳定性和出入库效率，建立储位优化的数学模型，提出了基于Pareto 最优解的改进粒子群算法（PSO）来解决此问题；焦玉玲等[5]考虑货物出入库作业时间、货架整体等效重心等因素，构建多目标货位分配优化数学模型，提出了多种群遗传算法求解货位分配优化数学模型；Yue 等[6]结合自动化立体仓库应力稳定性和出库效率建立自动化立体仓库优化数学模型，提出了基于改进遗传算法的储位优化算法；邱建东等[7]以自动化立体仓库出库效率建立数学模块，提出了基于周期性病毒遗传算法的储位优化方法；Wu 等[8]结合货架的稳定性和存取货物的效率建立数学模型，通过改进遗传算法实现对自动化立体仓库货位分配的优化；Pan 等[9]结合货架空间利用率和货物拣选效率建立数学模型，通过启发式遗传算法实现对仓库货位分配的优化。以上研究的数学模型基本以运行效率和货架稳定性为目标，并且大多采用遗传算法和模拟退火算法求解。其中遗传算法虽然全局搜索能力强但过早收敛且易陷入局部最优解；模拟退火算法局部搜索能力强，但收敛速度慢。

某型船用多载具自动化立体仓库由平移装置、升降装置、储具和自动化控制设备等组成，是我国自主研发的特种立体仓库，主要用于存储特种物资，为用户提供容积率高、出库便捷的物资存储服务。储位分配优化是实现自动化存取系统高效运作的基础瓶颈问题，该问题类似于广义指派问题[10]，且已被Sahni 等[11]和Feng 等[12]证明为NP 完全（NP-complete）问题。

该型立体仓库系统初始为有序状态，在日常运行过程中，调度员按需随机地对储具进行出入库操作。因此，在使用一段时间后会造成自动化立体仓库储具类型摆放混乱的问题。为保证物资出库效率，同时解决由此引发的立体仓库载荷不均衡等问题，必须在尽可能短的时间内进行立体仓库库位优化操作。

考虑到本系统对储位优化时间的要求，为解决以上问题，本文将使用蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）的储位优化算法求解，并在局部参考模拟退火思想，增加算法局部搜索随机性。该方法通过可以提前预测输入优化步骤在模拟运行的输出值，然后通过蒙特卡洛树搜索算法在等效无滞后的情况下学习控制策略，消除滞后的影响，加快响应速度和收敛速度。

1 问题描述及建模

1.1 问题描述

以某型号船用自动化无人仓库为研究对象，其初始状态如图1 所示。该仓库有3 个横向作业巷道和2 个垂直巷道，出口在仓库左侧，货物统一由仓库左侧出库，在平衡状态下，货物应基于左侧进行类别分配，其布局关于横向巷道作业巷道对称，即对称作业巷道的储位布局完全一致，该仓库为同端出/入布局，即入库口与出库口在巷道的同一侧，货架沿通道排列，平移装置按指令沿通道运行，进行货架上货物的拣选作业。

图1 某型自动化立体仓库初始状态Fig. 1 Initial state of an automated 3D warehouse

库存盘点过程中，算法根据当前库存状态选择储具运行动作，储具运行的目的就是将分布于立体仓库各层的同类型储具进行合并。储位优化过程中，可以通过检查库存状态设置一个暂存区，该暂存区用于存放需要顺序调整的储具，通过不停进行储具周转动作，实现库存的平衡有序。其中，自动化立体仓库按照指令周期模式进行运作，通过平移装置、储具升降装置的配合完成各指令操作。

本文自动化立体仓库有R行C列(R≥3，C≥3)，各行有N(N≤C-2)个储具，存放K种物资，此处K=3。自动化立体仓库动作如表1 和图2 所示。

图2 自动化立体仓库储位移动示意图Fig. 2 Schematic diagram of automatic 3D warehouse slotting position movement

表1 自动化立体仓库动作集合Table 1 The action set of automated 3D warehouse

本文主要研究多平移装置在多储具混乱的情况下，设计合理的储具运行步骤，从库存平衡状态、作业时间等各方面考虑，以最小化指令周期内存取货物的时间距离为目标进行集成优化。

1.2 模型建立

对于自动化立体仓库储位优化问题，首先要达到的目标是同类储具集合存放，且对于三行储具、三类储具的问题，每一行对应各类储具，以保证出库效率；此外，应考虑储位优化耗时最短，储位优化的总时间与采取的储具移动措施、移动次数和路径长度有关，在速度恒定的情况下，移动次数越少，路径长度越短，储具储位优化耗时越短。因此，需要以库存的离散度之和最小及储具储位优化时间最短为目标，建立自动储具储位优化数学模型。

计算储具类内离散度，定义第t次储位优化时第Ki类储具的坐标均值为

第t次储位优化时第Ki类型储具的第j个储具到均值坐标的距离可表示为

式中：dt为 第t次储位优化时所有KI类储具类内离散距离之和；(x)为 第t次货物优化时第Ki类储具行数的坐标均值；(y)为第t次货物优化时第Ki类储具列数的坐标均值。随后，计算类间离散度。全部KI类储具的均值坐标为Mt[x,y]，则

定义所有储具类中心到Ki类储具中心Mt[x,y]的离散度和的值为每类储具的中心[x,y]到Mt[x,y]的距离和，则

式中：Mt(x) 为 水平方向均值坐标值；Mt(y)为垂直方向均值坐标值。由于储具所存货物种类繁多，需要将储存相同类型货物的储具放在一起，并尽量使所有类型储具均匀分散在仓库中并离出库口最近，因此需要使类内离散度尽量小，类间离散度尽量大，并使均值坐标点M离出库口距离最短。

则得到第1 个目标函数库存最小离散度之和minF1为

储位优化是对储位重新调整的过程，储具的重新摆放涉及到储具的搬运。本文主要研究平移装置、左右两侧升降装置运行次数及累加的时间。为节约时间和成本，需要使搬运时间最短。自动化立体仓库移动过程中，平移装置移动时间要快于左右两侧升降装置移动时间。

储位优化单步移动时间分为2 种情况：

1） 循环、集合操作。2 种操作均为储具集合的移动，各储具移动均包括平移装置移动和升降装置移动，平移装置与升降装置并行移动。

2） 出/入暂存区、单个储具换层操作。2 种操作均为单个储具的移动，各储具移动均包括平移装置移动和升降装置移动，平移装置与升降装置串行移动。

因此储具移动总时间分为2种情况。设[xKi j(t-1),[yKij(t-1)]为]第Ki类型储具的第j个储具的当前坐标，xKijt,yKijt为储具移动后的坐标。

1） 循环、集合操作时，储位优化花费时间为

2） 出/入暂存区、单个储具换层操作，储位优化花费时间为

因此，得到第2 个目标函数最短储具储位优化时间 minF2为

式中，Z为储位优化总步数。

最后，由式(7)和式(8)得到储位优化数学模型为

式中：t，i，j，x，y，n为约束条件，均为整数；t=1，2，3，···， 表示储位优化步数，i为储具种类，j为第Ki类储具中某个储具，x为储具水平位置，y为储具垂直位置，n为第Ki类储具总数；1≤i≤KI，1≤j≤n，0＜x＜C，0＜Y＜R，0＜n＜N。

模型中2 个目标函数F1和F2的量纲不一致，需要进行归一化处理。其中F1为 无量纲量，F2的单位为s，所以只需对F2进行归一化处理：

式中： maxF2为系统允许储位优化的最长时间；ε为归一化参数，设置 ε的意义是为了防止在计算过程中出现数值溢出情况，本文取值ε= 0.001。

为了防止多目标模型在求解时相互影响，需要给目标函数添加权重系数ω，以此转化为单目标模型，式( 12) 为变形后的目标函数：

其中使用层次分析法( analytic hierarchy process，AHP) 求解[4]的权重系数为 ω1= 0.647 9， ω2= 0.352 1。

2 基于模拟退火的蒙特卡洛树算法（SA-MCTS）设计

2.1 算法选择

根据表1 可执行动作信息，自动化立体仓库执行储位优化时，每步需考虑28 种可能执行结果，对于3×9 的自动化立体仓库储位优化问题，初始空库实现有序入库需至少27 步，考虑到储具类型数量不平均、布局不均衡等因素，自动化立体仓库储位优化形成路径搜索树至少为 2728，约1.197×1040。因此，自动化立体仓库储位优化步骤搜索空间巨大，对储位优化状态树进行搜索直到终局的方法并不可行，不可能对后续所有情况进行完全统计。

储位分配中选择自动储具进行库存调整的过程可以被视为马尔科夫决策过程（Markov decision process，MDP）[13]，上述章节建立的库存状态和目标函数作为马尔科夫过程的状态和过程参数，来指导储具调度。自动化立体仓库内储位优化马尔科夫决策通过四元组描述为{S，A，P，R}，其中，S为状态集合，A为动作集合，P为状态转移函数，R为效用函数。采用蒙特卡罗树搜索算法，基于强化学习模型Mv和模拟策略π，对于当前要选择动作的状态St，对每一个可能采样的动作a∈A，都进行K轮采样，这样每个动作a都会得到K组经历完整的状态序列。即

对于每个 (St,a)组合，可以基于蒙特卡洛法来计算其动作价值函数并选择最优的动作。

式中，Gt为一个模拟序列的训练得分。式（14）和式（15）为对k个模拟序列采样，创建一个由已经访问过的节点和动作组成的树，并评估树内每个状态动作的价值；构建完成之后，选择当前状态St所能执行动作中Q值最大的节点作为后续动作起点。

MCTS 以当前状态为根节点建立搜索树，通过向前预估可能发生的各种情况，综合选择最好的动作。采用该思想只需求解从当前状态开始的子MDP 过程，无需求解整个MDP 过程，因此MCTS 能够处理状态动作数量较大的马尔科夫问题。目前，以MCTS 搜索算法为代表的强化学习算法已经在电力系统[14]、围棋类游戏[15-16]、计算机视觉[17]、轨迹跟踪预测[18]等方面广泛应用。

2.2 基于SA-MCTS 强化学习

针对自动化立体仓库储位优化问题，提出基于模拟退火的蒙特卡洛树算法(simulated annealing Monte Carlo Tree search，SA-MCTS)的储位优化方法。SA-MCTS 算法源于MCTS，其求解库存盘点问题的总体思路是将库存盘点过程看作一个模拟随机落子过程，其中，以每次储位优化动作作为一次模拟过程，以当前状态得分作为储位优化效果。然后依据数学模型中的约束关系制定规则，以收益最大化为优化目标，整个搜索过程包括选择、扩展、模拟和更新4个阶段[19]。本文通过对MCTS 的选择、模拟、更新步骤进行改进，最终实现自动化立体仓库库存优化目标。

2.2.1 选 择

MCTS 通过树策略选择下一个节点进行扩展，从根节点开始，递归地选择得分最高的子节点或终端状态（游戏胜负或循环时间到）。在MCTS 中遍历树的分数称为树策略，在传统的MCTS 方法中，由上限界限信心（upper confidence bound，UCB）方程给出：

式中：VUCB为 节点的UCB 得分；vi为节点v的第i个子节点；Q为获取节点累计价值的函数；Q(vi)为在v节点处采用i动作获得的总得分；N(vi)为获取节点累计访问次数的函数；Q(vi)/N(vi)为强调对历史动作的利用；N(v)为总模拟次数；c为用于调整加号前后两部分在整体中的比重系数，c越大越偏向于广度搜索，c越小越偏向于深度搜索。

单纯使用MCTS 算法，容易陷入局部最大值，即使在非最优状态，仍然无法跳出局部最优[19-20]。本文通过使用Metropolis 准则，使当前步骤以一定概率接收离散度较差的情况。

选择算法设计如图3 所示，其中，T为退火系数，q为模拟退火降温速度；double为数据类型，rand()为取随机数函数，RAND_MAX为随机数的范围。

图3 选择模块算法图Fig. 3 Algorithm diagram of selection module

2.2.2 扩 展

如果搜索至叶节点SL且该节点遍历次数大于等于P（P为节点扩展临界值）时，应用选择策略后执行分支节点扩展。根据动作a得到状态SCL。此时将状态SCL扩展为树中叶节点且节点初始信息为{N(SL,a)=0，Q(SL,a)=0，N(SCL)=0}。如果下一个要到达的状态为变差状态或相同状态，则进行剪枝操作，并且直接结束本次寻优控制，否则转到模拟阶段。

2.2.3 模 拟

根据表1 中自动化立体仓库可执行动作列表，随机选择某一动作作为模拟策略，模拟过程中需判断，如果模拟结果已经达到库存平衡标准，则停止模拟。结束后，根据式（12）判定胜负，即获得的收益值Vreward，并将其返回。

2.2.4 更 新

当模拟至定义的终止状态时（如终止深度），信息更新从模拟的初始叶节点SL回溯至根节点S0。更新各遍历节点信息：

其中，L(L,0)为叶节点至根节点距离。

通过重复上述MCTS 动作以及不断地拟合、控制，最终蒙特卡洛搜索树将收敛，回溯MCTS动作可以获得储位优化策略。综上所述，梳理基于SA-MCTS 算法的储位优化算法流程，如图4 所示。

图4 基于SA-MCTS 的储位优化算法流程图Fig. 4 SA-MCTS based slotting optimization algorithm flow chart

2.3 SA-MCTS 参数设置

设置自动化立体仓库的库存容量、缓冲区大小、模拟退火参数、蒙特卡洛搜索算法参数、储具类型以及计算机模拟环境等参数。

2.3.1 自动化立体仓库参数设置

1） 自动化立体仓库库存大小为3 行9 列，即该仓库高3 层，每层9 个储位；

2） 自动化立体仓库中有2 个空储位作为缓冲区，该缓冲区可以在储位优化过程中灵活变动，该缓冲区容量设置考虑了储具出入库时间，同时兼顾内部储具；

3） 为使问题简单化，在储具运输过程中不考虑库存半箱及半箱摆放问题，库存包含3 类储具：A 类型储具、B 类型储具、空储具；

4） 平移装置每移一步时间为9 s；

5） 升降装置每移动一层时间为13 s，平移、升降装置时间均根据电机转速及移动距离计算得到。

2.3.2 SA-MCTS 算法参数设置

1） UCB 公式中参数c设置为2，c越大越偏向广度搜索，c越小越偏向深度搜索；

2） MCTS 最 大 运 行 深 度MAX_DEPTH设 置为70，考虑储位优化的时效问题，将搜索最大深度设计为70；

3） MCTS 最大运行模拟次数CHOICES设置为27，对应该自动化立体仓库可运行所有动作集合；

4） MCTS 最大子节点数MAX_CHOICE设置为27，对应该自动化立体仓库可能存在的最多子节点数量；

5） 模拟退火初始温度T0=50 000，该参数参考文献[4]设置；

6） 退火系数Tend= 1×10-8；

7） 模拟退火降温速度q=0.98，实际应用中该参数设置为0.99 或0.98，本文设置为0.98，主要考虑让算法充分寻优。

2.3.3 初始状态和目标状态

初始状态下自动化立体仓库的3 种类型储具随机均匀分布。

目标状态为各行均以3 种类型中的一种储具为队列头部，后续为同类储具，同类储具多于一行的情况下，可以顺序存入其他行。

2.3.4 奖励函数

本文根据自动化立体仓库储具运动， minF1和minF2分别为之前和本次目标函数运算结果，可能存在的收益包括：收益增加、收益不变、收益减少，因此Vreward设计为

2.3.5 计算环境

计算机硬件环境为龙芯3A4000 处理器，内存8 GB；软件环境为中标麒麟桌面版本V5 64 位操作系统。

3 仿真结果及分析

依据上述参数，应用SA-MCTS 算法对自动化立体仓库储位进行优化排列。本文采用随机生成的3 000 组库存数据进行优化算法验证，库存由盘库算法模拟器随机生成，软件界面如图5 所示。图6 所示为储位优化的某一中间状态，其中第2 行储位缺少2 个位置,是由于已有2 个储具A，B 出库（出库储具见图6 左下角），腾出暂存区导致。图7 所示为储位优化完成后的库存状态。

图5 储位优化算法模拟器界面Fig. 5 Slotting optimization algorithm simulator interface

图6 储位优化运行中间结果展示Fig. 6 Display of slotting optimization intermediate result

图7 储位优化结果展示Fig. 7 Display of slotting optimization result

图8 所示为蒙特卡洛搜索树深度与收益值的比较结果，其中每条线为一次训练过程。由图可见，在前期搜索中，随着节点经验信息依次累加，库存离散程度迅速降低；在后期搜索中，随着状态空间不断缩小，树节点越深其收益数值变化越趋平缓，且数据波动越趋收窄。因而说明在储位优化中应用SA-MCTS 能够快速准确地选择最优储位动作决策。

图8 蒙特卡洛搜索树深度与收益值的比较Fig. 8 Comparison of depth and reward value by Monte Carlo search tree algorithm

在SA-MCTS 算法真正有效地进行储位优化之前的所有迭代，都称为训练学习迭代。本文设置训练学习时间为1 000 次“选择-扩展-模拟-反向更新”寻优过程。最后得到从SA-MCTS 控制到储位优化的最佳时间变化曲线，如图9 所示。

图9 收敛次数分布(频次与正态分布图)Fig. 9 Convergence number distribution (frequency and normal distribution map)

由图8 和图9 可知，随着不断尝试储具动作、学习迭代，采用SA-MCTS 算法得到的储位优化时间越来越短，可确定较好的储位优化策略。

为了验证SA-MCTS 算法的储位优化能力，本文设计了基于贪心算法、基于魔方还原算法和传统MCTS 的储位优化算法，并对4 种算法原理进行对比。

1） 基于贪心思想的储位优化算法的主要原理是：设置一定的储位优化步骤，通过在每次优化时，不断尝试换层、储具出/入库、循环等操作，实现同类型储具的聚合，当达到储位优化效果或达到循环次数时输出。

2） 基于魔方还原算法的储位优化算法的主要思想是：首先，设置一定的储位优化步骤数，通过不断的换层、循环操作，实现某一类储具达到一定数量的聚合；随后，设置库内暂存区，同样设置一定的储位优化步骤数，在库内现有库存基础上，尝试进行储具出入暂存区、循环等操作，实现库内同类储具的聚合。

3） 基于传统MCTS 的储位优化算法与本文改进的SA-MCTS 算法的区别在于，SA-MCTS 算法主要包括选择、扩展、模拟、更新4 个算法模块，传统MCTS 的储位优化算法对最优子节点不够随机化，该区别导致传统的MCTS 算法可能无法跳出局部极大值的限制。

基于传统MCTS 算法的储位优化参数设置为每次学习1 000 次，共进行50 轮循环。采用算法模拟器随机生成100 组随机库存样本，储位优化步骤结果取均值，得到采用4 种算法进行储位优化所需运行步数的对比结果（表2）。

表2 各算法储位优化运行步数对比结果Table 2 Comparison on the slotting optimization steps of four algorithms

根据表2 各算法的储位优化对比结果，基于贪心算法的储位优化算法在储具规模较大时，收敛速度较慢，基于魔方还原的储位优化算法优于基于贪心算法和传统MCTS 算法，由于其通过快速换行操作在“种子行”的形成过程中，储具已经达到部分聚合，形成“种子行”后，储具通过较少移动便达到优化效果。SA-MCTS 算法在储具较少时优势并不明显，当储具规模较大后，训练情况更多，能够更好地选择下一个优化步骤，取得了较好的优化效果。

随后，对盘库结果作进一步分析，计算优化后的库存均值和库存方差，这两项数据均为3 层库存数据的平均值。库存均值计算方法为以当前储具为1，后续相同类型则继续累加，不同则继续为1，累加后除以储具数目。通过库存均值和库存方差，能够反映储位优化后库存的整齐程度，其中，库存越整齐，同行同类储具越多均值越大；同行插花少，同类储具多，则方差越小。各算法盘库效果对比如表3 所示。

表3 各算法盘库效果对比Table 3 Comparison on the storage optimization results of four algorithms

最后，对比上述4 种算法的时间复杂度、解出比例、平均计算时间、计算结果的储位优化耗时（以3*9 库存为例）等参数，结果如表4 所示。时间复杂度方面，受内部循环影响，基于MCTS算法的时间复杂度更高。解出比例方面，传统MCTS 算法容易陷入局部最小，某些情况下无法给出对应解。平均计算时间方面，SA-MCTS 算法复杂度高，模拟次数较多，因此平均计算时间较长。储位优化时间方面，贪心算法未使用暂存区，且主要通过双层循环进行同类型储具聚合，在储位优化时，每一次双层循环需要使两层储具按照一定方向全部运行一个储位，是储位优化中最耗时的动作，因此基于贪心算法的优化耗时最高；而基于SA-MCTS 算法得到的优化步数较其他算法更优，整体储位优化耗时更少，比传统的基于魔方还原算法的储位优化耗时优化了30%。

表4 各算法储位优化效果对比Table 4 Comparison on the slotting optimization results of four algorithms

4 结 语

针对某型船自动化仓库储位优化问题，本文设计了一种基于SA-MCTS 的储位优化算法，从问题的描述、数学模型的建立、算法的选择及优化、算法参数的设置等多角度对储位优化算法进行了设计，并与基于贪心算法、基于魔方还原算法、基于传统MCTS 算法的储位优化算法进行了仿真对比实验。结果表明，本文改进的SA-MCTS算法在储位优化时间上优于其他方法，能够推广应用于自动化仓库储位优化步骤求解。

由于自动化仓库库存状态较多，仅采用强化学习应对大规模仓库储位优化难度较大，后续可考虑引入深度学习。通过大规模数据训练深度神经网络，增加对库存状态的识别，随后结合强化学习，进一步优化盘库动作，实现对大规模仓库储位的快速优化求解。