具有劳动异质性的订单分批优化研究

徐兆峰，姜雪松，李春伟，王 婧

（东北林业大学机电工程学院，哈尔滨 150040）

0 引言

近年来，越来越多的实体超市，如永辉超市、盒马生鲜、物美等，开始将传统的实体销售渠道与数字销售渠道整合，这也被称为O2O超市（online to offline）。O2O超市是利用现有的大型实体超市作为仓储配送中心，为客户提供准时、便捷的送货上门服务。拣选商品作为仓储配送中心出库作业的终点、超市配送的起点，其作业效率是超市提高配送效率和顾客满意度的关键［1］。在拣选作业中，通常会遇到大量相似度高的商品未能有效合并，实际拣选作业中大规模订单未能合理安排，拣选员工实际效率不高的问题。对于近几年文献提出的订单分批的解决方案，发现大多数相关研究都假设在配送中心的拣选员工都有着相同的拣选能力。对于超市仓储配送中心，专业的拣选员工将创造更多利润［2］。但是这种行业往往有着更多兼职，即临时的工组人员，这种具有劳动异质性员工的出现使工作平衡就变得尤为重要，因此对仓储配送中心的订单分批、拣选员工之间平衡的研究具有重要的现实意义［3］。

对于商品拣选员工来说，拣选商品是一种特殊的旅行商问题，其中拣选员工从入口到出口形成一个闭环拣选路径，并且目标为行走距离最短。Difrancesco等［4］发现，对于员工工作平衡问题的关注显得更加突出。Koch等［5］发现忽略劳动力异质性可能会影响整体生产效率。朱友琼等［6］根据订单相似度建立订单分批模型。在完全确定拣选系统中，旅行商也可以表现出混沌行为［7］。陈彦博等［8］在S型策略的基础上，提出一种定价分支算法对问题进行求解，保证在既定规则下的最优拣货路径。还有很多学者从员工拣选平衡［9］、员工学习能力［10］、员工拣选方式等［11］方面对问题订单分批进行研究。目前，超市常用的拣选路径策略主要为S型策略［12］。刘晨旻等［13］采用萤火虫算法求解最短拣货路径，结果表明其适合于大型仓储拣货路径优化。刘晨旻等［13］的作业负载平衡问题与上述研究的不同之处是，它是按时间（即每天）来平衡工作负载，而不是在区域、拾取者或批次之间进行平衡的。因此，Zulj等［14］主要在拣选订单的背景下研究工作负荷峰值。

综上所述，目前对于订单分批问题结合平衡工作负载已经有了相关的研究，但是没有考虑拣选员工之间的差异性对于订单拣选的影响。大部分超市配送中心在拣选商品时存在没有合理的分批订单和考虑拣选员工之间存在的差异性会影响工作平衡。在此背景下，综合考虑具有劳动异质性的员工和订单分批问题，提出拣选员工行走的最小距离、最大化拣选员工工作量平衡的双目标混合整数非线性规划模型，并通过改进萤火虫算法进行求解，仿真验证其结果的可行性。

1 问题描述及数学模型

1.1 问题描述

本文研究面向以超市为仓储配送中心的订单分批和具有劳动异质性的拣选员工拣选平衡问题，并通过对现有常用的订单到交付通道的指派规则，即先到先服务（first come first served，FCFS）指派规则进行分析，来获得使拣选员工行走距离最小、员工拣选最平衡的订单分批策略。工作流程为拣选员工需要等待订单信息的到来，然后根据分批后的订单信息从入口进入商品区拣选对应的商品，等商品拣选完成后打包发送。配送流程如图1所示。

图1 配送流程图

传统的FCFS方法已经不能满足超市拣选的需求，过多的拣选时间将导致订单延误风险的增加。在这种动态竞争中，随着具有劳动异质性的拣选员工的出现，专业的拣选员工总是快速拣选完成后等待订单的到来，而业余的拣选员工总在根据订单拣选，所以拣选员工平衡问题已经成为超市仓储配送中心拣选商品的重要问题。

1.2 模型构建

超市配送仓库由12条通道和300个仓位组成，起点和终点都在左下角，所研究的仓库布局图如图2所示，模型参数如表1所示。为了简化描述，模型的假设条件如下。

表1 模型参数

图2 仓库布局图

1）每个仓位的物品都不一样，并且物料充足。商品质量：1—100号为1 kg，101—200号为2 kg，201—300为5 kg。每个小推车最大承载量为100 kg。

2）每个订单都不许拆开，只能一起拣选并放到一个订单批次内。

3）拣选员工必须按仓位顺序拣选，不可跳着拣选商品。如果订单只有一个商品，那么拣选员工需要在拣选商品完成后原路返回，返回入口0。

4）在货架上寻找和拣选物品的时间与每个拣选员工对特定存储位置的熟悉程度高度相关，并在数学模型中明确考虑这一因素。

构建订单分批优化模型，第1个目标主要是高效及时地完成订单拣选，第2个目标旨在使具有劳动异质性的拣选员工的工作更加平衡。双目标混合整数规划模型为：

式（1）和式（2）为所提数学模型的目标函数，即拣选员工行走的最小距离和拣选员工工作量最平衡；式（3）约束了每一批次订单的总质量不得超出小推车的载重量；式（4）约束了每个订单商品的质量不得大于小推车的载重量；式（5）和式（6）保证一个订单只能出现在一个批次里；式（7）为每个员工的拣选能力。假设拣选时间遵循学习曲线，并且进一步假设学习发生在单个项目级别，因此越频繁地拣选物品，拣选员工就越能记住该物品的位置，并且搜索时间越短。搜索时间为：

S形路线的批次的总行进距离为：

式（2）的模型系数允许拣选员工以以下方式表示：具有β1，w的拣选者，w表示能力强的人；具有β2，w的拣选者，w表示能力弱的人；拣选员工的平均批处理执行时间随着订单数、行进距离的增加而增加。这些都是合理的，随着工作量的增加，时间自然也会增加。较高拣选水平的员工拣选更快，这表明根据拣选能力来进行订单分批处理，使拣选商品的效率更高。

2 算法设计

2.1 萤火虫算法

萤火虫算法属于种群智能优化算法，每只萤火虫都可以看做一个问题的解。这种算法就是通过模拟萤火虫的发光行为而提出的，所以实际上其原理很简单。为了方便算法的描述，需要3个理想化的假设：

1）所有萤火虫雌雄同体，都能被其他萤火虫所吸引；

2）萤火虫的亮度受目标函数影响或决定，对于最大化问题，亮度可以简单地与目标函数值成正比；

3）对于任意2只闪烁的萤火虫，较暗的那只会朝着较亮的那只移动；

需要满足不得超过小推车载装量的限制，因此订单分批方案的总成本计算公式为：

式中：a为萤火虫个体，代表订单分批方案；f（a）为萤火虫个体转化成订单分批方案的总成本；c（a）为拣选工作行走的距离；q（a）为各批次订单违反小推车的装载量之和；∂为违反装载量权重。

在使用萤火虫算法解决连续优化问题时，第a只到第b只萤火虫的距离为：

在牵引力作用下，萤火虫在可见范围内向比它们自己更亮的个体b移动。位置移动的公式如下：

式中：x（t）为个体a在t的位置；α为步长因子，恒定范围为［0，1］。

2.2 动态自适应步长改进萤火虫算法

虽然萤火虫算法有明显的优点并受到许多研究者的青睐，但与其他启发算法一样，它也存在一些不足。例如，在高维条件下，算法很容易陷入局部最小值，并且由于吸引力的减弱而降低了解的性能。为此提出了一种动态自适应的萤火虫优化算法，加入动态步长调整因子，随机改变算法的步长，防止算法陷入局部最优。该策略能有效平衡算法，提高算法的收敛速度。

标准FA是根据高亮度萤火虫和低亮度萤火虫之间的吸引力来更新位置的。由于萤火虫的可视范围有限，因此低亮度萤火虫只能在其可视范围内找到可移动的高亮度萤火虫。对于标准萤火虫算法，步长因子α是常数。这意味着在迭代中，步长因子α是一个固定值，没有考虑后期个体之间的距离随着迭代次数的增加而不断减小，因此固定值α容易导致算法产生“振荡”。步长因子α的取值对算法的搜索能力有很大的影响。通过分析和实验发现，α值越大，全局最优性越好，但在算法后期不容易收敛。α值越小，收敛越好，但容易陷入局部最优。

为了使演化过程更有效，在优化过程中引入动态阶跃因子机制，将α控制在一个区间［αmin，αmax］，并使该值与优化的距离偏差程度相适应，从而提高求解精度和收敛速度。同时，为了增强种群的灵活性，采用均匀分布随机因子对α进行定向随机化。新算法中α的取值公式为：

式中：αmax、αmin分别为最大步长和最小步长。经过大量的实验测试，当αmin＝0.5，αmin＝0.1时，优化效果最好。萤火虫个体分散在整个空间中，大多数萤火虫个体与全局最优个体之间存在较大距离。为了防止算法因α值过小而陷入局部极值，加入了向最好萤火虫移动的方法，即最好的萤火虫在其搜索方向上采用大步长线性加速，剩下的萤火虫采用线性减速移动，Δ＝（max－min）／最大迭代数＝1。

根据上述分析，步长因子α根据萤火虫个体间的距离自适应动态变化，平衡了算法开发和搜索的能力。

本文采用动态自适应步长改进萤火虫算法的终止条件为迭代出最优的目标函数值，如果满足终止条件，那么输出最短行走距离和订单分批出的具体订单。改进后的算法解决订单分批流程如图3所示。

图3 动态自适应步长改进萤火虫算法解决订单分批流程图

3 仿真实验与结果分析

3.1 实验参数

为了验证改进的萤火虫算法可以更好地解决订单分批和拣选员工工作量不平衡的问题，采用模拟仿真方法进行了一系列数值实验。超市布局和订单特征等参照相关文献和现实调研情况设定。以永辉超市（YH）配送中心实际订单数据为例，假设在1个时间窗口内累积了20个在线订单。可用的拣选订单的工作人员的最大数量应大于在1个时间窗口中累积的订单总数。可供拣选订单的工作人员为10人，因为员工具有劳动异质性，其中一些员工接受了拣选订单的培训，另一些为零时工。

式中：t2＝1表示初学者的初始搜索时间；LRp＝0.95表示搜索时间的个体差异；k为先前选择的累积项。将k设为100、500和1 000，表示个人的技能熟练程度。设置了2个经验丰富的拣选人选（k＝1 000）、4个新员工（k＝500）和4个临时工（k＝100）。每名采摘者的行走速度为40 m／min。

本文采用随机的方式构建初始种群，初始种群的任意1只萤火虫个体都是（N＋K－1）的随机排列。在使用改进萤火虫算法解决连续优化问题时，第i只萤火虫与第j只萤火虫之间的距离为求出2只萤火虫对应位置上不同元素之和，并且把2个目标函数看成2只萤火虫之间的相互吸引。我们随机拣选永辉超市（YH超市）配送中心的20个订单数据，通过应用Matlab软件进行多组仿真验证。输入基础参数、初始化定义、订单数据后，开始仿真验证，求出最优订单批次。订单数据如表2所示，基础参数如表3所示。

表2 订单数据

表3 基础参数

3.2 小规模实验分析

订单分批策略定义了如何将消费者订单分批到单个拣选流程中。FCFS策略为与改进FA策略比较的基线，并且还与基本FA策略和种子策略进行比较。种子分批策略首先选择顺序最小种子通道的数量，然后添加客户订单，使需要通过额外仓库通道数量最小，直到拣选的产品总数达到分批处理量。先前的研究已经证明了种子分批策略可以产生高效的订单分批解决方案。FCFS和种子分批策略产生的订单批次首先分配给专业的拣选者，然后给其他的员工。研究的目的是实现双目标拣选订单，使超市的利益最大化。尽管有各种复杂的启发式方法来解决订单批处理和分配问题，但增加的计算时间和复杂（或简化）的假设可能会阻碍它们在实践中的应用。

实验的程序运行环境：处理器CPU为R7，主频为3.40 GHz，操作系统为Windows10，开发环境为MatlabR 2022b。改进FA算法的步长因子在［0.5，0.1］区间，经过100次迭代结束。

在订单分批问题中，超市仓储配送中心采用的是先到先拣选的策略。在相同拣选S型路径的策略下，分别对比FCFS策略、种子策略、FA策略和改进FA策略。在订单数据表2的20个订单数、85个商品的条件下，得出的订单分批不同策略对比如表4所示，拣选距离对比迭代图和员工拣选平衡图如图4、图5所示。

表4 不同策略对比表

图4 拣选距离对比迭代图

可以看出，在4种分批策略下，拣选员工行走的距离分别为749、630、628、568 m，而拣选员工的平均工作平衡率为75.1%、77.1%、85.0%、88.3%。改进FA策略与其超市仓储配送中心采用的FCFS策略（基准）、种子策略和FA策略相比都有所降低，拣选员工拣选距离分别降低了24.1%、9.8%、9.5%；而拣选员工的平均工作平衡率分别提高了17.6%、14.5%、3.9%。综合来说，改进FA策略与现阶段超市仓储配送中心采取的FCFS策略、FA策略和种子策略相比，拣选效率有着明显的提高。

3.3 大规模实验分析

为了减少因订单数据以及商品数据数量少的偶然性，将随机选取的YH超市50个订单进行订单分批实验。所有的参数变量都和以上分析一致，得到的不同策略对比如表5所示，拣选距离对比迭代图和员工拣选平衡图如图6、图7所示。

图6 50组订单拣选距离对比迭代图

图7 50组订单员工拣选平衡图

可以看出，随着订单数据的增加，改进FA策略改善订单分批的效果更加明显，比FCFS策略和种子策略分别降低了21.4%和21.9%。但是在工作平衡方面，随着订单的增加，拣选员工拣选单批订单行走的路程增加，工作量平衡率大幅降低，尤其是种子策略，甚至分批订单数已经超过了拣选员工数量，只能进行下一次拣选，这对于拣选效率无疑是大大降低的。简单来说，改进FA策略并不能保证在工作平衡方面做到极致，在8批订单中，80%都高于FCFS策略。总的来说在订单窗口正常接单、无员工恶意旷工的情况下，改进FA策略是可以提高超市仓储配送中心的拣选效率的，可以使拣选员工更有效率、更平衡地拣选商品，提高总体效率。

4 结论

本文对O2O超市仓储配送中心的订单分批和拣选员工工作不平衡问题进行了描述，结合现有的研究提出了双目标混合整数型模型。由于超市线上订单数量巨大，商品种类丰富，因此采用改进FA算法求解优化模型。

首先为解决双目标混合整数模型，在算法设计中采用均匀随机分布步长因子和最好的萤火虫搜索方向上采用线性加速，剩下的萤火虫采用线性减速移动的方式改进萤火虫算法，并且利用萤火虫相互吸引的特点；然后通过Matlab仿真验证模型及算法，设计多组数值实验，在20个订单实验中验证了模型的可行性。为了避免数据过小存在随机性，采用50组订单实验、200多个商品进行验证；最后通过实验表明改进FA策略可以较好地解决所提模型存在的求解问题，并且改进FA策略比FCFS策略、种子策略在求解上更具有优势。

综上所述，本文是对O2O超市仓储配送中心订单分批问题改进的初步尝试，但关于此方面的研究并没有考虑到拣选商品的一些复杂的操作特征，如商品位置的不准确性、后台库存数据更新不及时，以及不同区域拣选中存在的问题，所以希望未来的研究可以建立相对应的模型给予解决。