自动化立体仓库中出入库任务顺序与出库位置选择集成优化研究

韩东亚，陈 然，余玉刚，郭晓龙

(中国科学技术大学管理学院，安徽 合肥 230026)

1 引言

近年来，随着电子商务的高速发展，以阿里、京东和苏宁为首的电商企业迅猛崛起，我国的自动仓储系统市场呈现稳步高速增长态势，传统的批量化、单一化产品越来越难以满足消费者的需求。电商物流呈现出订单数目大、海量SKU、订单时效性高、随季节波动性大的特点。传统的自动化立体仓库需要先使用堆垛机取出整托盘货物，然后将整托盘通过传送带送至分拣系统。取货人员按照订单从整托盘中取出所需数量的货物，并将托盘放回至传送带使其入库。托盘在传送带往往花费大量的等待时间，分拣作业效率低下，无法满足电商物流中多品种、小批量的消费需求。

多出库位置的自动化立体仓库(Automated Storage and Retrieval System with Multiple In-the-Aisle Pick Positions, 简称ASRS-MIAPP)是一种新型的仓库技术，能有效地改善上述分拣作业效率低下的问题。与传统的单出入口自动化仓库不同，ASRS-MIAPP在货架底层有多个出库位置，可被视为单入口多出口的仓库系统。ASRS-MIAPP中有两种类型的过道：拣选过道和堆垛机过道。其中拣选过道比堆垛机过道略宽，为取货人员提供移动空间进行货物拣选。ASRS-MIAPP能够有效地将存储和分拣作业集成在一起，既减少了占地面积，提高了空间利用率，减少能量损耗，同时又能减少工人数量，降低人力成本。目前已得到众多国际知名公司，如Publix Super Markets, Wal-Mart, Walkers, Ferrero GmbH等的广泛使用[1]。

在ASRS-MIAPP中，出入库任务的合理调度，对整个系统整体运作起着至关重要的作用。当出入库任务的完成顺序选择较差时，堆垛机运作的距离会变大，既延误了完成下一批任务的时间，也延误了出库货物到达顾客的时间，对企业造成不好的影响。同时，出口货物释放到出口的位置，也会影响到堆垛机完成两个连续任务的运作距离。因此，出入库任务的调度和出库位置的选择，是紧密相连的联合决策问题。然而，随着问题规模的扩大，求解难度急剧上升，如何快速求得最优解或近似最优解至关重要。

目前，针对自动化立体仓库系统运作绩效问题，国内外有很多学者进行了研究。Roodbergen和Vis[2]，Gagliardi等[3]，Boysen和Stephan[4]从不同的角度对现有研究进行了综述分析。Roodbergen和Vis[2]提出可以通过四种控制决策包括存储策略、批处理、堆垛机停顿点策略和出入库调度策略等来有效地提高自动化立体仓库的绩效。Han等[5]指出，自动化立体仓库存取顺序问题类似于旅行商问题。对于动态环境下的存取顺序问题，可以通过两种方法来解决：块调度和动态调度。块调度是指选择一个块，对其中的所有出入库任务进行调度，当此块内的所有作业全部完成后，再进行下一个块调度；而动态调度则是指每次有新的任务加入时对所有任务重新排序，采用截止日期优先的方式，确保不会过度延迟出库任务。Lee和Schaefer[6]研究了一种特殊情况，即系统中的任意空位均可作为存货位置使用，作者首先求解一个线性指派模型，然后使用排序算法求解，此算法在空位数量较小时可以找到系统最优解。在Lee和Schaefer[7]的另一项研究中，根据先来先服务(FCFS)规则操作入库任务，而通过指派问题的算法优化出库任务顺序。Chen等[8]在考虑每个单元负载的停留持续时间的情形下建立混合整数模型，并构造启发式以及禁忌搜索算法解决此问题。Eynan和Rosenblatt[9]提出最近邻域搜索算法并应用于分类存储策略中。Gharehgozli等[10]针对具有两个进出口的自动化立体仓库提出了一种多项式时间的算法解决出入库调度问题。

以上研究均假设堆垛机每次只能存取一个负载单元，与之相反，双梭立体仓库可以一次存(或取)两个负载单元，因此，出入库任务的组合更多更复杂。Keserla和Peters[11]用基于最小周长的优先规则方法解决双梭立体仓库调度问题。Sarker等[12,13]针对类似的问题提出了基于最近邻的简单启发式方法。Yang Peng等[14]则研究多梭立体仓库调度问题，建立了混合整数模型并用可变邻域搜索方法求解。对于类似的问题，一个两阶段禁忌搜索方法和遗传算法结合修改最近邻启发法分别在文献[15]和[16]中给出。目前很少有学者针对ASRS-MIAPP系统进行研究，Ramtin和Pazour[17]在随机存储策略下，建立了堆垛机行走时间模型，分析不同系统尺寸，不同系统构造(单层多出库位置和双层多出库位置)对系统绩效的影响。Ramtin和Pazour[1]考虑了不同需求曲线下货物的存储问题，在假设有无限多的出库位置下，他们建立了连续的数学模型，并与离散事件仿真的结果作对比，发现只有0.1%的差距，验证了此连续模型的有效性。

国内学者也对自动化立体仓库的运作绩效进行了深入的研究。田国会等[18]考虑自动化立体仓库固定货架系统中出入库策略优化问题，提出了一种新的自适应启发式方法，使用最近点搜索算法获得初始种群的解，然后进行逐步迭代，结果表明算法能在较短的时间里获得很好的解。王雯等[19]提出一种基于层次分析法和遗传算法相结合的出入库调度优化算法，并使用仿真的方式验证了算法的有效性。刘韬等[20]采用面向对象的赋时Petri网研究了出入库调度问题，建立了数学模型，并分析了该模型的死锁问题。邓爱民等[21]以医药仓库为例，建立了基于时间的多目标货位优化模型，并使用遗传算法求解模型。李鹏飞和马航[22]以出入库效率和货架稳定性作为优化目标建立数学模型，采取病毒协同遗传算法进行仿真对比，结果显示此算法能够获得较好的解。靳萌等[23]针对军用维修器材仓库，提出了考虑物资周转率和相关性的货位优化模型，并设计了一套基于Pareto保持和模拟退火的算法，验证了此模型的有效性。刘臣奇等[24]构建了货物拣选路径问题的优化模型，提出了改进的蚁群算法，结果显示该算法相较于基本蚁群算法收敛速度显著提高，具有很好的可行性。常发亮等[25]考虑了周转货箱的容量限制，根据自动化仓库货物拣选的特点建立了数学模型，用遗传算法对该模型进行求解，数值结果表明此算法高效可靠。

本文与以上学者研究的区别在于(1)本文研究一个单入口、多出口的自动化立体仓库，因此即需要考虑出入库任务的操作顺序，也要考虑出库任务被分配到哪一个出库位置的问题。而以上学者主要研究单入口单出口的仓储系统，只需要考虑出入库任务的操作顺序既可。(2)目前研究此系统的文献聚焦于系统绩效，以及货物存储策略方面的研究，本文首次研究此系统出入度调度策略问题。

2 出入库调度与出库位置选择集成优化模型

2.1 问题描述

本文的问题可以描述为：在一个多出口位置的自动化立体仓库(如图1所示)中，有一系列货物等待存储，同时还有一系列货物等待取出。堆垛机既可以每次只完成一个入(或出)库任务，也可以每次先完成入库任务，再完成出库任务。

图1 ASRS-MIAPP示意图，左图为左视图，右图为侧视图(引自Ramtin和Pazour[1])

上述堆垛机操作过程中存在以下特点：

(1)入库任务顺序约束：一般来说，需要存放的货物会在传送带上等待堆垛机完成入库任务。由于很难在传送带上改变待存放货物的位置，因此入库任务按照先到先服务的模式进行。

(2)多种出入库路径情形：我们考虑堆垛机的停顿点策略为停留策略，即堆垛机会在完成出库(或入库)任务的位置处停留，等待下一个任务。当完成的任务为入库任务时，堆垛机会停留在完成上架的标准化托盘所在的位置上；当完成的任务为出库任务时，堆垛机会停留在完成出库的标准化托盘所在的出库位置处。因此，堆垛机启动的位置取决于前一个任务。另一方面，堆垛机的作业模式有以下三种：(1)单一入库任务：堆垛机从完成上一个任务的停顿点处空载到入口，将从入口处将要存放的标准化托盘运送到给定存储位置上。(2)单一出库任务：堆垛机从完成上一个任务的停顿点处空载到所需托盘所在位置，从货架上取下并将它运送到某个拣货位置处。(3)复合作业：堆垛机从完成上一个任务的停顿点处空载到入口，将要存放的标准化托盘运送到给定存储位置上，空载到需要取出的托盘所在位置，从货架上取下并将它运送到某个拣货位置处。考虑到停顿点和堆垛机作业模式之间的组合，堆垛机会根据出入库任务顺序和出库位置选择按照相应的路径移动。如图2所示，堆垛机一共有6种可能的路径移动：(a) 停顿点在货架上的单一入库任务；(b) 停顿点在货架上的单一出库任务；(c) 停顿点在货架上的复合作业；(d) 停顿点在出库位置处的单一入库任务；(e) 停顿点在出库位置处的单一出库任务；(f) 停顿点在出库位置处的复合作业。

空心圆代表停顿点；实心圆代表出库位置；实心方块代表入库位置；实线代表堆垛机负载移动路线；虚线代表空载移动路线图2 堆垛机可能的移动情形

本文考虑如何进行出入库任务的调度并确定出库任务释放到哪一个出库位置，使得堆垛机完成所有任务的总距离最短。该问题的决策包括出入库任务的完成顺序，以及出库位置的选择。为了方便问题表述和模型建立，我们假设上述仓储系统：

(1)堆垛机既可以进行单一作业，也可以进行复合作业，其运作能力为每次一个标准化托盘；

(2)堆垛机可以沿水平方向和竖直方向同时运动，且速度为常数；

(3)堆垛机的停顿点策略为停留策略，即堆垛机会在完成出库(或入库)任务的位置处停留，等待下一个任务；

(4)系统采用专用存储策略。因此，对于要存放的标准化托盘，其存储位置已知。

2.2 模型构建

考虑有m个入库任务，n-m个出库任务，以及K个出口位置。不失一般性，对任务进行编号，i=1,2,…,m表示入库任务，j=m+1,…,n表示出库任务，另定义任务0和T为虚拟任务，分别表示开始和结束任务；令Si为对应入库任务i的位置，Rj为对应出库任务j的位置，Ok为出口位置k，I和E分别为对应虚拟任务0和T的位置。

定义lk为出库位置k=1,2,…,K到入口的距离；dijkp为堆垛机从完成任务i后所停留的位置k，移动到完成任务j后所停留的位置p的距离，其中d0jIk表示堆垛机从入口I移动到完成第一个任务所在停留点位置k的距离，diTkE表示堆垛机从完成最后一个任务i所停留位置k，移动到虚拟任务T所在停留点位置E的距离，具体计算公式见表1。其中四元数组(A,B,C,D)定义为堆垛机从任务A移动到任务B，任务A和B的停顿点分别为C和D；堆垛机按照切比雪夫距离移动；此外(xi,yi)，(lk,0)分别是任务i和出库位置k的笛卡尔坐标。

表1 不同情况下对应的边权重计算公式

决策变量定义为：当堆垛机完成任务i后立即完成任务j，同时任务i的停顿点为k，任务j的停顿点为p时，Xijkp=1，否则为0。其中X0jIp，XiTkE取1时，分别表示第一个任务为j，且停顿点为p和最后一个任务是i，且停顿点是k；任务i完成的次序ui。于是，多出口位置的自动化立体仓库出入库调度与出库位置选择集成优化模型可以表示为：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

u1=1,

(9)

2≤ui≤n,∀i≠1,

(10)

(11)

ur

(12)

Xijkp={0,1},∀i,j∈J,∀k,p∈L.

(13)

目标函数(1)表示最小化堆垛机完成所有任务的移动距离；约束(2)和(3)确保堆垛机有起始任务和终止任务；约束(4)和(5)表示每个任务的前后均有任务；约束(6)和(7)表示堆垛机在每个停顿位置最多停顿一次；约束(8)表示每个任务对应的停顿点唯一；约束(9)、(10)和(11)表示避免产生子回路；约束(12)表示入库任务按照次序完成；约束(13)给出决策变量的取值范围。

2.3 复杂度分析

本节分析模型的复杂性，证明此类问题是NP-hard问题。

定理1出入库调度与出库位置选择集成问题是NP-hard问题。

证明：本文将该问题的一类特殊情况转化为TSP旅行商问题。构造研究问题的实例如下：设有m个出库任务，m个出库位置。我们设置一个虚拟点AP代表堆垛机的初始点和终止点，并假设虚拟点AP到出库任务所在位置和出库位置的距离均为0。为了防止堆垛机从任务所在位置(或出库位置)直接移动到另一个任务所在位置(或出库位置)，设任意两个任务所在位置(或出库位置)之间的距离足够大。原问题转化为求解从AP点出发，访问每一个任务位置和出库位置并回到AP点的最短回路。因此，求解此类特殊问题等同于求解TSP旅行商问题，由于TSP是NP-hard问题[26]，原问题也是NP-hard问题。

3 算法设计

3.1 多项式时间求解子问题

本文研究的堆垛机出入库调度与出库位置选择集成问题属于NP-hard问题，随着问题规模的扩大，无法在有效时间内获得精确的最优解。然而，我们可以在多项式时间内求解一个重要的子问题，即给定入库和出库任务的操作顺序，如何确定各个出库任务对应的出库位置。将此子问题命名为SP，并在之后利用其求解原问题。

定理2SP问题能够在O(n3)的时间内求解出最优解，其中n为出入库任务的数量。

证明：当给定出入库任务的操作顺序后，任意出库任务的下一个任务有三种情况且已知。(1)当下一个任务是入库任务时，堆垛机从出库任务的位置出发，移动到出库位置，再空载返回入口；(2)当下一个任务是出库任务时，堆垛机从出库任务的位置出发，移动到出库位置，再空载移动到下一个任务的位置；(3)当出库任务为最后一个任务时，堆垛机从出库任务的位置出发，移动到出库位置并结束。我们引入二分图理念，节点表示为出库任务j和出库位置k。如有必要，我们增加虚拟任务使得出库任务和位置的数量相等。任意出库任务均和所有出库位置相连，根据不同情况设置不同的边权重cjk见表2(其中q已知)。

表2 不同情况下对应的边权重计算公式

针对上述问题，我们可以建立整数规划模型如下：

(14)

(15)

(16)

yjk={0,1}.

(17)

目标函数(14)表示最小化总的边权重；约束(15)和(16)表示出库任务和出库位置一一对应；约束(17)表示决策变量的取值范围。此问题为指派问题，可使用匈牙利算法在O(n3)的时间内获得最优解。

注意到SP问题本身也是实践中的一个重要优化问题。对于入库任务来说，需要存放的货物会在传送带上等待堆垛机操作，由于很难在传送带上改变待存放货物的位置，因此，入库任务按照先到先服务的模式完成；对于出库任务来说为及时满足客户订单是许多仓库的重要准则，因此，出库任务通常根据到期时间排序，此时，出库任务的取货顺序也确定。

3.2 两阶段启发式算法

原问题分解成为两个子问题：(1)找到出入库任务的最优操作顺序，(2)在给定操作顺序下，决策如何将出库任务分配给出库位置。后一个子问题可以通过求解3.1小节中的指派问题获得最优解。为此，本文设计基于遗传算法和指派算法的混合求解算法对模型进行求解。遗传算法是一种通过模拟生物界自然选择和遗传机制的随机搜索算法，具有收敛速度快，不易陷入局部最优等特点。具体流程如下：

3.2.1 编码方式

编码方式为整数编码。入库任务按照先到先服务方式完成，编号为1,2,…,m；出库任务编号为m+1,…,n。采用一个n维序列表示一条染色体，即为子问题1的一个解。其中第i维上的数字为fi，表示任务fi被第i个处理。例如，图3(a)表示有6个任务(3个入库任务，3个出库任务)的子问题1的一个解的编码，在此调度方案中，堆垛机按照1-5-4-2-3-6的次序完成任务。

3.2.2 生成初始种群

定义种群规模为Npop的初始种群。考虑到入库任务按照先到先服务方式完成，有相对完成顺序的约束，在此基础上产生初始种群。例如图3(b)并不是可行解，因为入库任务2先于1完成，违背约束。

图3 编码表示

3.2.3 计算个体目标函数

在获得子问题1的解，即入出库任务的操作顺序(记为Ai,i=1,2,…,Npop)后，通过3.1节所提出的求解指派问题的方法确定各个出库任务对应的出库位置(记为Bi,i=1,2,…,Npop)。当出入库任务顺序，出库任务对应的出库位置均已知时，可计算出目标函数F(Ai,Bi)。

3.2.4 适应度函数

目标函数为求堆垛机完成所有任务运行总距离的最小值，因此，采用个体目标函数的倒数作为适应度函数，定义如下：

fitnessi=1/F(Ai,Bi)，i=1,2,…,Npop.

3.2.5 选择

对每代个体，通过轮盘赌法进行选择，每个个体的选择概率为

产生一个在[0,1]之间的均匀随机数，将该随机数作为选择指针确定被选个体。

3.2.6 交叉操作

采用单点交叉的方法，先从区间[1,n]中随机抽取交叉点，子个体Offspring1在交叉点左侧的基因与父个体Parent1在交叉点左侧的基因相同，Offspring1缺失的基因按顺序从父个体Parent2处获得；同理获得子个体Offspring2。由于模型对入库任务有严格的顺序约束，因此，为了避免产生非可行解，在交叉操作完成后增加一个步骤：不改变出库任务的顺序，将入库任务按照编号从小到大的顺序重新排序。

3.2.7 变异操作

随机产生两个变异点位置，交换两个变异点位置的基因，形成新的染色体。为避免变异产生非可行解，只对两个出库任务，或者不影响入库顺序的一个入库任务和一个出库任务进行变异操作。

综上，该算法的流程图和伪代码分布如图4和表3所示。

图4 算法流程图

表3 两阶段启发式算法伪代码

4 数值实验

实验使用MatlabR2014a开发算法程序。由于遗传算法的参数设置会影响算法效率，我们对参数的选择进行多次测试，其中种群规模大小、交叉概率和变异概率的集合分别为Npop={50,80,100}，α={0.7,0.8,0.85,0.9}，β={0.05,0.1,0.15,0.2}。通过预先实验获得了一组较好的遗传算法参数组合：Npop=50，α=0.8，β=0.15。本文制定2个遗传算法终止规则：一是当最优目标值保持不变次数达到最大迭代数的三分之一时终止；二是算法的迭代次数达到预设的最大迭代次数时终止(本文采取文献中常用的100次迭代)。仓库参数设计选用Ramtin和Pazour[17]，设置仓库长为60 m，高为24 m，托盘大小为1.2 m*1.2 m。为了验证所建立模型与本文设计的两阶段启发式算法的有效性，对每个算例进行20次计算取平均值，并使用CPLEX求解模型，通过结果比较来验证算法效率。所有实验均运行在1.8 GHz Intel Core 4 CPU和8GB内存的计算机上。

针对每一个算例，分别用CPLEX和本文提出的启发式算法求解，对比CPU计算时间和求得的结果。其中GAP1=(本文算法目标值-CPLEX目标值)/CPLEX目标值*100%，GAP2 =(FCFS方法目标值-本文算法目标值)/本文算法目标值*100%。记SN、RN和K分别表示入库任务、出库任务和出库位置的数量。实验结果如表4所示，且有以下结论：(1)当出入库任务数量多于27个时，CPLEX已无法求解，而本文算法在所有算例中均能求出近似最优解，与CPLEX求出的最优解最多相差2.82%。同时，本文算法花费的CPU时间也非常短，求解20个任务15个出库位置的问题只需不到6秒，运算效率远远高于CPLEX。综上，本文算法在效率和有效性两个方面上表现均较好。(2)本文提出的算法相较于先到先服务方法最大改善了25.09%，平均改善了20.47%，表明本文算法明显优于企业中常用的先到先服务方法。

表4 算例结果对比

接下来研究出库位置的数量变化对数值结果的影响。我们随机产生10组出入库任务的数量和所在位置，对于每组算例，出库位置的数量K变化为{10,12,14,16,18,20}。使用本文提出的算法求解目标值并对10组算例取平均值。数值结果如图5所示。我们发现随着出库位置数量的增加，堆垛机移动的距离从636 m逐步降低，最终保持平缓到596 m。注意到出库位置的增加也会带来运作成本的增长，如拣选人员的人力成本等。因此，企业管理人员需要权衡每多开一个出库位置带来的堆垛机移动成本的减少和其他运作成本的增加，以确定最优的出库位置的数量。

图5 出库位置数量对目标值的影响

5 结语

本文主要研究了一种新型自动化仓储系统，其特征是在货架的底层有多个出口位置以供拣选人员做订单拣选任务。此仓储系统将存储和分拣任务统一于一处，既提高了空间利用率，又降低了能源消耗。本文聚焦于出入库任务调度和出口位置选择问题，需要同时决策出入库任务的顺序以及出库任务与出口位置的匹配。我们提出了求解该问题的混合整数规划模型，并将问题分解成两个子问题：先确定出入库任务的顺序，再在给定顺序的情况下决策出库货物释放到哪一个出库位置。后一个子问题可以在多项式时间内求出最优解。根据此性质我们设计了基于遗传算法和指派问题的两阶段启发式算法，并与CPLEX求解的结果进行比较。数值实验的结果表明了该模型和算法的有效性。

本文可以在以下几个方面进行扩展研究：首先，本文考虑了仓储系统采用专用存储策略，而针对不同的存储策略对调度问题影响的研究对实践也有重要的指导意义。其次，在理论方面，如何为该优化问题设计求解一个紧的下界也很值得期待。