0 引言

随着物流订单从品种少、批量大到品种多、批量小或批次多、批量小的发展，仓储功能已从考虑存储效率的重要性逐渐变为考虑如何合理地分配仓位以及顺利地自动存发货。智能仓储系统被广泛应用于仓储和物流的各个方面，合理高效的仓储调度不仅大大减轻了工作人员的劳动强度，而且在提高仓储空间利用率和降低人力成本等方面具有明显的优势。智能仓储调度系统的建模与求解已经成为业内人士的热门研究领域。

传统的物流仓储车间和运作体系依赖大量的人工作业，需要大量的人力成本。而且传统的库位分配方式存在着仓储库位及进出库货品数据更新缓慢、库位有效利用率偏低、库位分配模式静态化、仓储内搬运效率低下等问题，从而产生高额的库存成本。目前，在针对物流仓储调度优化技术和方法中，建模及求解已经成为检验该仓储调度系统及决策是否高效的主要技术之一。在设计新的库位优化方法或在对运输设备的行动优化时，利用一个良好的仓储调度模型进行模拟求解能提供直观的决策支持。

对于智能仓储调度问题的建模与求解，现有的许多方法依赖于基于特定模型的优化方法（具体见第1章）。这些模型参数多、人工干预多，常需在实验过程中手动定义多个参数值。参照某物流公司提供的仓库库位及堆垛机信息，本文提出一种基于概率并行规划的物流自动仓储调度方法。根据仓储库位及智能体存取货动作的不确定性及并行性等特点，该方法首先构建一个形式化的规划领域描述模型，然后使用概率并行规划技术来进行自动求解。本文主要利用智能规划方法对自动仓储调度领域进行建模，然后利用规划求解技术进行自动模拟。构建的规划领域模型包含了对各种影响因素、约束条件以及可能事件的形式化描述，以求解得到可表征整个调度过程的动作策略。整个求解过程不需要人工干预，可解释性强，直观易懂。

1 研究背景

1.1 物流自动仓储

伴随着电子商务、人工智能、新能源等行业的快速发展，物流订单特征呈现品种多、周期短、批量少、批次多的趋势。然而在当今的企业用工作业大环境中，人口红利逐渐减弱，土地和劳动力成本不断上升。以劳动密集型为主要形式的传统仓储物流业务形式已经不能满足当前阶段的实际业务需求。仓储物流技术的发展急需转型升级以实现智能化。

近年来，国内外厂商都在积极关注并创新开发智能物流仓储系统。亚马逊率先成功研究了Kiva Systems仓库机器人系统，使用数百个自动导航车（automated guided vehicle,AGV）代替了工作人员完成货物订单的存取任务，使工作人员免于每天马拉松式地来回存取货物并极大地提高了仓储存取操作的效率[1]。国内厂商如极智嘉、海康等先后实现了类似Kiva智能系统的先进技术并占据了大部分市场份额，京东也正在研发建设完全无人的自动化物流中心。在技术不断创新与融合的背景下，自动仓储AGV的功能及性能得到极大的改进和提升，而实现订单与AGV的合理调度策略才能决定整个自动物流仓储系统的性能。

针对智能仓储调度问题的建模与优化，近年来国内外很多学者进行了深入的探讨。Aoyama等人[2]基于电子商务的发展趋势及物流产业的模式，使用蒙特卡罗仿真设计了物流以及信息流两个内部连接网络的最优化模型，通过实验仿真模拟信息和运输费用因素在物流企业中的影响。Ballestín等人[3]考虑了在具有随机存储和不同类型叉车的实际仓库中存储和检索问题，为每个存储或检索的位置选择足够熟练的叉车，并确定每个叉车执行操作的顺序，以使总的使用时间最小化，通过将问题分解为三个子问题并基于启发式算法解决。Cheng等人[4]改进了存储/运输物流系统的最优化问题，基于离散事件建模和随机优化控制设计了一种用于决策支持物流系统的建模仿真算法，使决策者了解动态随机系统的行为。国内学者于赫年[5]以仓储空间环境模型为研究对象，分析多智能体调度系统的任务分配模式、作业流程及任务调度约束条件，以最小化最大任务完成时间为主要目标，建立复合指标的数学模型确定AGV的调度方案。印美等人[6]以堆垛机行驶时间和货架稳定性为优化目标，基于Pareto遗传算法建立货位多目标优化的数学模型求得动态货位优化最优解，较大改善出入库效率及能量消耗。鲁建厦等人[7]通过分析跨层穿梭车仓储系统中提升机与穿梭车的实际作业流程，建立复合作业路径规划模型并基于人工鱼群算法求解该模型，有效地提高该仓储系统的运行效率。

1.2 概率并行规划

智能规划[8]是人工智能的一个重要分支。其规划过程是寻找从初始状态到目标状态的一个无冲突可应用的动作序列。概率并行规划是概率规划和并行规划的结合体，允许非互斥的动作并发执行，动作的前提和效果满足全局性约束，放松了经典规划的五大假设[9]。由于在该类问题中动作具有不确定性和并行性，所以在模拟现实问题上有很大的应用潜力。饶东宁等人[10]针对股票市场具有大量的不确定性和并发性，基于概率并行规划构建股指模拟问题的规划领域并求解得到股票模拟指数。但是，由于不确定性和并行性的结合，状态搜索空间在最初的几个搜索步骤中变得非常大，所以传统的搜索策略和启发式评估效率很低，如何更好更快地求解概率并行规划问题也是近年来规划领域的热门研究方向[11,12]。

概率并行规划问题由规划语言关系动态影响图语言RDDL来进行描述的。RDDL是基于规则的规划描述语言，其语义为关系动态贝叶斯网络（relational dynamic Bayesian network,RDBN)[13]。RDDL是经过之前的规划语言演进过来的，具有许多其他规划语言所不具备的新特性，包括一切含有参数的非流（non-fluent）或流（fluent）的变元。它描述了函数变化作为状态转移、通过逻辑表达式或分布函数来描述回报函数、（部分可观察）马尔可夫决策过程（partially observable Markov decision process,(PO)MDP）目标和对其的状态/动作约束等特性。RDDL使用马尔可夫决策过程（MDP)[14]来建模具有顺序决策的问题，其中系统在时间上不断发展，并且由代理控制。马尔可夫决策过程（Markov decision processes,MDP）描述了一个动态过程，每个规划步代理观察环境，随后它选择执行一个动作，动作被执行后环境发生改变，随后代理会得到环境变化后的奖励。MDP定义如下：M=(S,A，φ，R），其中S和A分别是有限的状态和动作集；φ（s,a,s′）是在状态s执行动作a后环境演化到s′的概率；R是回报函数，R(a,s）定义了在状态s执行动作a获得的中间奖励。MDP的解叫做策略（policy），简称π，定义了在每个状态代理要执行的动作。用Vπ（s）表示策略π下状态s的值函数，最优策略π*是指获得累计启发奖励最大的策略V*，满足贝尔曼等式。

其中：γ（0≤γ≤1）为折扣系数，它被用来对未来的行动进行折扣奖励，因为不确定性决定了这个过程。

2 问题描述与假设

参照某物流公司提供的仓储库位及堆垛机信息，本文模型使用RDDL规划语言进行建模。仓库模型如图1所示。

图1 仓储模型   

将整个仓库的对象抽象为一个三维体系（图1(a）），体系中包含有智能体（堆垛机）、货柜、不同位置的货物、多个通道、一个入货口和出货口（图1(b））。堆垛机只能在通道里移动并且根据订单需求进行存货和取货。堆垛机的动作是确定性的，在入货口或者出货口分别是入货和出货动作，在通道中是移动动作，到达存储货物的货柜位置时存放或拿取货物。一台堆垛机的存放容量是有限制的，即一台堆垛机本身只能存放一定的货物。货柜即存放货物的地方，通道、入货口和出货口的位置都是固定的。假设货物的存放位置是由系统根据订单状态随机得出的，并且只有货柜为空和货柜的大小符合货物大小的时候堆垛机才能存放货物，另外货柜是两层的，内外层都是可以存放货物的。由于货物的存放位置是不同的，所以入货到存货、取货到出货时每台堆垛机的移动也是不同的，最终完成目标的时间也是不同的。

3 模型构建

本文仓储调度的RDDL领域模型由六个部分组成。RDDL文件包含了领域（domains）和实例（instances）两种类型的顶级声明。RDDL领域由六个部分组成，包括requirements、types、pvariables、cpfs、reward和constraints。每个部分在构建完整的概率并行规划领域过程中都是不可缺少的。实例模块包括了非流变量、领域问题对象、领域的初始状态、可并发变量和折扣因子等。针对本文仓储调度的具体对象，领域模型（https：//github.com/KimkaychanJK/warehouse＿scheduling＿domain）构建过程如下：

a)requirements。该部分描述各个领域具体操作的需求，包括领域的特点和所需要的约束等。本文使用了三种需求，reward-deterministic说明领域是使用自定义的特定回报值；constrained-state说明领域使用状态约束；concurrent说明领域对象可同时执行多个动作。具体为

b)types。该部分定义该仓储调度领域的对象，分别为stacker（堆垛机）、bin（货柜）、aisle（通道），x＿section、y＿shelf、z＿level分别代表仓库三维体系的三个方向。具体为

c)pvariables部分。该部分定义影响该仓储调度的变量类型（分别有非流文字（non-fluent）、流文字（fluent）、动作流（action-fluent）、状态流（state-fluent）、中间流（interm-fluent）和观察流（observfluent）），并界定每种变量的变化范围。本仓储调度领域使用了non-fluent、state-fluent和action-fluent。non-fluent与fluent示例如下：

non-fluent表示在整个规划过程中保持不变的量，它只会改变每个问题的定义。本文领域中的non-fluent分别为adjacent-forward和adjacent-backward（堆垛机移动方向）、binAt（货柜位置）、aisleAt（通道位置）、inboundItemAt（入货订单位置）、inboundBase（入货口位置）、outboundBase（出货口位置）和outbound＿prob（货物出货的概率）。

state-fluent变量表示在规划过程中变化的状态，分别为stackerAt（堆垛机位置）、binUsed（货柜使用状况）、itemTaken（堆垛机取出货物状态）、itemStored（堆垛机存放货物状态）、itemInbound（堆垛机入货状态）、itemOutbound（堆垛机出货状态）、num＿InboundItemAt（堆垛机上入货货物的数量）、num＿OutboundItemAt（堆垛机上出货货物的数量）、num＿OutboundItem（总的出货订单数量）和num＿BinUsed（被使用的货柜的数量）。

action-fluent表示领域中采取的动作，分别为forward（往前移动）、back（往后移动）、move（移动）、fetch（取货）、store（存货）、inbound（入货）和outbound（出货）。

d)cpfs。cpfs(conditional probability function，条件概率函数）部分是使用RDDL建模的重要部分，即fluent变量必须执行的转换。它能够反映状态变量如何进行演化。本文仓储调度领域中的每个cpf采用条件语句等语句结构解释各个变量的变化情况。

当堆垛机到达出货口位置且当堆垛机上携带的待出货货物数量为0时，堆垛机成功出货，具体的cpfs定义为：

e)reward。该部分定义确定性回报函数，受状态变量和动作变量的影响。本仓储领域的reward函数设计为所有堆垛机完成入货和出货任务时的时间之和，具体为

f)constraints部分。该部分指定状态约束，旨在领域实例运行之前检验模拟期间每个状态的约束条件，如下约束函数表示对于每一台堆垛机来说，每一步只能采取一个动作。

具体的货柜数量、堆垛机数量等影响整个仓储调度因素的初始化数据、模型求解运行次数和并行运行的堆垛机动作数由问题实例给出。根据给出的仓储库位信息，本文模型可以随时加入最新的可知变量（即影响调度过程的因素）和修改变量（即影响调度过程的因素）参数，不需要编译直接就能运行。

4 实验

a）实验环境。Windows 10 64位+CPU 1.70 GHz(i5-4210U）+内存8.00 GB，模型horizon=400。实验平台是运用国际概率规划大赛（IPPC）提供的rddlsim(2014）规划器，它能够对RDDL描述的领域进行完全解析和配置估值函数并实现求解策略（式（1））的计算过程。

b）实验模型。图2为该仓储调度领域模型的RDDL语义模型图。该图为动态贝叶斯网络（dynamic Bayesian network,DBN）扩展的影响图（influence diagrams,ID），描述了该仓储调度领域影响因素之间的对应关系。实验假设仓库模型（15×5×2）有三条通道，两层货柜共有72个，三台堆垛机从入货口入货然后分别进入各自的通道依据各自的货物订单移动到对应的货柜位置进行存货或取货，最后在出货口出货。实验将构建完成的领域文件输入进行解析，采用rddlsim提供的随机布尔策略进行求解，领域问题由初始状态经过一系列演化最终到达目标状态，自动实现模拟效果。

图2 仓储调度领域的语义模型  

实验求解结果如图3所示，可以看出三台堆垛机从入货口开始各自采取不同的动作完成入货及出货任务。由于在rddlsim中采取的是随机布尔策略，堆垛机的动作是随机的，所以从初始状态到目标完成任务状态每台堆垛机所用的动作序列及时间是不同的。领域reward值定义为所有堆垛机完成任务的时间之和，所以此次模拟实验的reward为79。整个模拟过程不需要人工的干预，通过动作序列图可以直观地了解整个模拟过程，解释性强，并且能够通过不断地模拟求解，得到较低的reward值的动作策略。

rddlsim精确方法求解次数越多，得到最优解可能性越大。但随着问题规模的扩大，对于中等规模或者大规模的问题，在有限的时间内不可能求得最优解。对于大规模的问题，不需要求得最优解，只需在短时间内求得次优解或者满意解。表1为对于不同规模的模型问题，规划器求解的平均时间。假设一条通道加上两侧的货柜为一个单元，从图中可以看出问题规模越大，求解时间越长，且当问题规模过大时（如通道数目达到5时）求解时间过长甚至无法求解。

图3 rddlsim规划器求解动作序列  

表1 不同规模问题求解时间

5 结束语

本文主要是基于概率并行规划方法对自动物流仓储调度领域进行建模，然后利用规划器rddlsim及随机布尔策略进行求解。本文构建的领域模型包含了对多种影响因素、约束条件以及可能事件的形式化描述，可解释性强，直观易懂，具有较好的模拟性能。实验结果表明，本文方法能够实现堆垛机在仓库中入货和出货过程的自动模拟，并可以根据模型的reward值定义实现对模型的优化。当然，该领域模型还存在许多值得研究和改进的方面。下一步工作要考虑更多的约束条件与可能事件，包括多台堆垛机的拥塞控制及多种不确定事故等。另外，还需要不断地优化模型参数，调整规划器求解策略和提高求解效率。