自动化立体仓库调度模型分析及优化

蔡安江，史启程

（西安建筑科技大学 机电工程学院，陕西 西安 710055）

1 引言

自动化立体仓库是当代物流技术，仓储技术、自动化和计算机技术高度集成的产物[1]，衡量其存取效率的标准是单位时间内货物的存取量，为保证整个仓库的性能指标最优，需要对堆垛机路径进行调度，降低存/取货物所需时间，使其能够高效协调运转[2]。

堆垛机调度问题是在仓库模型和出/入库位点确定的前提下，合理安排任务执行顺序，以求得所需时间最短的方案。国内外学者对立体仓库路径优化调度问题进行了大量的研究，文献[3]用遗传算法对仓库调度问题进行研究，该算法很容易陷入“早熟”，对求解的精度有一定影响；文献[4]将模拟退火算法和遗传算法相结合，将每次迭代的结果当作父代种群，两种算法交替进行，实际每次迭代种群进化两次，算法结合方式过于生硬；在上述研究中，均未对同轨双车情况下堆垛机的调度路径模型进行研究，而双车存储效率远高于单车。细菌觅食优化算法（Bacterial ForagingOptimization BFO）是文献[5]于2002年提出的，引起不同领域广泛关注和应用，然而目前将BFO算法应用于自动化立体仓库调度的并不多，该算法针对种群的单一性扩大搜索范围，因此文章通过BFO算法对趋化步长加以改进，使其能够寻优，在搜索过程中具有自适应调节，从而提高收敛速度和仓储效率。

2 问题描述

在生产物流中，传统仓库模型货架纵深过长，导致单台堆垛机运行时间较长，出/入库台或其缓冲区经常处于闲置状态[6]。为缩短出/入库台到货架深处库位点的距离，提高库位缓冲区的利用率，提出一种两端式同轨双车的仓库模型。

同轨双车模式下两端式仓库布局结构图，如图1所示。通过在立体仓库两端各设置一个出/入库台，并在同一巷道上增加一台堆垛机，将货架深处库位点转移至仓库中心位置，缩短堆垛机行进路线，大幅提高存取效率。

针对同轨双车仓库布局模型，当一批存/取任务输入后，同一轨道上两台堆垛机同时工作，完成这批任务所需时间为两台堆垛机完成各自任务后，用时最长的堆垛机的运行时间：

式中：TL，TR—货架左右两端堆垛机完成各自任务的运行时间。

将一条入库任务和一条出库任务组合而成的复合任务，称为DC任务；单独执行一条入库任务或一条出库任务，称为SC任务[7]。组合成DC任务，可以减少堆垛机从出/入库台到库位点的往返次数，因而效率更高。在实际应用中，入库任务数和出库任务数往往不等，基于此，同轨双车模式下，其中任意一台堆垛机运行的时间为

其中，m=min（Npike，Nput），n=max（Npike，Nput）。

式中：TDCi—堆垛机执行第i条DC任务花费的时间；TSCi—堆垛机执行第i条SC任务花费的时间；Npike—出库任务数量；Nput—入库任务数量。

3 出入库调度模型

在同轨双车运行模式下，两堆垛机在同一巷道上同时工作，它们各自的水平位移和垂直位移互不干涉。故其中一台堆垛机完成一次存/取任务所花费的时间为水平、垂直作业所需时间的最大值。设一个货架的长度为l、高度为h，堆垛机水平位移速度为Vx、垂直位移速度为Vy。则其中一台堆垛机以位置［xa，ya］为起点，以位置［xb，yb］为终点，所需时间为：

3.1 任务分配方式

统筹分配原则的目标是在一组出/入库任务分配完成后，两堆垛机完成各自任务的运行时间最短；两堆垛机运行时间差的绝对值最小。数学模型表达如下：

3.2 DC作业方式

同轨双车模式下的DC作业方式为：一批出/入库任务分配给两台堆垛机后，两堆垛机同时工作，各自从出/入库台运载货物运行到入库任务指定库位点，卸载货物后直接运行到出库任务指定库位点装载货物，再将货物运至出/入库台。同轨双车情况下，DC作业方式下堆垛机路径示例，如图2所示。

图2 DC作业方式下堆垛机路径示例图Fig.2 DC Operating Mode Stacker Road Sample Diagram

图中：IO—出/入库台；P1，P3—两堆垛机的入库货位；P2，P4—两堆

垛机的出库货位。

式中：TDC—两台堆垛机完成DC任务的运行时间中较大值。

3.3 SC作业方式

在实际的应用过程中，入库任务数量和出库任务数量并不相同，两堆垛机在执行完组合而成的数条DC任务后，剩下的入库或出库任务即为SC任务。同轨双车情况下，SC作业方式下堆垛机路径示例，如图3所示。

图3 SC作业方式下堆垛机路径示例图Fig.3 SC Operating Mode Stacker Road Sample Diagram

图中：IO—出/入库台；P1—分配给堆垛机的入库货位；P2—分配给堆垛机的出库货位。

只讨论其中一台堆垛机，运行路径为IO→P1→IO，无论是入库任务还是出库任务，运行时间为：

3.4 建立同轨双车模式下调度模型

在实际执行出/入库任务中，一批任务在分配给两台堆垛机后，每台堆垛机获得的出库任务、入库任务的数量可能不一致。因此假设两堆垛机分别获得nL、nR个入库任务与mL、mR个出库任务，取：

根据在同轨双车情况下对DC任务、SC任务的分析，两堆垛机分别有QL2、QR2个DC任务和QL1-QL2、QR1-QR2个SC任务。

基于此，货架两端堆垛机完成各自任务的运行时间为：

因此，完成一批出/入库任务时，堆垛机最优路径模型为：

4 进出库调度优化

利用BFO算法对堆垛机进行路径优化分析，通过四种基元反应操纵，求得同轨双车的最优或近似最优任务序列。

4.1 编码设计

为了方便问题的求解，采用基于任务编号排序的间接编码法[8]将每台堆垛机的出库任务和入库任务分别写成两段编码。

4.2 算法步骤

同轨双车运行模式下，采用统筹分配原则不能保证一次分配的结果为最优，通过在BFO算法中增加调整分配结果的操作，可逐步寻得最优解[9]。细菌觅食优化算法具体步骤如下：

步骤1设定初始参数，包括出/入库任务库位点坐标，初始分子个数，最大反应次数Max-BFO；

步骤2根据统筹分配原则将任务分配给两台堆垛机，产生初代分子；

步骤3：初始化细菌种群个体位置，定义初始化参数Niter、Nc、Ns、Nre、Ned；

步骤4：种群进化代数：n=n+1；

步骤 3：迁移代数：l=l+1；

步骤 4：繁殖行为：k=k+1；

步骤 5：趋化行为：j=j+1；

步骤6：不可行解可能携带若干可行解无法获取的有用信息，如距离全局最优解较近，能够快速获取搜索全局最优解，采用提出的部分不可行解保留策略以提高算法收敛速度；

步骤7：若j≤Nc，则返回步骤5继续趋化操作；

步骤8：种群繁殖，达到临界趋化次数时细菌将完成一个生命周期，并根据健康评价标准进行优胜劣汰，将给定的序号为1到N的N个细菌个体，定义第i个细菌健康程度为：

式中表示种群中每个细菌在趋化过程中完成适应度的累加之和，并对N个细菌健康程度指标按降序进行排列，只保留健康程度较好的部分细菌。

步骤9：若k≤Nre，则返回步骤4继续繁殖操作；

步骤10：迁移操作，为了增强细菌的全局寻优能力，保持规则进行概率迁移，种群内的所有细菌将会按照自身指定的概率迁移到解空间中一个随机位置；

步骤11：若l≤Ned，则返回步骤3继续执行迁移操作；

步骤12：若n≤Niter，则返回步骤2继续种群进化操作；否则输出优化结果。

统筹分配原则的BFO算法流程图，如图4所示。

图4 统筹分配原则的BFO算法流程图Fig.4 Flow Chart of BFO Algorithm of Overall Allocation Principle

通过上述融入统筹分配原则的BFO算法的操作步骤，可以对路径优化问题进行有效的全局搜索[10]，通过分解与合成操作，不易使算法陷入局部最小值。

5 仿真验证

以某企业实际自动化仓库为研究对象，验证数学模型的适应性和BFO算法的有效性。仓库货架位置固定，大小一致，每排货架共840个货位，分为12层，70列，每排货架两端各一个出/入库台，出/入库台坐标分别为［0，1］，［71，1］，用于工业产品的出库运输和入库存储。

在某批出/入库任务中，对应的库位点坐标，如表1所示。提出的细菌觅食算法可以使可搜索的解空间得到扩大的同时，可以有效地引导BFO向最优解靠近，不仅提高求解质量，也提高收敛速度。利用所建立的堆垛机调度模型对上述出/入库任务运用MATLAB进行仿真优化，堆垛机运行所需时间的优化曲线，如图5所示。

表1 出/入库任务坐标Tab.1 Out/In Bound Task Coordinates

图5 堆垛机运行时间优化曲线Fig.5 Optimization Curve of Stacker Running Time

由图5可以看出，堆垛机的运行时间随着算法迭代次数的增加不断减小，于第42代求得最优解。

出/入库任务优化前后，堆垛机运行时间的对比，如表2所示。由表2知，通过优化后堆垛机的调度效率提高了29.5%。在求得堆垛机路径调度最优解后，根据输出的最优解任务序列，其堆垛机运行路径图，如图6所示。

表2 优化前后堆垛机运行时间Tab.2 Stacker Running Time Before and After Optimization

图6堆垛机运行路径图Fig.6 Stacker Running Path Map

图6 中，白色方块为仓库两端出/入库台；黑色方块及实线为SC任务的运行路径；灰色方块及虚线为DC任务的运行路径。可以看出，两台堆垛机各自执行分配所得的出/入库任务，不存在碰撞情况。

结合表2，两堆垛机运行时间差的绝对值为ΔT=2；Right堆垛机先完成任务后，如果执行用时最短的编号为9的出库任务，所需时间为tmin=34.27。满足式（14）的分配原则，故分配结果为最优解。

6 结束语

为提高立体仓库的存储效率，满足物流系统性能要求，研究了在同轨双车情况下，堆垛机的路径优化调度模型。取得以下成果：（1）基于BFO算法邻域搜索能力和跳出局部极小值能力强的特点，对所建立的同轨双车堆垛机调度模型进行优化分析，缩短了堆垛机工作时长，通过优化，堆垛机的调度效率提高了29.5%。（2）结合实际任务进行仿真验证表明，所建立的调度模型对两端为出/入库台的同轨双车调度问题有很好的适应性，采用统筹分配原则可有效避免碰撞和产生无效任务序列，其分配结果是合理、高效的。BFO算法在解决此类问题上是有效可行的。