半自动化仓库内订单分批优化研究

项 溪，唐仕青，徐晓威，宫 琳，刘 欣 （北京理工大学 机械与车辆学院，北京 100081）

0 引 言

近年来，我国电商行业发展迅速，移动支付普及得越来越广泛，网购交易规模增长甚猛。国家统计局数据显示，2021年全国电子商务交易同比增长19.6%，对应全年1 083.0亿件的快递业务支持[1]。面对如此巨量的订单，仓储物流效率成为决定电子商务服务品质的重要环节[2]。公司为应对日渐加剧的市场竞争，努力保持订单履行的高度及时性，以确保为消费者提供高质量的网上购物体验。然而，这给仓库的订单处理带来了越来越大的压力，据统计，传统配送中心内，拣选作业成本占总成本的60%、订单处理时间占比达30%~40%，订单拣选已成为制约电商发展的物流瓶颈[3]。订单分批处理则是提高订单拣选效率的一种常用方法，将若干个订单分批成组，将每批订单依次委派给拣货员，每批订单由单个拣选员通过巡回拣货完成拣选任务。

经典的订单分批问题（Oder Batching Problem, OBP）只考虑商品的种类和数量，通常结合仓库的布局转化成拣货员的路径优化问题，OBP已经被证明是NP-hard的。吴天行等对OBP提出了人工蜂群算法求解，并创新性地结合“反学习”理论提高算法的收敛[4]。王转等面向“人到货”系统提出启发式拣货策略，以批次里程节约量之和最大化为目标，提出D-eco分批算法求解，补充了物流中心实际操作问题的解决方案[5]。陈彦博等面向多区块、多通道、多交叉点的仓库系统，以拣选员的总行走距离最小化为目标，提出针对大规模问题的分支定价算法，并结合实际电商仓库运作案例给出算法可行性证明[2]。黄敏芳等受JIT装配流水线思想启发，考虑订单在并行分区的拣选和批次的排序两流程之间受到的制约，提出两阶段启发式优化方法，实现流程工序的均衡[6]。张国维等就AGV仓库订单分批问题，以搬运和拣选成本最小化为目标，提出交替选择的贪婪算法求解，并与CPLEX比较了求解误差[7]。

已有研究不断丰富了OBP的应用场景和模型细节，并在求解上对算法进行了不断的创新，但模型的复杂度往往过高，以致于难以快速处理较大规模的分批订单。另一方面，现有研究往往只关注单一拣选员的拣选路径规划问题，而对考虑仓库布局的多人并行拣选的订单分批问题研究甚少。综上，本文考虑一种“人到货”半自动化仓库的布局及运作方法，针对订单分批处理，提出了一个混合整数规划模型，并使用Gurobi作为MIP求解器对模型进行算例验证。

1 问题建模

本节提出了一种半自动化仓库的布局模式及运作方法，并构建了相应的数学模型。

1.1 问题描述

本文基于仓储布局提出一种“人到货”仓库采取多人分区、并行拣选的运作策略。考虑如图1所示的半自动化仓库布局：矩形仓库内设有垂直于墙面的平行过道。每条过道的两侧安装有从墙面出发的货架，货架上有连续不断、用来临时存储货物的方形货槽，并且每个槽内只允许盛放同种商品。在货架尽头及与之靠近的墙面之间设有传送带，传送带在经过过道时，会以一定的功率持续不断地将拣货员拣出的出库货物传输到缓冲区。缓冲区的分拣员则需注意及时取出商品并按订单所需要的组合放在一起，最后将订单打包出库。此处将订单定义为客户所需商品的清单，包括商品的指定类别（本文以SKU ID表示）和各类别所需的数量。

图1 半自动化仓库的布局及运作模式

基于该半自动化仓库的布局，本文考虑采用多人订单拣选模式，如图2所示。

图2 多人拣选模式

首先分析单个订单的拣选流程。拣货员执行“获取订单→检索商品位置→取货→搬运”的操作步骤。开始之前，所有拣货员都在各过道的传送带处等待，订单抵达系统时，转化为取货清单，清单内包含各商品所在的过道及货架等具体位置信息。拣货员收到清单后，迅速开始移动，通过在过道内的一次往返，就拣出全部目标商品；对于没有取货要求的过道，拣选员则需在起点处保持等待，直至整个仓库进入下一订单的拣选。取货时，拣货员用手推车搬运拣出的商品，回到起点后卸货至传送带上，通过传送带将拣选出的商品传输至缓冲区。当所有拣货员都完成卸货时，定义本订单的拣选结束，接下来仓库进入下一订单的拣选。由于订单结构的差异性，这种逐单件拣选的模式会造成巨大的人力浪费和大量订单延误。因此，实际电商仓储选择采取分批拣选方式。

订单分批即拣货员们在过道内一次往返时需要处理多个订单，如图3所示。当一个订单涉及多个通道的拣选时，由多个对应通道的拣选员分别执行拣选。当若干个订单被分到同一批次拣选时，由多名拣选员在各自的过道内分别对多个订单内的多个商品进行拣选。拣选员拣出的商品经传送带抵达缓冲区时，分拣员将其逐个捡出，并根据订单组成将商品打包。

图3 订单分批处理的流程示意图

当系统面临大批量订单涌入时，对订单进行逐一单件拣选将会造成拣选员的重复行走，增加移动时间；如果将大量订单合并拣选，虽然会缩短拣货员的行走时间，但也会大大增加分拣员的工作负荷。因此本文的研究目标旨在为实时变化的订单需求，找到快速合理的订单分批方法，使系统内订单的总处理时间达到最小，提高电商仓库的订单处理效率。

1.2 模型构建

1.2.1 模型假设

每个订单不允许被拆分到不同批次；每个过道有且仅有一名拣货员；拣货员在过道中进行往返时手推车的容量是固定且相同的；订单是固定时间窗口内的全部累积订单；不考虑临时插入的新订单。

1.2.2 符号说明

在研究模型的描述和建立之前，首先给出符号如表1。

表1 符号说明

1.2.3 目标函数

考虑订单的实时性需求变化，往往需要根据实时需求进行动态分批，通常会设置固定时间窗，对时间窗内累积收到的订单进行分批优化，通过时间窗的平移，实现对长期需求变化的动态分批。而对于电商仓库而言，其首要目标往往是提高订单处理效率而反映订单处理效率最主要的指标就是处理时间，因此本文将系统固定时间窗内累计订单的总处理时间最小化作为主要优化目标。

如果系统采用订单分批方法，则目标等价于使全部批次的总处理时间最小化，即系统拣选时间与分拣执行时间之和最小。

1.2.3.1 系统拣选时间

相较于检索和行走时间，拣选员拾取货物的作业时间几乎可以忽略不计，因此拣选时间等于对商品的检索和在过道内行走所需时间。

假设各过道拣货员的移动速度相同且保持不变，仓库内货架的长度一致，为在过道j中取走本批次所需全部商品所经过的距离，由于拣选员的移动方式是在过道内进行一次往返，因此其移动时间为。同时考虑过道j的拣选员拿到清单后对商品的检索时间，则总拣选时间为：

将各过道拣货员的最长用时定义为系统对批次的拣选时间，于是批次k的总拣选时间为

当要求Tkp最小时，式（2）等价于

1.2.3.2 分拣时间

分拣时间等于将商品还原为订单要求的组合并对订单进行打包这两部分的时间之和。分批k包含的订单总数为Σo∈Oyok，所包含的商品总数为Σo∈OCo·yok，因此，

综上，目标函数应为

1.2.4 约束条件

对于订单分批问题，本文考虑有如下约束条件。

其中：约束（6）和（7）用来生成商品、订单和批次之间的子集关系；约束（8）用于保证每个订单在同一批次内；约束（9）计算各道拣选员的行走距离，并选出其中的最大值；约束（10）表示在整个仓库中，批次内商品总量不超过推车的总容量；约束（11）声明决策变量为0~1变量。

2 算例分析

为了检验前文所述模型的可行性，本文基于新加坡NTUC FairPrice药品仓库Unity的真实订单数据与文献[8]的算例进行数值实验。所有实验均在Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz上完成，使用Gurobi 10.0.1作为MIP求解器，所有代码均在Python 3.11上编写并运行。

2.1 算例生成

首先基于新加坡NTUC FairPrice药品仓库Unity的真实订单数据和文献[8]的算例，对于实验中所涉及的参数说明如表2所示。

表2 算例部分参数生成

2.2 实验结果及分析

基于表2算例参数及真实订单数据，分别进行了五组实验，分别在商品种类数量为40、60、80、100、120时进行不同订单规模的数值实验。同时考虑到混合整数规划求解的难度，将Gurobi求解器的TimeLimit参数设置为120 s，求解结果如下表所示。

表3 不同商品种类及订单规模下的Gurobi 求解结果

本文又进一步分析了不同订单规模下解的质量，即Obj和Gap的影响。绘制出折线图如图4所示。

图4 不同规模下求出的Obj 和Gap

从图4可以看出随着订单规模的扩大，订单总处理时间增多，但求出最优可行解的Gap仍稳定在一定的数值范围内；同时，商品种类的增加也会延长订单的总处理时间。总的来说，随着商品种类和订单规模的增加，模型的复杂度提升，但解的质量仍旧保持相对稳定状态，说明本文所建立模型对中小规模订单处理的性能较好。

3 总结与展望

为满足复杂环境下实时性变化的需求，本文提出了一种动态订单分批的思路，并建立了一个针对中小规模下订单分批问题的混合整数规划模型。本文的研究结果可以集成到仓储管理系统（Warehouse Management System, WMS）中，从而有效应对订单激增等变化，对提高仓库的订单处理效率具有重要作用。考虑到实际业务流程，本文的研究还存在一些不足，例如还需考虑订单的截止日期、紧急订单的插入等问题，此外本文的订单分批问题还可与储位分配等问题进行联合优化。