论文拾萃 | 紧致化智能机器人存取系统的运行策略研究
论文拾萃 | 紧致化智能机器人存取系统的运行策略研究
紧致化智能机器人
存取系统的运行策略研究
邹碧攀，René de Koster，徐贤浩
摘要
近年来，紧致化智能机器人存取系统(Robotic compact storage and retrieval systems)得到了广泛应用。该类系统将货物存储在标准化物料箱(bin)中，然后采用堆叠(stack)的形式进行存储。智能机器人在网格顶部行走，将货物在工作站与堆叠之间进行运输。本研究在该系统中考虑指定(dedicated)和分享式(shared)存储策略，并结合随机与分区存储方案，旨在建立有效的绩效指标评估模型，分别从系统吞吐率与运行成本的角度来优化系统结构和运行策略。首先，建立半开半闭排队网络(semi-open queueing network)；然后采用近似矩阵几何算法进行求解，并使用仿真和真实案例进行模型验证。该绩效评估模型可用于优化系统结构和运行策略选择，结果表明，指定存储策略可显著提升系统吞吐能力；最后，本研究构建带吞吐时间约束的成本优化模型，比较不同存储策略下的最优运行成本。结果表明，分享式存储策略可大幅提升系统存储空间利用率，从而降低约40%的运行成本。
关键字
物流、仓储、紧致化智能机器人存取系统、理论与仿真建模
原文出处
Bipan Zou*, Xianhao Xu & René de Koster, 2017. “Operating policies in robot-based compact storage and retrieval systems.” Transportation Science, In Press.
基金支持
国家自然科学基金资助项目（71131004）
一、 紧致化智能机器人存取系统的发展
与研究现状
根据全球知名的管理咨询公司罗兰贝格（Roland Berger）2016年发布的一篇报告显示：“智能机器人在物流系统中的广泛应用将不再是问题，且未来10年欧元区将会有近150万工作岗位被机器人取缔”。这种趋势在智能化仓储系统中尤为明显。本文研究一种全新的智能机器人存取系统（Robotic Compact Storage and Retrieval System, RCSRS），这是一种全自动化的单元载荷存储和订单拣选系统（如图1所示）。该系统采用标准化物料箱存储货物，并将它们组织成堆叠的形式存放在网格中。带有升降能力的机器人在网格顶部移动，进行货物的存取和运输。
(a) 主视图 (b) 智能机器人
与传动自动化存取系统相比，RCSRS具有如下几点优势：
1. 灵活、模块化的结构：应用者可以先从小网格开始，然后根据需求逐步扩张系统。
2. 灵活的吞吐能力：该系统可以很容易的通过加入机器人和工作站来提升系统吞吐能力。
3. 相对较低的运行成本：根据罗兰贝格的报告，机器人解决方案可降低约20%-40%的运行成本。机器人的平均运行成本（18-20欧元/小时）已低于劳动力成本，且会持续下降。
4. 紧致化存储空间和快速反应时间：该系统采用堆叠形式进行存储，消除了巷道。机器人可以灵活的选择最优路径，从而更快完成订单任务。
基于以上几点优势，RCSRS系统已在许多知名企业尤其是在线零售商中得到应用，包括英国的ASDA和Ocado，荷兰的Active Ants和澳大利亚的Catch of The Day等等。
在企业实际应用该系统之前，需要从海量可行方案中选择符合系统吞吐能力与运行成本需求的最优方案。而该工作很难在合理时间内通过仿真来完成，因此，准确有效的绩效指标评估模型将是RCSRS的应用所必须的一项工具。
另一个RCSRS系统的使用者需要考虑的问题是存储策略的选择。在该系统中，存储策略会显著影响系统所需的存储空间和系统吞吐时间。具体来说，每个存储堆叠中存储一种货物（即指定存储策略）可以消除不必要的翻箱作业，从而提升吞吐能力，但系统将需要更多的存储空间。相反，允许多种货物共享一个存储堆叠可以显著降低系统所需存储空间，但将带来更多的翻箱作业，从而降低吞吐能力。因此，本文将从运行效率与运行成本的角度来研究指定存储策略与分享式存储策略，并结合随机和分区堆叠方案。本文的研究框架如图所示
二、 运行策略
本文考虑如下图所示的系统结构。工作站设置在系统的左右两侧，在每个工作站的入口处有一个小车等待的缓冲区。每个工作站有一个旋转系统和两个存放料箱的位置，一个位置供拣货人员进行拣选，另一个位置用于小车释放和抓取料箱。当小车释放一个需要进行拣选的料箱后，该旋转系统快速的将前面已经拣选了的料箱和该料箱更换位置，然后小车抓起拣选过的料箱，将其存放到系统中去。基于此作业模式，小车进行双指令作业(dual-command cycle)，即在一个作业周期中执行一个存作业和一个取作业。
在一个使用高位存储堆叠的系统中，存储策略决定了该系统所需要的存储空间和吞吐时间。在制定存储策略下，每个堆叠只存储一种货物，其优势在于避免了取货过程中的翻箱过程。劣势在于系统需要更多的存储空间。在共享式存储策略下，每个堆叠中可以存储多种货物，其优势在于系统需要的存储空间更少，其劣势在于由于取货过程包含了料箱的翻箱作业，取货时间更长。在堆叠中，本文考虑指定存储策略和分享式存储策略。此外，在网格上，本文考虑随机存储策略和分区存储策略（如下图所示）。在随机存储策略下，每个堆叠都有可能存储任意一种货物，在分区存储策略下，所有的堆叠分为几类区域，指定区域的堆叠只存储属于该区域的货物。
在共享式存储策略下，取货过程可能需要翻箱，本文考虑两种翻箱策略，即立即翻箱策略和延迟翻箱策略。在立即翻箱策略下，小车首先将阻挡在目标料箱上面的料箱移动至相邻的网格单元上，然后取出目标料箱并将其放置在相邻的网格单元上，最后，小车将阻挡料箱返回该堆叠。在延迟翻箱策略下，小车将阻挡料箱移动至相邻网格单元上后，取出目标料箱，然后将其运输至工作站完成双指令作业，最后再返回阻挡料箱处，将它们返回堆叠中。
接下来，本文建立半开半闭排队网络模型(Semi-open queueing network)来评估系统绩效指标。
三、 基于SOQN的系统绩效评估模型
本文首先构建如下图所示的半开半闭排队网络模型(SOQN)来评估各存储策略和翻箱策略下的系统绩效，然后，设计近似矩阵几何算法(Matrix-Geometric Method)求解该理论模型。
该模型将紧致化自动小车存取系统的双指令作业服务过程模拟为一个SOQN。每个订单都包含一个存作业和一个取作业，小车被模拟为一种单独的资源，每个订单的服务都需要首先匹配一个小车。该SOQN模型包含一个同步服务点(synchronization node)，该点包含一个订单队列(Q_o)和一个小车队列(Q_r)。到达系统的订单首先在Q_o中等待小车，闲置的小车则在Q_r中等待订单的到达。其中，除工作站以外，其余服务站点的服务都不需要等待资源，所以，它们被模拟为无限能力服务者(IS)。
该模型通过变化服务点u_s和u_r的结构来刻画不同的存储策略与翻箱策略。小车首先从其待命位点移动至取货料箱所在的堆叠处，该过程被模拟为服务点 u_d,r(IS)。到达取货点后，小车从堆叠中提取取货料箱，该过程模拟为服务点u_r。然后，小车以概率
行走至工作站w_i，该过程模拟为服务点u_r,wi。到达工作站后，如果拣选人员繁忙，小车等待，然后进行交换料箱的过程，该过程模拟为服务点u_wi。小车将需要重新存储的料箱运输至存储点，该过程模拟为服务点u_wi,s。最后，小车将料箱释放到存储堆叠的顶部，该过程模拟为服务点u_s，小车完成一个双指令后被释放，停在作业完成点等待下一个作业。该过程对应于小车进入队列Q_r等待订单。
本文构建的SOQN包含一种类型的顾客和多个服务时间服从一般性分布的服务点，由于该类SOQN没有产品式解法(Jia and Heragu, 2009))。基于此，本文使用如下近似解法求解该SOQN：
(1) 构建一个包含服务点u_r,wi及u_w和u_wi,s的闭环排队网络CQN1（如图6）。然后，使用近似均值分析算法（Approximate Mean Value Method, AMVA）求解该闭环排队网路的吞吐率TH_1(n_1)。最后，将这三个服务点用一个服务率为
的复合服务点代替。
(2) 构建一个包含服务点u_d,r及u_r和u_s的闭环排队网络CQN2（如图7），使用AMVA求解其吞吐率TH_2(n_2)，将这三个服务点用一个服务率为
的复合服务点代替。
(3) 经过步骤1和2后，得到一个含两个复合服务点的简化SOQN（如图8），然后使用矩阵几何算法求解（Matrix-Geometric Method, MGM）该模型。
闭环排队网络CQN1
闭环排队网络CQN2
简化半开半闭排队网络
定义该简化半开半闭排队网络的状态变量为
其中n_op为外部队列Q_o中等待小车的订单数，状态变量的下标k通过下列公式计算
简化半开半闭排队网络的状态转移过程如图所示
令π_k为状态s_k的稳态概率。定义稳态概率向量为
和
得到生成矩阵Q后，基于如下公式和如下迭代算法求得速率矩阵R
得到R后，本文可以通过求解如下方程式来求解状态概率向量π_0和π_1
其中，e是单位向量。其他稳态状态概率向量可以由来
求得。外部队列中的平均等待顾客数可以用下列公式计算
其中，|π_i|是概率向量π_i中所有元素的和。
系统中处于工作状态的机器人的平均数量，即系统正在处理的平均作业数，可以通过如下公式来求得
一个工作站的缓存区中，等待小车的平均数为
其中，EL_w(i)是当服务点u_c1(.)有i个顾客时，该工作站的缓存区中等待小车的平均数。可以通过AMVA算法得到该值。
根据利特尔法则(Little’s Law)，作业对小车的平均等待时间和小车对工作站的平均等待时间可以通过如下公式计算
系统吞吐时间计算公式为：
小车与拣货人员的利用率计算公式为：
其中，Q_w(i)是当第一个复合服务点有i个顾客时，一个工作站繁忙的概率。本文通过AMVA算法得到该值。
四、 绩效评估模型仿真验证
本文使用Arena(版本14.7)为紧致化自动小车存取系统构建仿真模型。系统参数（包括料箱尺寸、小车速度和小车装载/卸载货物的时间）见表1。该系统参数来源于一家在瑞士的纸材料分配中心，该中心使用紧致化自动小车存取系统。
为充分验证理论模型的有效性与可行性，本小节通过变化系统高度H，订单到达率λ和系统所使用的存储策略和翻箱策略来生成多种系统方案。具体来说，H取10或者15，系统长宽比等于1。在一个给定存储策略下，首先得到系统所需的存储容量C，然后得到系统长L和宽W。对于每种系统方案，订单到达率λ都取三个值，对应于工作站利用率从60%变到80%。所以，一共有36个仿真方案（见表2）。
对于每一个方案，仿真程序首先运行100小时的热身时间，以消除系统误差，然后正式运行100次，每次1000个小时，以达到95%置信度条件下置信区间半长小于均值的2%。本文收集系统的五个指标，然后与理论值进行对比，包括双指令吞吐时间THT_DC，小车对工作站的期望等待时间W_w，小车利用率ρ_r，拣选人员利用率ρ_p和堆叠填充率
理论模型的准确性通过绝对相对误差δ来衡量
其中，A和S分别是理论结果和仿真结果。δ的均值和变化范围见表3。结果表明，理论模型可以准确评估紧致化自动小车存取系统在不同存储策略和翻箱策略下的绩效，除了小车对工作站的平均等待时间W_w。然而，由于W_w的绝对值相对较小，所以，其相对误差的绝对值较大。从表3中可以得出如下几点结论：
(1) 与随机存储堆叠相比，将堆叠进行分区可以在指定存储策略下将系统吞吐时间平均提高4.5%，在分享式存储策略下将系统吞吐时间平均提高7.7%。
(2) 尽管指定存储策略比分享式存储策略多需要51.9%的存储位，但是，指定存储策略相比于分享式存储策略，可以将系统吞吐时间平均提高24.5%。立即翻箱策略相比于延迟翻箱策略，可以将双指令吞吐时间平均提高12.1%。
此外，本文还通过一个真实系统来验证理论模型的准确性与有效性。使用该系统的是一个位于比利时奥德纳尔德的运动服务公司(Lalesse 2016)。该系统使用全混合的存储策略，即分享式策略和随机堆叠的组合，并使用立即翻箱策略。为准确比较真实系统与理论模型的绩效，本问考虑小车的加减速。行走时间可以通过下列公式计算
验证结果见表4，结果表明理论模型可以准确的估算紧致化自动小车存取系统的绩效。
五、主要结果
本文利用理论模型对RCSRS系统进行结构设计和运行策略优化。首先，研究不同存储策略下系统的最优结构尺寸；然后，研究不同存储策略下系统的最优堆叠高度；最后，考虑RCSRS系统的成本优化问题。
最优系统结构
研究一个存储能力固定的RCSRS系统的最优结构尺寸（长、宽、高）。系统存储N种产品，产品需求率D(i)和订货成本与存货成本的比例K都给定，系统满足EOQ补货条件。优化目标是最小化系统吞吐时间THT_DC。所以，构建模型:
其中，工作站数量n_w满足系统稳定条件
第一个等式是产品i的需求，第二个不等式保证了堆叠数足以存储所有产品，第三个不等式表示网格尺寸的实际约束。在堆积堆叠策略下，决策变量是网格高度H和系统长宽比r，在分区堆叠策略下，决策变量是P_A,P_B,H和r。本文使用贪婪算法求解模型(4M.1) 。
表5和6分别对应随机堆叠下和分区堆叠下系统的最优结构尺寸。从中，本文有如下几点观察：
(1) 在随机堆叠策略下，系统最优长宽比为
在分区堆叠策略下，系统最优长宽比略大于0.5，这是因为将堆叠进行分区有利于减小小车在宽度方向上的行走时间。
(2) 指定存储策略需要的总存储位大约是分享式存储策略需要的总存储位的两倍。这是因为两个原因：分享式存储策略允许空间共享且堆叠的填充率更高；高网格更适合指定存储策略，扁平网格更适合分享式存储策略。
(3) 以双指令作业吞吐时间为评价标准，指定存储策略在立即翻箱策略下，优于分享式存储策略约10%，在延迟翻箱策略下，优于分享式存储策略约4.6%。与延迟翻箱策略相比，立即翻箱策略可以将双指令作业吞吐时间平均降低约15.7%，然后会提高取货吞吐时间约13.7%。
不同存储策略下的最优系统高度
本文研究不同存储策略下，紧致化自动小车存取系统的最优堆叠高度。
首先，通过变化产品数量N和存储策略来生成一系列的方案。具体来说N=5000或者15000，系统使用指定存储策略、分享式存储策略、随机或分区堆叠策略。产品需求率服从曲率为s=0.065的ABC曲线。对于分享式存储策略，使用立即翻箱策略，K以步长100从100变化至1000。使用模型(4M.1)来求解系统最优高度H*，结果如图:
结果表明，在指定存储策略下，最优堆叠高度H*随着K的增加显著增加，然后，在分享式存储策略下，H*只会略微增加。该结果表明，如果订货成本增加，订货期变长，单次订货量增加。因此，系统需要使用更高的网格来存储更多的产品。相反，如果订货成本降低，系统需要降低网格高度，以减少库存量。与指定存储策略相比，分享式存储策略下的最优堆叠高度相对较小且对K的敏感度更低。这表明高网格更加适合指定存储策略，而扁平网格则更加适合分享式存储策略。
成本优化模型
以上研究结果表明，相比于分享式存储策略，指定存储策略在系统吞吐时间方面更具优势。这是因为分享式存储策略下，小车取货作业需要进行翻箱。然而，尽管分享式存储策略不利于系统吞吐时间，但是它却可以节省存储空间。因此，这两种存储策略之间的选择问题实际上是运作效率与系统成本之间的权衡问题(trade-off problem)。因此，本文研究指定和分享式存储策略下RCSRS系统中的成本优化问题，成本优化模型为（4M.2）
接下来，使用一个算例来分析紧致化自动小车存取系统的成本优化问题。该系统存储N=10000中产品，产品的需求ABC曲线，曲率为s=0.065,0.222,0.576。每个小车可以使用7年，成本为30000欧元，每个存储位可以使用10年，成本为40欧元，仓库中每平米地面面积可以使用30年，成本为500欧元。考虑利率IR=0.5%，然后，小车、存储位和每平米仓库地面面积的年均成本为
系统订单到达率为λ =300每小时。本文求解模型（4M.2），系统最小成本如图：
s=0.065
s=0.222
s=0.576
上图表明，在给定吞吐时间约束下，与指定存储策略相比，分享式存储策略可以显著减少RCSRS系统的总成本。具体来说，分享式存储策略下，系统最优成本比指定存储策略下的低约50%。该结果可以通过如下原因解释：与分享式存储策略相比，指定存储策略需要更多存储空间且堆叠的填充率相对较低。
除了分享式存储策略在系统成本方面的优势外，上图也反映了指定存储策略在系统吞吐时间方面的优势。相比于分享式存储策略，指定存储策略可以为紧致化自动小车存取系统提供更低的系统吞吐时间。具体来说，在指定存储策略下，s=0.065时，系统吞吐时间THT_DC可以到达[90,95)，s=0.222时，THT_DC可以到达[95,110)，s=0.576时，THT_DC可以到达[110,120)。因此，这两种存储策略之间的权衡就是：分享式存储策略可以显著减少系统成本，然而，指定存储策略可以为系统提供更低的吞吐时间。
六、管理启示
本文为RCSRS系统构建了准确有效的绩效指标评估模型和成本优化模型，分别以吞吐时间和最低运行成本为评价指标，对堆叠内存储策略、堆叠间存储策略、翻箱策略和系统结构尺寸进行了研究。结果表明：
- 在随机堆叠策略下，系统最优长宽比约为2/3，在分区堆叠策略下，该值略大。
- 在最优结构中，高网格更适合于指定存储策略，扁平存储策略更适合于分享式存储策略。
- 指定存储策略更有利于降低系统的双指令吞吐时间，延迟翻箱策略可以通过牺牲双指令吞吐时间来降低系统取货吞吐时间，分享式存储策略可以减少系统存储空间，从而降低系统总成本，但是，指定存储策略可以提供更低的系统吞吐时间。
作者信息：
邹碧攀：管理学博士，中南财经政法大学工商管理学院讲师。研究方向为紧致化仓储系统的运行策略优化研究。主持湖北省自然科学基金青年基金项目1项。
René de Koster: 工业工程专业博士，荷兰伊斯拉姆斯大学鹿特丹商学院（Rotterdam School of Management, Erasmus University）物流与运作管理系（Logistics and Operations Management）全职教授，研究兴趣包括仓储系统、物料运输、容器处理运作、行为动作和逆向物流等。目前，已出版8本书籍，已发表150篇论文，这其中有30余篇发表在POM,TS,JOM等国际顶级期刊上。现在多个学术期刊上担任副主编或者编委会成员，包括Transportation Science(SIE), International Journal of Operations & Production Management(SIE), JOM等。
徐贤浩：管理学博士，华中科技大学管理学院教授，博士生导师。华中科技大学即时定制研究所副所长，法国国家高等工业管理学院供应链管理研究所（ENSGI-GILCO）客座教授。研究方向包括物流与供应链管理、生产运作管理、现代项目管理和紧致化仓储等。主持和参加多项国家自然科学基金项目，其中1项国家重点项目，获得2013-2014年中国物流与采购联合会2项科技进步。
