基于动态订单约束的仓库拣货作业双层优化算法

王 磊，徐跃明，安裕强，叶 晓，潘 楠

（1.红云红河集团有限责任公司 物流中心，云南 昆明 650202；2.昆明理工大学 民航与航空学院，云南 昆明 650500）

0 引言

随着物联网技术的不断发展，物流行业步入智能化时代。仓储作业作为物流行业的重要环节，其作业效率直接决定了物流行业的运转速度。仓储作业主要由订单分配及拣货两大部分构成，因此如何实现高效合理的订单分配和拣货路径优化成为行业关注的重点。

在仓储作业问题中，已有不少学者对订单分配和拣货路径优化进行了协同研究，其中孙军艳，等建立了基于嵌套遗传算法的联合优化模型，通过外层不断优化订单分批结果，内层不断优化拣货路径，有效地提高了拣货效率，为解决仓储作业中的难题提供了有效依据。Cheng Chen-Yang ，等针对联合批次拣选和拣选路线问题，设计了混合算法对其进行求解。此外，有部分学者研究了仓库布局对拣货时间的影响，其中刘建胜，等研究了Flying-V型仓库布局下的拣货问题，并针对仓库布局特点设计了订单分配及路径优化模型，进一步采用蚁群算法对模型进行了求解，仿真对比结果表明该模型有较强的实用性。文献[8]则针对双区型仓库的布局特点，建立了以最短拣货时间为目标的优化模型，并设计了动态货物调整和人工拣货协同作业的动态拣货策略，采用混合遗传算法对模型进行了求解，仿真实验结果表明该策略在大规模订单时能够显著地提高拣货效率，但并没有考虑拣货辅助工具物理限制对拣货作业的影响。孙慧，等在拣货优化模型中引入了拣货车容量约束等实际约束，并通过仿真结果验证了所设计的模型有较强的实际应用价值。上述研究均取得了一定的成果，但没有涉及多服务台等仓库模式。为此，本文基于某企业的仓库布局，构建了涉及多服务台的订单分配及拣货路线优化模型，尝试解决相应问题。

基于上述分析，本文针对某物流企业的仓库布局特点，综合考虑仓库物理限制、拣货人员及辅助工具能力约束等实际约束，构建了涉及多货物种类、多订单、多服务台的包含订单分配和拣货路径优化在内的双层优化模型，并通过比较WOA（Whale Optimization Algorithm）、MVO（Multi- Verse Optimizer）和CSV（Crow Search Algorithm）以及改进CSV 的优化结果，选择改进群体智能算法进行订单分批优化和拣选作业路径优化。仿真实验结果表明，所设计的算法能够有效地求解人员拣货问题，相较于传统的遗传算法，能够进一步提高拣货效率，为加快传统物流企业智能化提供有效借鉴。

1 问题描述

某集团仓库作业主要包含订单分配和人员拣货路径规划两部分，其中订单分配除订单分批外还包含服务台分配，而人员拣货作业采用“人到货”的拣货模式，即货物位置固定不动，由拣货人员结合辅助拣货作业工具完成货物的拣选。订单分配的结果直接决定了拣货路径的生成，因此，本文通过构建双层优化模型对两部分进行综合优化，针对上述对问题的分析及企业的仓库管理策略，得到了以下假设：

（1）同一储位货物具有同质性；

（2）储位中心位置为该储位的坐标；

（3）员工的行走速度相同；

（4）每个储位的尺寸相同；

（5）每个巷道入口处左侧都有服务台；

（6）仓库处于动态补货的过程中，即货架的货物剩余量无限；

（7）升降机等辅助工具数量充足，即不考虑其行驶时间；

（8）货物在最大容量时未超过辅助工具的载重限制，因此忽略拣货容积限制。

表1 符号说明

2 模型建立

2.1 仓库布局介绍

仓库布局如图1所示，每个货位的位置由巷道数、所处巷道货位数、巷道左右侧及货位深度所决定(r,s,p,l,d)，其中，r为货位所处巷道数；s为货位所处巷道距入口序号；p为货位位于巷道左或右侧；l为货位层数；d为货位所处深度。

图1 仓库布局

在仓库矩形布局中，得到任意两个货位之间的距离，表示如下：

从任意服务台到任意一个货位的距离为：

2.2 双层优化模型构建

某集团的仓库拣货作业基于服务台开展，其整体作业效率的高低取决于服务台的合理利用与人员的任务安排，由于拣货订单采用批次处理，因此订单的分批及分配结果直接决定了服务台内员工拣货任务安排的合理性。综上，考虑到拣货订单存在同质性，因此基于相似度进行订单分批，在此基础上围绕仓库服务台作业公平性进行订单分配，并综合考虑仓库物理限制，最终建立以经过最少拣货通道、最高服务台公平性为上层优化目标的订单批次优化模型。

式（11）表示每个批次由一个服务台负责；式（12）表示每个订单只能分配给一个批次；式（13）表示货架能够满足该批次订单的品项需求；式（14）表示不超过仓库最大供应能力。

基于上层订单分批与服务台分配结果，以及每个服务台的作业情况，安排空闲员工进行拣货作业，综合考虑拣货作业人员的作业素质，拣货辅助工具的物理限制，以及货架的实际情况等真实约束，建立了以最短总拣货时间为下层优化目标的员工拣货作业模型。拣货总作业时间由员工行走时间和作业辅助工具升降机工作时间以及货物清点结算时间三部分构成，拣货作业人员作业过程中行走时间计算公式见式（15），拣货作业过程中升降机工作时间计算公式见式（16）。

式（21）表示拣货作业不超过最大人数限制；式（22）表示每个人负责一个批次；式（23）和式（24）表示在一个批次中货架只能被拣货一次；式（25）表示订单容量不超过拣货工具限制；式（26）表示单个订单的工作时间不超过拣货人员的最大持续作业时间；式（27）表示拣货人员完成拣货后返回出发时的服务台。

3 算法设计

3.1 设计思路

订单分批和拣货路径优化是拣货作业优化的重要组成部分。订单分批以所需货架总数最少为目标函数，每批次订单中货物的质量和体积不可超过拣货车的最大容积和最大载荷量。订单分批结束后，根据订单分批结果规划拣货路径，得到每批次的最优拣货路径。在实际生产活动中，大多数的仓库拣货人员大于1，因此得到各批次的最优拣货路径后，需要检查拣货过程中是否存在冲突点，总体框架如图2所示。

图2 算法设计思路

3.2 优化过程

3.2.1 订单分批。为了更好地使用智能优化算法求解上述模型，用矩阵索引号表示订单编号，矩阵中的数值表示分批批次。如，假设对10张订单进行分批，用“[1,1,2,3,4,4,2,3,5,2]”表示分批结果，其中第1、2张订单为第1批次，第3、7,、10张订单为第2批次，第4、8张订单为第3批次，第5、6张订单为第4批次，第9张订单为第5批次。确定拣货设备容量和体积限制，以及乌鸦数量、最大迭代次数（maxGen1）、矩阵维度（dim）、感知概率（AP）和飞行距离，具体优化过程见表2。

表2 订单分批问题伪代码

3.2.2 拣货路径优化。在拣货路径优化问题方面，采用矩阵索引号表示拣货员先后经过对应拣货位的顺序，矩阵中的数字表示某批次需要经过的拣货位信息。如“[1,2,3,8,23,45,32,34,12]”，表示依次经过拣货位1,2,3,8,23,45,32,34,12。确定自变量编码后，初始化鲸鱼种群数（SearchAgent）、变量维度（dim）、最大迭代次数（maxGen2）、系数向量A和c等，同时变量维度等于需要经过的拣货位数量。编码过程见表3。

表3 拣选路径优化问题伪代码

3.2.3 动态路径调整。当拣货人员数大于1时，由于拣货通道的宽度限制，极有可能发生堵塞现象，将文献[11]与企业的实际情况相结合，可将堵塞种类分为以下三种，如图3所示。

（1）一个拣货员需要经过该拣货通道前往目的拣货位进行拣货，另一拣货员在该拣货通道有拣货任务，如图3中的a所示。

（2）两拣货员在该拣货通道均有任务时，分为三种情况。两拣货员的目标拣货位位于拣货通道两侧，且都需要经过对方的目标拣货位，如图3中的b(1)所示。两拣货员的目标拣货位位于同一通道两侧的相邻位置，如图3中的b(2)所示；两拣货员到同一通道拣选货物，如图3中的b(3)所示。

（3）两拣货人员在该拣货通道均无拣货任务，但需要经过同一拣货通道到达目的拣货位，如图3中的c所示。

图3 路径冲突类型

当遇到以上列举的情况时，为避免造成拥堵，需要进行路径调整，本文基于动态规划思想，以拣货人员到达相邻两货位的时间为单位，检查是否存在冲突点。根据文献[12]，当员工拣选速度为1.39m/s 时，物流拣选劳动者平均每工作48min 后，需要休息6min，由此每当有拣选员完成任务时，需要检查员工的累计工作时间是否达到48min，若达到48min 则需安排该员工休息，具体过程如图4所示。

图4 路径调整流程图

4 实例分析

4.1 仓库模型

仓库布局如图5所示，该拣货区由5条拣货通道、4 条巷道、160 个拣货位组成。为每个拣货位进行编号，图中D表示拣货通道宽度，D表示拣货位宽度，D表示拣货位长度，D表示巷道宽度。出入口位于拣货位1、40、41、80、81、120、121附近。

图5 拣货区平面布局图

4.2 订单分批

对随机产生的10张订单，分别采取鲸鱼优化算法（WOA）、乌鸦搜索算法（CSV）、多元宇宙算法（MVO）以及改进乌鸦搜索算法对模型进行求解，对比结果如图6所示。

图6 收敛迭代曲线图

由图6可知，MVO收敛最快，改进算法收敛速度最慢，但是优化效果最优，同时由表4可知，尽管WOA和MVO 的优化效果较好，但是二者在进行仿真时CPU响应时间远长于改进算法，当订单规模较大时，无法及时满足生产要求。

表4 CPU响应时间

4.3 拣货路径优化

随机生成10 张订单，其中每张订单中都包含10个货物品项（即10个不同的拣货位），分别采用遗传算法（GA）、鲸鱼优化算法（WOA）、乌鸦搜索算法（CSV）和多元宇宙算法（MVO）计算10 张订单的拣选距离，对比结果如图7所示。

图7 收敛迭代曲线图

以第一张订单为例研究各个算法的收敛性，收敛结果如图7所示，由图7可知乌鸦搜索算法收敛性最好，遗传算法的优化结果最优。图8为在使用各个算法对10 张订单进行路径优化时，计算机CPU 响应时间。由图8可知，遗传算法的计算时间最长，鲸鱼优化算法（WOA）、乌鸦搜索算法（CSV）和多元宇宙算法（MVO）的计算时间相近，且远少于GA。尽管利用GA可得到最优结果，但是CPU 响应时间远多于其他算法，无法满足实际生产要求，因此选择优化结果次优的WOA。

图8 CPU响应时间

4.4 路径调整

随机产生20张订单，共有4名拣选人员。20张订单进行分批后，对分批结果进行路径规划，最终各批次优化后的拣选距离及拣选时间见表5。

对表5中的优化路径进行预研究，将拣选任务分配给4名拣选人员，以经过一个拣货位的时间为单位，检查拣货过程中是否存在拣货冲突，若存在冲突点，则按照优先级调整路径，调整结果见表6。

表5 路径优化结果

表6 路径调整结果

由表5和表6可知，单人完成拣选货物所用总时间为18.29min，多人拣货时间为24.57min，完成拣选任务需要6.69min。尽管单独完成部分批次订单拣选时间相较于调整前较长，但多人拣货完成任务的总拣选时间明显更短，效率更高。同时多人拣货时基于人因工程考虑了每个人的最佳工作时间，并且达到一定的工作时间后，为工作人员设定合理的休息时间。

5 结语

本文针对某物流企业的作业要求，对订单分配和拣货路径问题展开研究，构建了以最少总货架数、最大服务台公平性为上层优化目标，以最短总拣货时间为下层优化目标的双层优化模型，并综合考虑了仓库物理布局、人员及辅助工具能力约束等实际作业约束，相较于传统的模型，本文所构建的模型有更强的实用性，并通过比较MVO、WOA、CSV和基于WOA气泡网围捕机制改进的乌鸦搜索算法在解决订单分批时的优化效果，最终选择改进算法求解上层优化模型，选择WOA求解下层优化模型。同时针对拣货过程中可能出现的路径冲突，提出相应的调整策略，避免员工在拣货过程中出现阻塞，影响通行。仿真实验结果表明，在订单分批问题方面，本文所设计的算法相较于WOV、MVO和CSV等算法，在收敛速度和计算时间方面都有较为理想的效果，因此更能有效地求解物流企业的仓储作业问题，为推动行业智能化发展提供有效借鉴。