基于改进防碰撞策略的两端式双堆垛机出入库优化研究

耿赛，王雷，李东东; GENG Sai; WANG Lei; LI Dongdong

2025年4月6日 21:36 星期日

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

摘要

针对大型自动化立体仓库出入库路径优化调度难的问题，在采用两端式双堆垛机出入库调度模型的基础上，提出改进的防碰撞原则，避免两堆垛机同时运行时碰撞；并结合最优防碰撞边界检验机制，在保证防碰撞的前提下，为两堆垛机划分了最佳的工作区域。提出一种新型改进遗传算法（New improved genetic algorithm，NIGA），能够根据种群适应度值的集中分散程度，来调整遗传算法的进化结构，从而有效提高算法的收敛速度以及跳出局部最优的能力。运用NIGA算法对双堆垛机的调度路径进行优化，并在算法的每一次迭代中嵌入改进的防碰撞原则和最优防碰撞边界检验机制，最终得到两端式双堆垛机出入库优化的最优解。仿真实验结果表明该策略可以有效防止两堆垛机发生碰撞，大型立体仓库货物出入库的效率有了明显提高。

关键词

自动化立体仓库; 双堆垛机; 改进防碰撞策略; 改进遗传算法

自动化仓储系统（Automated storage and retrieval system， AS/RS）是一种新型的仓储技术，作为现代物流系统的核心部分，正越来越多地应用于各个行业^［

1‑3］。仓库的出入库效率直接影响到整个物流系统的效率，因此出入库路径的优化就成为提高整个物流系统效率的关键。堆垛机是AS/RS中运输和存取货物的主要设备，其中堆垛机拣选出入库货物的时间占其整个作业周期的50%左右，因此解决堆垛机行驶路径优化问题是提高自动化仓库效率的有效手段^{［参考文献 4

百度学术}4］。

国内外学者对立体化仓库出入库堆垛机路径优化问题做了大量的研究。Liu等^［

5］、李媛媛等^{［参考文献 6

百度学术}6］、杨姣等^{［参考文献 7

百度学术}7］主要针对I/O设在货架同一侧的情况，对堆垛机的不同工作模式建立了相关的数学模型，并分别结合遗传禁忌搜索算法、近似动态规划算法和遗传模拟退火算法对模型进行优化求解，提高了最优解的收敛速度。Emanuele等^{［参考文献 8

百度学术}8］以仓库设计、存储策略和耗能作为重点对堆垛机进行路径优化。Bortolini等^{［参考文献 9

百度学术}9］建立了分析模型来评估堆垛机在单一作业和复合作业中的预期时间。韩东亚等^{［参考文献 10

百度学术}10］以堆垛机出入库的复合作业和任务顺序为研究方向，根据问题的特点设计了两阶段启发式算法求解此问题，有效地提高了仓库拣选效率和堆垛机的作业方式。Lerher^{［参考文献 11

百度学术}11］对跨巷道堆垛机仓储系统进行研究，建立单、双指令情况下堆垛机的行程时间模型，并对时间模型进行性能分析。Torabizadeh等^{［参考文献 12

百度学术}12］和Hao等^{［参考文献 13

百度学术}13］建立新型的模型来研究仓储系统的可持续性可以通过存储策略、堆垛机停顿点策略和出入库调度策略等来有效地提高自动化立体仓库的效率。卞和营等^{［参考文献 14

百度学术}14］提出将I/O分别设在货架两侧，并建立堆垛机的单一、复合作业模型，结合一种改进的遗传算法对模型进行优化求解。上述研究虽然最终取得了不错的货物出入库优化结果，但仅仅局限于算法上的优化，并没有对传统立体化仓库I/O台以及堆垛机的数量和位置布局上提出改良。蔡安江等^{［参考文献 15‑16}15‑16］在码头双堆码起重机调度的构思下，提出两端式I/O同轨双车模式的双堆垛机调度模型，并结合防碰撞原则，用改进的化学反应优化算法进行求解，有效地提高了立体仓库货物出入库的调度效率。虽然该方法避免了两堆垛机在工作时发生碰撞，但防碰撞原则实现方法较繁琐且最终的任务分配也非最优，优化效果仍存在较大改进空间。基于此，本文以两端式双堆垛机模式下的立体仓库为基础，提出改进的防碰撞原则和最优防碰撞边界检验机制，并运用新型改进遗传算法（New improved genetic algorithm，NIGA）进行优化求解，最大限度提高大型立体仓库的出入库调度效率。

1 问题描述

1.1　两端式双堆垛机问题描述

在一般仓库的运输调度中，一般采取单端I/O、单堆垛机的调度模型，通过对单一作业、复合作业出入库任务的优化，来提高调度效率。但随着科学技术的发展，现代企业仓库规模不断扩大，这种传统模式下，仓库的优化效果往往不尽如人意。为了缩短堆垛机的最大工作行程、提高存取货物效率，蔡安江等^［

15］提出两端式双堆垛机模型。图1为两端式双堆垛机立体仓库模型的结构图，在货架两端都设立相同规格的I/O位置，货架之间的巷道上放置了两台规格相同的堆垛机。将堆垛机的最大行驶距离“一分为二”，左右两堆垛机分别负责自己的“工作区域”，极大地缩短了堆垛机的行驶路程，提高了大型仓库的出入库调度效率。

图1 两端式双堆垛机立体仓库模型结构图

Fig.1 Structure diagram of the warehouse model with two‑end double stacker

图1中的堆垛机选用单立柱堆垛机，两堆垛机货叉相向，货叉可以左右伸缩，以便向两侧的货架存取货物。当两堆垛机同时工作时，要保证两堆垛机始终不会发生碰撞。即左端堆垛机处于货架第I列，右端堆垛机处于货架第I+1列存取货物时，此时两堆垛机处于临界安全距离，仍可正常工作不会发生碰撞。

立体仓库两端式双堆垛机的调度模型下，两堆垛机分别从对应的I/O台完成出入库任务的存取，工作时互不干预，仅负责自己工作区的任务。所以完成一批货物存取所需的时间取决于两台堆垛机中耗时更长的一方。

T = m a x (T_{L}, T_{R})

（1）

式中T_L和T_R分别为同一巷道左端堆垛机和右端堆垛机完成各自任务所花费的时间。

堆垛机存取货物的工作方式有两种：（1）堆垛机每次从I/O台出发，仅执行一个出库任务指令或者入库任务指令，称为单一作业（Single operation cycle，SC）；（2）堆垛机从I/O台出发，先执行一个入库任务指令，然后紧接着马上执行出库任务指令，称为复合作业（Double operation cycle，DC）。因为复合作业能够减少堆垛机往返I/O台的次数，提高堆垛机的运行效率，因此优先选用复合作业方式。

若立体仓库为两端式布局，同一巷道上有两台堆垛机负责货物的出入库调度。现仅分析左堆垛机完成所有的单一作业任务，复合作业任务所用的时间为

T = \sum_{i = 1}^{m - n} T_{S C_{i}} + \sum_{j = 1}^{n} T_{D C_{j}}

（2）

式中： $T_{S C_{i}}$ 为左端堆垛机完成第i个SC作业时所运行的时间， $T_{D C_{j}}$ 为左端堆垛机完成第j个DC作业时运行的时间。其中

m = m a x (Q_{1}, Q_{2})

（3）

n = m i n (Q_{1}, Q_{2})

（4）

式中：Q₁为入库货物的数目，Q₂为出库货物的数目。

T_{S C_{i}} = T_{I O_{L} X_{i}} + T_{X_{i} I O_{L}}

（5）

T_{D C_{j}} = T_{I O_{L} X_{j_{1}}} + T_{X_{j_{1}} X_{j_{2}}} + T_{X_{j_{2}} I O_{L}}

（6）

式中：除 $T_{S C_{i}}$ 和 $T_{D C_{j}}$ 外，T表示堆垛机从一个货位到另一个货位所用时间；IO_L为左侧出/入库台；X_i为堆垛机执行第i个单一任务时，出库/入库货位的位置； $X_{j_{1}}$ 、 $X_{j_{2}}$ 分别为堆垛机执行第j个复合作业时，入库货位的位置和出库货位的位置。

式（2~6）仅分析了左端堆垛机存取货物的工作模型，右端堆垛机同理。当仓库接收到一批出入库混合任务指令时，需要两堆垛机协同工作拣取完所有的货物。因此要根据实际的工作情况，将一批出入库货物合理地分配给两堆垛机，在保证两堆垛机同时运行无碰撞的前提下，取得最优的调度效率。

因此，针对两堆垛机运行时无碰撞和任务分配最优两个关键问题，本文提出了改进防碰撞原则以及最优防碰撞边界检验机制，并运用NIGA算法对包含SC、DC两种工作模式的立体仓库双堆垛机模型进行出入库调度优化。

1.2　相关参数的基本假设

对于本文中的两端式双堆垛机立体仓库模型布局，为了研究更具有普遍性以及实用价值，参考文献［

9］中的相关参数，现假设堆垛机作业时匀速运行，加速和制动时间忽略不计，不考虑货叉存取货物时间，设货位的长度和高度分别为 l 和 h。根据上述假定参数可知，堆垛机从货位（x₁，y₁）到货位（x₂，y₂）的运行时间为

t = m a x (\frac{|x_{2} - x_{1}| l}{V_{x}}, \frac{|y_{2} - y_{1}| h}{V_{y}})

（7）

2 出入库调度模型

两端式双堆垛机出入库调度模式下，首要问题就是避免两堆垛机执行任务时发生碰撞以及合理分配左、右两堆垛机执行任务。因此本节首先提出了改进的防碰撞原则，并以此为约束条件，建立相关的双堆垛机调度模型，最后嵌入最优防碰撞边界检验机制。

2.1　改进的防碰撞原则

当接收到一批出入库货物混合订单时，把出库货物、入库货物对应货位的横坐标提取出来构成集合U。为了防止两端堆垛机在拣选、存放货物时发生碰撞，将这批货物分为两组，各组任务对应货位的横坐标分别构成集合Ｌ＝｛ $x_{i_{1}}$ ， $x_{i_{2}}$ ，…， $x_{i_{l}}$ ｝和R＝｛ $x_{j_{1}}$ ， $x_{j_{2}}$ ，…， $x_{j_{r}}$ ｝，在保证集合Ｌ中各元素均小于集合R中各元素外，为了方便后续优化算法的操作，将集合L和集合R中的货物横坐标元素 $x_{i_{1}}$ ， $x_{i_{2}}$ ，…， $x_{i_{l}}$ 以及 $x_{j_{1}}$ ， $x_{j_{2}}$ ，…， $x_{j_{r}}$ 按从小到大的顺序依次排列。集合L中元素对应的出/入库任务交由左端堆垛机执行，集合R中元素对应的出/入库任务交由右端堆垛机执行。以此来划分两台堆垛机的工作区域，使左端堆垛机执行的出/入库任务对应货位的横坐标均小于右端堆垛机执行出/入库任务对应货位的横坐标，从而实现左右堆垛机在相同巷道同时作业时不会发生碰撞干预现象。

改进的防碰撞原则数学表达式为

U = L ⋃ R

（8）

s.t.

\{\begin{array}{l} \forall {x_{i}}_{k} \leq {x_{i}}_{(k + 1)} \\ \forall {x_{j}}_{k} \leq {x_{j}}_{(k + 1)} \\ \forall x_{i} < x_{j} \end{array}

（9）

x_{i} \in L, i = 1,2, \dots, l

（10）

x_{j} \in R, j = 1,2, \dots, r

（11）

采用式（8，9）表示的改进的防碰撞原则，可将左、右两堆垛机负责执行的出/入库货物，根据其所处货位的列坐标从左往右按大小排列，划分为没有重叠部分的左、右两工作区域。

2.2　双堆垛机调度模型

虽然该调度模型下堆垛机型号完全一致，但是左、右堆垛机被分配的出库任务、入库任务的数目可能完全不同。假设左侧堆垛机需要执行n₁个入库任务，m₁个出库任务，右侧堆垛机需要执行n₂个入库任务，m₂个出库任务，取

\{\begin{array}{l} Q_{1} = m i n (n_{1}, m_{1}) \\ Q_{2} = m a x (n_{1}, m_{1}) \\ P_{1} = m i n (n_{2}, m_{2}) \\ P_{2} = m a x (n_{2}, m_{2}) \end{array}

（12）

由式（12）可知，两端式双堆垛机模式下，左侧堆垛机要执行Q₁个DC作业和Q₂-Q₁个SC作业，右侧堆垛机要执行P₁个DC作业和P₂-P₁个SC作业，结合式（2~6），参考文献［

10］的相关内容，可得左、右两侧堆垛机完成各自任务所运行的总时间为

T_{L} = \sum_{i = 1}^{Q_{2} - Q_{1}} (T_{I O_{L} X_{i_{1}}} + T_{X_{i_{1}} I O_{L}}) + \sum_{j = 1}^{Q_{1}} (T_{I O_{L} X_{j_{1}}} + T_{X_{j_{1}} X_{j_{2}}} + T_{X_{j_{2}} I O_{L}})

（13）

T_{R} = \sum_{i = 1}^{P_{2} - P_{1}} (T_{I O_{R} X_{i_{1}}} + T_{X_{i_{1}} I O_{R}}) + \sum_{j = 1}^{P_{1}} (T_{I O_{R} X_{j_{1}}} + T_{X_{j_{1}} X_{j_{2}}} + T_{X_{j_{2}} I O_{R}})

（14）

式中：T_L为左侧堆垛机完成任务所用的时间；T_R为右侧堆垛机完成任务所用的时间；IO_R为右端货物出/入库台。

两端式双堆垛机模式下，堆垛机运输完一批出入库任务的总时间应该取决于两堆垛机中耗时较长的一方，综上所述，两堆垛机完成一批出/入库货物订单的总时间如式（1）所示。则两端式双堆垛机模式下完成这批出入库作业，双堆垛机的最优路径模型为

g (T) = m i n (T)

（15）

2.3　最优防碰撞边界检验机制

虽然上述改进的防碰撞原则可以将货架分为左、右工作区域，避免了两堆垛机在执行各自任务时发生碰撞。但如果左右区域划分不当，就会出现两堆垛机工作量差异较大的状况，导致任务量较少的堆垛机过早地完成任务，而任务量较大的堆垛机仍要“加班”工作的情况，极大降低了堆垛机的利用效率，与本文提出的双堆垛机提高货物出入库效率的想法相悖。于是为了解决这个问题，在改进的防碰撞原则的基础上，提出最优防碰撞边界检验机制。

最优防碰撞边界检验机制判断依据如下：根据改进的防碰撞原则得到左、右工作区分界线e；左、右堆垛机执行完各自分配任务所运行的时间T_L、T_R。

（1）当T_L≥T_R时，左、右工作区分界线左移取e左边较小元素，e_new=U（i-1），将［e_new，e］区间内横坐标对应的任务从左堆垛机负责的任务集合L中删去添加进右端堆垛机负责的集合R中，重新计算任务更新后，左、右堆垛机执行各自任务的运行时间T_Lnew，T_Rnew。比较两者大小：

①当T_Lnew≤T_Rnew时，此时分界线e_new必为最优的防碰撞边界线。因为工作总时间T =max（T_L，T_R），所以比较T_L与T_Rnew大小，若T_L≥T_Rnew则保留最新的出入库任务分配结果，记录最优解T_best = T_Rnew；反之保留原出入库任务分配结果，记录最优解T_best=T_L。

②当T_Lnew>T_Rnew时，令T_L=T_Lnew，更新左、右堆垛机出入库任务分配结果，边界e_new继续左移取U中最近的较小元素……按上述规则继续循环判断，直至T_Lnew≤T_Rnew时，比较T_L与T_Rnew大小，若T_L≥T_Rnew则保留最新的出入库任务分配结果，记录最优解T_best = T_Rnew；反之保留原出入库任务分配结果，记录最优解T_best=T_L。

（2）当T_L<T_R时，左、右工作区分界线右移取e右边较大元素，e_new=U（i+1），将［e，e_new］区间内横坐标对应的任务从右堆垛机负责的任务集合R中删去添加进左端堆垛机负责的集合L中，重新计算任务更新后，左、右堆垛机执行各自任务的运行时间T_Lnew，T_Rnew。比较两者大小：

①当T_Lnew≥T_Rnew时，此时分界线e_new必为最优的防碰撞边界线。比较T_L与T_Rnew大小，若T_R≥T_Lnew则保留最新的出入库任务分配结果，记录最优解T_best = T_Lnew；反之保留原出入库任务分配结果，记录最优解T_best=T_R。

②当T_Lnew<T_Rnew时，令T_R=T_Rnew，更新左、右两堆垛机出入库任务分配结果，边界e继续右移取U中最近的较大元素……同上述规则继续循环判断，直至T_Lnew≥T_Rnew时，比较T_R与T_Lnew大小，若T_R≥T_Lnew则保留最新的出入库任务分配结果，记录最优解T_best = T_Lnew；反之保留原出入库任务分配结果，记录最优解T_best=T_R。

针对自动化立体仓库的两端式双堆垛机模式，在采用改进防碰撞原则的基础上，校验通过防碰撞原则得到的左、右工作区的划分界线e是否为最优分界线，从而保证了两堆垛机最优的货位分配，极大地缩短了堆垛机的最大行程，提高了出入库作业的效率。将上述的最优防碰撞边界检验机制嵌入到算法后续优化的每一次迭代中，根据T_L、T_R以及T_Lnew、T_Rnew的大小情况对左、右两堆垛机任务的分配结果进行自适应地调整，最终得到最优的任务分配方案（具体步骤见3.3节）

3 出/入库调度路径的优化

为了解决自动化立体仓库出入库调度优化的多目标、多约束性等问题，通常采用启发式算法进行求解，常用的就是遗传算法。而在遗传算法中，交叉操作和变异操作对遗传算法的优化结果和收敛速度影响颇深，传统遗传算法中先进行交叉操作后进行变异操作，若种群的适应度值比较集中，交叉操作可能导致遗传算法（Genetic algorithm，GA）过早收敛，即使再进行变异操作，算法也很难跳出局部最优，在解决实际问题中，往往很难取到最优值^［

17‑18］。针对传统遗传算法“爬山能力差”，跳出局部最优能力弱的问题，本文提出了一种基于种群适应度疏密程度的不同而自适应调节进化过程的新型改进遗传算法NIGA。

NIGA算法在优化过程中先求出种群个体适应度的最小值f_min、最大值f_max和平均值f_avg，再判断不等式“（f_max-f_avg）/（f_max-f_min）≥1/2”是否成立，若成立则说明当前种群的最大适应度值、平均适应度值的差值与最大适应度值、最小适应度的差值比较接近，且比值比1/2大得越多，则说明此时种群的适应度值越密集，多样性不强，个体之间交叉产生优秀后代的几率不大，且算法容易陷入局部最优解，因此先执行变异操作，能增加算法跳出局部最优的能力，然后再执行交叉操作；若不成立则表明当前种群的最大适应度值、平均适应度值的差值与最大适应度值、最小适应度的差值存在偏差，且比值比1/2小的越多，说明此时的种群的适应度值分布比较分散，种群的基因多样性丰富，个体之间交叉产生优秀后代几率较大，极大地提高了算法收敛效率，因此先执行交叉操作，再执行变异操作。

3.1　编码设计

由于算法优化的目的是找到双堆垛机调度的最优任务执行顺序，高效地安排货物的出入库。若NIGA算法采用二进制编码，则不能直观地描绘出堆垛机拣取货物的路径轨迹，反而会使编码过程变得更加复杂。因此本文NIGA算法采用实数编码，每个实数代表待执行任务的编号。

每台堆垛机接收到的出入库任务指令按照前后顺序（左堆垛机Chrom1、右堆垛机Chrom2）分别编写成两段编码，每段编码中的实数代表着相应任务的序号。第1段编码X=［x₁，x₂，…，x_i，…，x_m］表示堆垛机接收到的入库指令顺序，第2段编码Y=［y₁，y₂，…，y_j，…，y_N］表示堆垛机接收到的出库指令顺序，Chrom=X∪Y=［x₁，x₂，…，x_i，…，x_M，y₁，y₂，…，y_j，…，y_N］，其中M为入库任务的个数，N为出库任务的个数，x_i为第i个入库货物在货架中的坐标位置，y_j为第j个出库货物在货架中的坐标位置。自左往右，从X、Y的第一位开始，对应编号的出入库任务优先组成DC作业，最后落单的出库或入库任务按SC作业执行。例如，在经过防碰撞原则的任务分配后，左端堆垛机可能收到4个入库任务和6个出库任务的指令，随机生成的任务序列为Chrom1=［2，4，1，3，5，2，3，4，6，1］，其中入库任务为X₁=［2，4，1，3］，出库任务Y₁=［5，2，3，4，6，1］，则左侧堆垛机编码Chrom1对应的任务执行顺序是：先执行DC作业：先执行入库任务2，出库任务5；再执行入库任务4，出库任务2；以此类推先执行完DC作业，最后执行落单的出库任务6和出库任务1两个SC作业，右端堆垛机工作模式与其一致。

目标函数为耗时较长一侧堆垛机完成所有任务运行时间的最小值，因此采用个体目标函数的倒数作为适应度函数，定义为

f (i) = \frac{1}{g (T)} i = 1,2, \dots, m

（16）

3.2　算法设计

（1）选择操作

对群体中个体使用轮盘赌选择法进行选择操作，个体被选择的概率与适应度函数值有关，个体适应度值越高，被选中的概率越大，并在选择过程中加入精英保留策略，将上代中最优染色体保留到下一代。每个染色体被选中的概率为

P (i) = \frac{f (i)}{\sum_{j = 1}^{m} f (j)}

（17）

式中：f（i）为第i个染色体的适应度值，m为种群个体的数目。

（2）交叉操作

分别对左、右两堆垛机的出/入库任务序列Chrom1、Chrom2采用两点交叉，将相邻的两染色体分为一组，当每组染色体的随机概率rand≤p_c时，从区间［1，m］随机选取两交叉点，对入库任务序列进行交叉操作，子代1继承父代1交叉点两侧的基因，中间缺失的基因按顺序从父代2的基因中获得；子代2同理获得。从区间［1，n］随机选取两交叉点对出库任务序列进行相同操作。用交叉后的子代染色体代替父代染色体。

（3）变异操作

分别对左、右两堆垛机的出/入库任务序列Chrom1、Chrom2采用位置变异，每组染色体的随机概率rand≤p_m时，从区间［1，m］随机产生两个变异点，对入库任务序列进行变异操作，交换两个变异点位置的基因形成新的染色体，同时从区间［1，n］随机产生两个变异点，对出库任务序列进行相同操作。用变异后的子代染色体代替父代染色体。

3.3　算法步骤

立体仓库出入库调度同轨双车的工作模式下，采用改进的防碰撞原则虽然能有效防止两车干预碰撞，但并不能使第1次得到的货架的左右分界线e为最优分界线，所以在新型改进的自适应遗传算法的每一次优化迭代中插入满足改进防碰撞原则的最优防碰撞边界检测机制，对分界线e进行最优处理，结合算法，最终得到同轨双车调度模型的最优解。

改进的防碰撞原则划分左右两端货区初始任务种群的详细处理步骤如下：

步骤1 由式（7）分别计算出堆垛机从货架左端I/O台到每一指定出/入库货物货位的行驶时间 $t_{1, i}^{L}$ ， $t_{2, i}^{L}$ ， $t_{3, i}^{L}$ ，…， $t_{n, i}^{L}$ （i∈［1，I］），然后计算堆垛机从右端I/O台到达每一指定出/入库货物货位的行驶时间 $t_{1, j}^{R}$ ， $t_{2, j}^{R}$ ， $t_{3, j}^{R}$ ，…， $t_{n, j}^{R}$ （j∈［1，I］）；其中i为每一个出入库货物的货位所在的货架列数，n为出入库货物的总个数，I为货架的货位的最大列数。

步骤2 把出库货物、入库货物对应的货位坐标的横坐标提取出来构成集合U。且按照从小到大的顺序进行排列。设定左右两侧堆垛机工作区域的分界线为e = U（i），i∈［1，n］。工作区域分界线e代表的含义为从第1列到第e列货位的货物为左端堆垛机的工作区域，第e+1列到第I列为右侧堆垛机的工作区域。

步骤3 当e = U（i）时，t^L=sum（ $t_{1, U (1)}^{L}$ ， $t_{2, U (2)}^{L}$ ，…， $t_{i, U (i)}^{L}$ ），i∈［1，n］；

t^R= sum（ $t_{1, U (i + 1)}^{R}$ ， $t_{2, U (i + 2)}^{R}$ ，…， $t_{n - i, U (n)}^{R}$ ），i∈［1，n］。

步骤4 判断t^L≤t^R，若成立，则令i = i+1，e = U（i），i∈［1，n］，转步骤3；否则，执行步骤5。

步骤5 左右两侧堆垛机任务分配完成，获得初始种群工作序列。从第1列到第e列货位为左侧堆垛机的工作区域，此工作区的出/入库货物由左侧堆垛机完成；从第e+1列到I列货位为右侧堆垛机的工作区域，此工作区的出/入库货物由右侧堆垛机完成。

步骤6 将左端堆垛机所分配的出/入库货物的任务序列随机排序，生成若干任务序列；对右端堆垛机所分配的出入库货物的任务序列随机排序，生成相应的任务数列。

满足改进防碰撞原则的最优防碰撞边界检测机制的具体操作如下：

步骤1 把左端堆垛机负责的左侧工作区的出入库任务种群根据式（13）分别计算出它们的个体适应度值 $F_{L 1}$ ， $F_{L 2}$ ，…， $F_{L n_{1}}$ ，把右端堆垛机负责的右侧工作区的出入库任务种群根据式（14）分别计算出他们的个体适应度值 $F_{R 1}$ ， $F_{R 2}$ ，…， $F_{R n_{2}}$ ，其中n₁、n₂分别为左右两端堆垛机负责出入库任务序列的个体个数，然后，定义T_L= min（ $F_{L 1}$ ， $F_{L 2}$ ，…， $F_{L n_{1}}$ ），T_R= min（ $F_{R 1}$ ， $F_{R 2}$ ，…， $F_{R n_{2}}$ ）。

步骤2 判断T_L与T_R的大小。

步骤3 如果T_L≥T_R，工作区分界线e_new=e（i-1），即e取货位坐标的横坐标集合U左侧上一元素，根据新工作区分界线重新调整两堆垛机任务分配后，计算两堆垛机的运行时间T_Lnew，T_Rnew。判断T_Lnew≤T_Rnew，如果成立，记录下T_Rnew，比较T_L与T_Rnew大小，若T_L≤T_Rnew，记录最优解T_best=T_L，左右两堆垛机的任务分配结果不变，若T_L>T_Rnew，记录最优解T_best = T_Rnew，将［e_new，e］区间，原属于左堆垛机任务序列的对应任务删除，添加到右堆垛机的任务序列中；如果不成立，同理循环。

步骤4 如果T_L<T_R，工作区分界线e_new=e =e（i+1），即e取货位坐标的横坐标集合U右侧上一元素，根据新工作区分界线重新调整两堆垛机任务分配后，计算两堆垛机的运行时间T_Lnew、T_Rnew。判断T_Lnew≥T_Rnew，如果成立，记录下T_Lnew，比较T_R与T_Lnew大小，若T_Lnew≥T_R，记录最优解T_best=T_R，左右两堆垛机的任务分配结果不变，若T_Lnew<T_R，记录最优解T_best = T_Lnew，将［e，e_new］区间，原属于右堆垛机任务序列的对应任务删除，添加到左堆垛机的任务序列中；如果不成立，同理循环。

在上述的最优防碰撞边界检测机制操作步骤中，重新划分的左右工作区分界线e_new，仍然约束着如下关系：左侧堆垛机分配任务所处货架的最大横坐标小于右侧堆垛机分配任务所处货架的最小横坐标，所以经过最优防碰撞原则检测机制优化后的左右堆垛机分配的任务依然满足改进的防碰撞原则，能够有效防止两堆垛机在运行时发生碰撞干预的现象。将最优防碰撞原则检测机制在NIGA算法的步骤7中调用，插入到在NIGA的每一次优化迭代中。

嵌入改进防碰撞原则以及最优防碰撞原则检测机制的NIGA算法对立体仓库同轨双车出入库调度优化的具体步骤如下：

步骤1 设定初始参数，包括两端I/O台O₁、O₂的坐标，设置初始种群的规模m、以及NIGA算法的最大迭代次数MAX_iter。

步骤2 调用经过改进的防碰撞原则产生的两个初始分配的种群Chrom1、Chrom2。Chrom1代表左端堆垛机需要负责的工作序列，种群Chrom2代表右端堆垛机需要负责的工作序列。

步骤3 设定初始代数iter=0，若iter<MAX_iter，则令iter =iter+1，根据式（17）计算每个染色体的适应度函数值，并记录此时种群的最小适应度值f_min、最大适应度值f_max和种群的平均适应度值f_avg。否则转步骤8。

步骤4 判断（f_max-f_avg）/（f_max-f_min）≥1/2是否成立，如果成立，则分别对种群Chrom1、Chrom2先进行选择操作，然后进行变异操作，最后进行交叉操作；反之，先对种群进行选择操作，然后进行交叉操作，最后进行变异操作。

步骤5 经过上述步骤，分别记录进化后Chrom1、Chrom2两种群的最优值T_L、T_R。

步骤6 调用最优防碰撞边界检验机制的具体步骤，检验左、右工作区分界线e是否最优，调整左右两堆垛机的任务分配，并记录最优解T_best；转步骤4。

步骤7 迭代结束，输出最优解T_best以及最优解对应的两堆垛机最佳调度序列Chrom1、Chrom2。

嵌入改进防碰撞原则和最优防碰撞边界检验机制的NIGA算法流程图如图2所示。

图2 嵌入改进防碰撞原则的NIGA算法流程图

Fig.2 Flow chart of NIGA algorithm embedded with improved anti-collision principle

改进后的NIGA算法，可以根据种群适应度值的集中分散程度，来调整算法的进化结构，有效地提高了算法跳出局部最优的能力，加快了算法的收敛速度。结合改进防碰撞原则和最优防碰撞边界检验机制后，NIGA算法有效地解决了两堆垛机工作时发生碰撞的问题，并为它们分配了最优的作业区域和任务序列，最终获得了理想的堆垛机任务分配方案。

4 实验仿真及分析

为证明本文所提出改进遗传算法的有效性，现通过一个具体的立体仓库货物出入库实例来进行验证。某企业的自动化立体仓库的一个货架有12层80列，共有960个货位。每个货位的位置固定，且大小相同，每个货位每次最多存储一个货物。货架的两端各分布着一个I/O台，仓库的巷道左右两端分别放置了型号规格完全相同的两堆垛机，两堆垛机在巷道上可以同时工作，且分别为各自负责的I/O台执行货物的出入库作业，货架及两堆垛机的具体信息见表1。

表1 立体仓库规格信息及堆垛机配置信息

Table 1 Specification information of warehouse and configuration information of stacker

部件名称

信息参数

左端I/O台坐标

右端I/O台坐标

货架长l/m

货架宽h/m

货架深度d/m

堆垛机水平方向运行速度v_x/（m·s^-1）

堆垛机垂直方向运行速度v_y/（m·s^-1）

（0，1）

（81，1）

立体仓库内有一批要执行的出入库任务，包含17个入库任务和15个出库任务，任务坐标位置信息如表2所示。

表2 出入库任务坐标

Table 2 Coordinates of storage and retrieval tasks

入库任务		出库任务
编号	坐标	编号	坐标
1	（40，6）	1	（58，11）
2	（74，8）	2	（14，3）
3	（72，7）	3	（50，8）
4	（15，11）	4	（63，9）
5	（34，4）	5	（34，7）
6	（42，1）	6	（12，5）
7	（69，5）	7	（49，9）
8	（58，3）	8	（41，12）
9	（22，10）	9	（32，11）
10	（68，3）	10	（52，3）
11	（31，12）	11	（36，6）
12	（46，11）	12	（45，4）
13	（39，10）	13	（65，11）
14	（20，4）	14	（22，6）
15	（25，2）	15	（36，8）
16	（54，4）
17	（46，7）

为了验证本文算法的可行性以及优越性，以NIGA算法为基准，分别利用GA，自适应遗传算法（Adaptive genetic algorithm，AGA）对上述的一批出入库任务坐标进行优化求解。对初始参数进行设定，初始种群的规模m=100，最大迭代次数MAX_iter=100，p_c=0.6，p_m=0.2。使用matlab2018b对上述立体仓库参数以及出/入库任务信息进行编程实现，分别用NIGA、GA、AGA3种算法对上述所给的出入库货物相关信息进行优化。

由图3可知，NIGA算法和AGA算法随着迭代次数的增加均收敛到了最优解307 s，而NIGA算法在第9代就收敛到最优值，其迭代速度更快，而GA算法则陷入局部最优，在第14代才得到局部最优解328 s，具体比较结果见表3。与GA、AGA算法相比，NIGA算法收敛速度更快，跳出局部最优能力更强，迭代效果更优。

图3 针对表2任务的目标函数进化曲线

Fig.3 Evolution curves of the objective function for tasks in Table 2

表3 3种算法结果对比

Table 3 Comparison results of three algorithms

评价指标

NIGA

AGA

完成任务用时/s

最佳收敛代数

307

328

由NIGA算法对表2的出入库货物序列优化后的最优解输出的左堆垛机调度序列为（3 8 5 4 7 6 2 1 1 7 4 3 5 6 2），右堆垛机调度序列为（4 9 2 3 6 7 5 8 1 3 7 8 1 2 6 4 5）。相应的堆垛机工作路线如图4所示。

图4 针对表2任务得到优化后两堆垛机的行驶路线图

Fig.4 Driving routes of the two stackers after optimization for tasks in Table 2

根据图4可知，通过NIGA算法对表2中的出入库货物信息进行优化，工作区的分界线为e=40，即从货架的第1~40列的出入库货物由左堆垛机负责调度，货架第41~80列货物由右堆垛机负责调度，左右两堆垛机分别在自己的工作区域内工作，不会发生碰撞干预现象。

为了证明嵌入改进防碰撞原则以及最优防碰撞边界检验机制后的NIGA算法能为堆垛机最大程度合理分配任务，使出入库调度结果达到最佳，同文献［

15］的防碰撞原则以及任务分配机制作比较，用本文改进遗传算法对文献［15］中的出入库任务数据进行优化求解。两算法参数调整一致，NIGA算法优化后堆垛机运行时间进化曲线如图5所示，两堆垛机行驶路线图如图6所示。文献［15］中利用改进的化学反应优化（Improved chemical reaction optimization， ICRO）算法求解得到的优化值为312.67 s，两堆垛机的工作区间的分界线为e =39，而利用本文NIGA算法求得的优化值为 251 s，减少了61.67 s，得到的两堆垛机的工作区间的最佳分界线为e =37。

图5 目标函数最优值进化路线图

Fig.5 Evolution curve of the objective function

图6 两堆垛机优化后行驶路径图

Fig.6 Driving routes of the two stackers after optimization

5 结论

针对目前大型企业的自动化立体仓库规模较大，调度难的现象，分析了两端式双堆垛机出入库调度问题，建立了相应的数学模型。在该模型的基础上提出了改进防碰撞策略以及最优防碰撞边界检测机制的解决方法，并提出一种新的改进遗传算法进行优化。对比实验结果表明，该算法能够根据种群适应度值的集中分散情况，从而自适应地调节进化过程中交叉操作、变异操作的先后顺序，加快了算法的收敛速度，提高了算法避免陷入局部最优的能力，并在每次迭代中嵌入改进防碰撞策略以及最优防碰撞边界检测机制，有效地确定了两堆垛机工作区的最佳分界线，避免了堆垛机运行中的碰撞，平衡了两堆垛机的工作时间，有效地解决了大型自动化立体仓库双堆垛机的出入库调度问题。本文对立体仓库的布局仅考虑了两端式I/O台布置，在实际工作中，为了生产调度的方便，I/O台也可能放置在货架中间。另外，本文假设堆垛机的水平和垂直速度是恒定的，堆垛机每次完成任务后都返回至I/O台。因此在今后的工作中，堆垛机的水平、垂直加减速和停靠点的位置选择也是未来研究中有待解决的问题。

参考文献

POLTEN L， EMDE S. Multi-shuttle crane scheduling in automated storage and retrieval systems［J］.European Journal of Operational Research，2022，302（3）：892-908. [百度学术]

徐欢欢.X公司自动化立体仓库出入库调度优化方法研究［D］.上海：上海交通大学，2017. [百度学术]

XU Huanhuan. Research on the optimization method of inbound and outbound scheduling of X company’s automated warehouse［D］. Shanghai： Shanghai Jiaotong University， 2017. [百度学术]

LERHER T， FICKO M， PALI I. Throughput performance analysis of automated vehicle storage and retrieval systems with multiple-tier shuttle vehicles［J］. Applied Mathematical Modelling， 2021， 91：1004-1022. [百度学术]

闫青，鲁建厦，江伟光，等.考虑双端口布局的紧致化仓储系统堆垛机路径优化［J］.上海交通大学学报， 2022， 56（7）： 858-867. [百度学术]

YAN Qing， LU Jiansha， JIANG Weiguang， et al. Path optimization of stacker in compact storage system with dual-port layout［J］. Journal of Shanghai Jiao Tong University， 2022， 56（7）： 858-867. [百度学术]

LIU T， GONG Y， DEKOSTER R B M. Travel time models for split-platform automated storage and retrieval systems［J］. International Journal of Production Economics， 2018， 197： 197-214. [百度学术]

李媛媛，郑孟.自动化立体仓库出入库路径优化研究［J］.物流科技，2019，42（4）： 161-165. [百度学术]

LI Yuanyuan， ZHENG Meng. Research on the optimization of the inbound and outbound path of automated warehouse［J］. Logistics Technology， 2019， 42（4）：161-165. [百度学术]

杨姣，杨旭东，李露莎，等. 基于遗传模拟退火算法的堆垛机路径优化［J］.物流技术，2022，41（8）： 119-123. [百度学术]

YANG Jiao， YANG Xudong， LI Lusha， et al. Path optimization of stacker crane based on genetic simulated annealing algorithm［J］. Logistics Technology， 2022，41（8）： 119-123. [百度学术]

EMANUELE G， VALERIA M， DAVIDE A， et al. Energy evaluation of deep-lane autonomous vehicle storage and retrieval system［J］. Sustainability， 2019，11（14）： 3817-3831. [百度学术]

BORTOLINI M， ACCORSI R， GAMBERI M， et al. Optimal design of AS/RS storage systems with three-clas-based assignment strategy under single and dual command operations［J］. The International Journal of Advanced Manufacturing Technology， 2015， 79： 1747-1759. [百度学术]

韩东亚，陈然，余玉刚，等.自动化立体仓库中出入库任务顺序与出库位置选择集成优化研究［J］.中国管理科学，2020，28（10）： 156-164. [百度学术]

HAN Dongya， CHEN Ran， YU Yugang， et al. Research on the integration and optimization of the sequence of incoming and outgoing tasks and the selection of outgoing locations in automated three-dimensional warehouses［J］. Chinese Management Science， 2020， 28（10）： 156-164. [百度学术]

LERHER T. Aisle changing shuttle carriers in autonomous vehicle storage and retrieval systems［J］. International Journal of Production Research， 2018， 56（11）： 3859-3879. [百度学术]

TORABIZADEH M， YUSOF N M， ARAM M， et al. Identifying sustainable warehouse management system indicators and proposing new weighting method［J］. Journal of Cleaner Production， 2020， 248： 1-11. [百度学术]

HAO J， SHI H， SHI V， et al. Adoption of automatic warehousing systems in logistics firms： A technology-organization-environment framework［J］. Sustainability， 2020， 12（12）：1-14. [百度学术]

卞和营，方彦军.基于改进遗传算法的堆垛机调度路径建模与优化研究［J］.科技通报，2015，31（7）：135-139. [百度学术]

BIAN Heying， FANG Yanjun. Research on modeling and optimization of stacker dispatching path based on improved genetic algorithm［J］. Bulletin of Science and Technology， 2015， 31（7）： 135-139. [百度学术]

蔡安江，蔡曜，郭师虹，等.同轨双车运行模式下的堆垛机调度策略［J］.计算机集成制造系统， 2018， 24（6）： 1483-1493. [百度学术]

CAI Anjiang， CAI Yao， GUO Shihong， et al. Stacker crane scheduling strategy in the same-track dual-car operation mode［J］. Computer Integrated Manufacturing System， 2018， 24（6）： 1483-1493. [百度学术]

蔡安江，蔡曜，郭师虹，等. 两端式同轨双车运行模式的货位分配策略［J］.计算机集成制造系统，2018，24（12）： 1484-1493. [百度学术]

CAI Anjiang， CAI Yao， GUO Shihong， et al. The cargo space allocation strategy of the two-end dual-car operation mode on the same track［J］. Computer Integrated Manufacturing System， 2018， 24（12）：1484-1493. [百度学术]

郭彩杏，郭晓金，柏林江.改进遗传模拟退火算法优化BP算法研究［J］.小型微型计算机系统，2019，40（10）： 2063-2067. [百度学术]

GUO Caixing， GUO Xiaojin， BO Linjiang. Improved genetic simulated annealing algorithm to optimize BP algorithm［J］. Small Microcomputer System， 2019， 40（10）： 2063-2067. [百度学术]

杨从锐，钱谦，王锋，等.改进的自适应遗传算法在函数优化中的应用［J］.计算机应用研究，2018，35（4）：1042-1045. [百度学术]

YANG Congrui， QIAN Qian， WANG Feng， et al. Application of improved adaptive genetic algorithm in function optimization［J］. Application Research of Computers， 2018， 35（4）： 1042-1045. [百度学术]

请使用 Firefox、Chrome、IE10、IE11、360极速模式、搜狗极速模式、QQ极速模式等浏览器，其他浏览器不建议使用!

基于改进防碰撞策略的两端式双堆垛机出入库优化研究 PDF

摘要

关键词

1 问题描述

1.1 两端式双堆垛机问题描述

1.2 相关参数的基本假设

2 出入库调度模型

2.1 改进的防碰撞原则

2.2 双堆垛机调度模型

2.3 最优防碰撞边界检验机制