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  某型自动化立体仓库初始状态

Figure  1.  Initial state of an automated 3D warehouse

下载: 全尺寸图片 幻灯片

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

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

表  1  自动化立体仓库动作集合

Table  1.  The action set of automated 3D warehouse

操作	动作描述	可执行动作
储具左换层	储具通过左通道移动至另一层某空储位	任意两层左换层
储具右换层	储具通过右通道移动至另一层某空储位	任意两层右换层
储具入暂存区	储具由当前位置换层入暂存区	非暂存区库口储具入暂存区
储具出暂存区	储具由暂存区换层移出至某储位	暂存区库口储具出至非暂存区
储具顺时针循环	某两行储具整体顺时针移动一位	任意两行储具进行顺时针循环
储具逆时针循环	某两行储具整体逆时针移动一位	任意两行储具进行逆时针循环
储具左集合	某行储具整体向左靠拢	任意一行储具进行左集合移位
储具右集合	某行储具整体向右靠拢	任意一行储具进行右集合移位

下载: 导出CSV 

| 显示表格

图  2  自动化立体仓库储位移动示意图

Figure  2.  Schematic diagram of automatic 3D warehouse slotting position movement

下载: 全尺寸图片 幻灯片

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

1.2   模型建立

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

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

式中： $\overline {{m_{t{K_i}}}} [ {x,y} ]$为第t次货物优化时第${K_i}$类储具的坐标均值；$[ {x,y} ]$为储具行、列值；j为第${K_i}$类型储具的第j个储具；$[ {{x_{t{K_i}_j}},{y_{t{K_i}_j}}} ]$为第t次货物优化时第${K_i}$类第j个储具的行、列坐标；n为第${K_i}$类型储具的总数量。

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

式中：${d_t}$为第ｔ次储位优化时所有${K_I}$类储具类内离散距离之和；$\overline {{m_{t{K_i}}}} \left( x \right)$为第t次货物优化时第${K_i}$类储具行数的坐标均值；$\overline {{m_{t{K_i}}}} \left( y \right)$为第t次货物优化时第${K_i}$类储具列数的坐标均值。随后，计算类间离散度。全部${K_I}$类储具的均值坐标为${M_t}\left[ {x,y} \right]$，则

定义所有储具类中心到K_i类储具中心${M_t}\left[ {x,y} \right]$的离散度和的值为每类储具的中心$\overline {{m_{t{K_i}}}} \left[ {x,y} \right]$到${M_t}\left[ {x,y} \right]$的距离和，则

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

则得到第1个目标函数库存最小离散度之和$\min F_{1}$为

式中，${L}_{t}=\sqrt{{M}_{t}(x)^{2}+{M}_{t}(y)^{2}}$，为均值坐标点${M_t}\left[ {x,y} \right]$到出库口的距离。

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

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

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

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

因此储具移动总时间分为2种情况。设$\left[ {{x_{{K_{ij\left( {t - 1} \right)}}}},{y_{{K_{ij\left( {t - 1} \right)}}}}} \right]$为第K_i类型储具的第j个储具的当前坐标，$\left[ {{x_{{K_{ijt}}}},{y_{{K_{ijt}}}}} \right]$为储具移动后的坐标。

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

式中：r为2行储具；${N_r}$为当前行储具数量；$\left| {{x_{{K_{ijt}}}} - {x_{{K_{ij\left( {t - 1} \right)}}}}} \right|$为储具平行移动距离；η₁为沿水平方向移动一次的时间。

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

式中：$\left| {{y_{{K_{ijt}}}} - {y_{{K_{ij\left( {t - 1} \right)}}}}} \right|$为升降装置的移动距离；${x_{{K_{ijt}}}} + {x_{{K_{ij\left( {t - 1} \right)}}}}$为平移装置的移动距离；η₂为沿垂直方向移动一次的时间。

因此，得到第2个目标函数最短储具储位优化时间$\min F_{2}$为

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

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

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

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

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

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

其中使用层次分析法( analytic hierarchy process，AHP) 求解^[4]的权重系数为${\omega _1}$= 0.647 9，${\omega _2}$= 0.352 1。

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

2.1   算法选择

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

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

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

式中，$G_{t}$为一个模拟序列的训练得分。式（14）和式（15）为对k个模拟序列采样，创建一个由已经访问过的节点和动作组成的树，并评估树内每个状态动作的价值；构建完成之后，选择当前状态${S_t}$所能执行动作中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，其求解库存盘点问题的总体思路是将库存盘点过程看作一个模拟随机落子过程，其中，以每次储位优化动作作为一次模拟过程，以当前状态得分作为储位优化效果。然后依据数学模型中的约束关系制定规则，以收益最大化为优化目标，整个搜索过程包括选择、扩展、模拟和更新４个阶段^[19]。本文通过对MCTS的选择、模拟、更新步骤进行改进，最终实现自动化立体仓库库存优化目标。

2.2.1   选　择

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

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

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

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

图  3  选择模块算法图

Figure  3.  Algorithm diagram of selection module

下载: 全尺寸图片 幻灯片

2.2.2   扩　展

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

2.2.3   模　拟

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

2.2.4   更　新

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

其中，${L_{\left( {L,0} \right)}}$为叶节点至根节点距离。

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

图  4  基于SA-MCTS的储位优化算法流程图

Figure  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） 模拟退火初始温度 T₀=50 000，该参数参考文献[4]设置；

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

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

2.3.3   初始状态和目标状态

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

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

2.3.4   奖励函数

本文根据自动化立体仓库储具运动，${\text{min}}{F_1}$和${\text{min}}{F_2}$分别为之前和本次目标函数运算结果，可能存在的收益包括：收益增加、收益不变、收益减少，因此$V_{\text {reward }}$设计为

2.3.5   计算环境

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

3.   仿真结果及分析

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

图  5  储位优化算法模拟器界面

Figure  5.  Slotting optimization algorithm simulator interface

下载: 全尺寸图片 幻灯片

图  6  储位优化运行中间结果展示

Figure  6.  Display of slotting optimization intermediate result

下载: 全尺寸图片 幻灯片

图  7  储位优化结果展示

Figure  7.  Display of slotting optimization result

下载: 全尺寸图片 幻灯片

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

图  8  蒙特卡洛搜索树深度与收益值的比较

Figure  8.  Comparison of depth and reward value by Monte Carlo search tree algorithm

下载: 全尺寸图片 幻灯片

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

图  9  收敛次数分布(频次与正态分布图)

Figure  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

储具规模	运行步数
	基于贪心 算法	基于魔方 还原算法	普通MCTS 算法	SA-MCTS 算法
3×3	33	31	40	28
3×4	37	33	45	34
3×5	54	40	60	36
3×6	63	53	63	43
3×7	86	62	68	44
3×8	102	70	70	50
3×9	113	75	80	52

下载: 导出CSV 

| 显示表格

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

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

表  3  各算法盘库效果对比

Table  3.  Comparison on the storage optimization results of four algorithms

算法	库存均值			库存方差
	3×7	3×8	3×9	3×7	3×8	3×9
基于贪心算法	2.634	2.722	2.753	0.408	0.461	0.484
基于魔方还原算法	2.603	2.513	2.925	0.4799	0.322	0.468
传统MCTS算法	2.238	2.857	2.095	0.480	0.329	0.480
SA-MCTS算法	2.952	3.428	2.857	0.473	0.247	0.494

下载: 导出CSV 

| 显示表格

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

表  4  各算法储位优化效果对比

Table  4.  Comparison on the slotting optimization results of four algorithms

算法	时间复杂度	解出 比例/%	平均计算 时间/s	优化 耗时/h
基于贪心算法	$O({n^2})$	85	0.931	7.320
基于魔方还原算法	$O({n^2})$	100	0.837	5.250
传统MCTS算法	$O({n^3})$	75	1.275	5.331
SA-MCTS算法	$O({n^3})$	100	1.163	3.664

下载: 导出CSV 

| 显示表格

4.   结　语

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

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