不同订单分配和算法下的拣货路径优化组合

孟 鑫，杨 琴 ，4，郝婷婷，张 洁，曹策俊

1.四川师范大学 商学院，成都 610101

2.长安大学 经济与管理学院，西安 710054

3.重庆工商大学 商务策划学院，重庆 400067

4.四川工商学院 经济管理学院，成都 611745

1 引言

随着网络购物的现象日益普遍，人们对物流配送行业倍加关注。配送中心的拣货作业过程是典型的劳动密集型，据了解，单件产品的拣货作业成本占配送成本的30%～40%之多，拣货作业劳动量占仓库总作业量60%，并且作业时间占到总时间的40%[1]。虽然仓库拣货作业趋向于无人化，但无人化技术的推广需要投入大量资金，现阶段无人仓还未完全普及，所以绝大部分的仓库仍处于人工仓。仓库拣货作业一般分为两个步骤：一是分配客户订单，产生拣货单计划；二是由拣货员进行商品拣取任务。前一个步骤执行过程中，不合理的订单分配方式会引发订单周期较长、商品错误率高等问题；后一个步骤中，不合理的路径规划会产生较多不必要的重复行走路线，导致搬运成本增加。因此，合理规划仓库中的拣货作业环节，提高拣货作业效率具有研究价值。

目前已有国内外学者针对仓库拣货作业中存在的问题进行了大量的研究和分析。从订单分配层次，Khojasteh 等[2]就如何在最短时间内完成客户订单检索这一问题描述成一个非线性规划模型，讨论了一个多通道自动化仓库中的订单拣配问题。Bozer 等[3]运用两种订单拣选系统（Miniload 系统和Kiva 系统）处理同一组客户订单，得出预期的检索时间。王旭坪等[4]构建以总服务时间最短和分区均衡度最优的双目标订单合并优化模型，研究如何合理进行订单合并优化。卢烨彬等[5]创新性地将引力模型应用到波次划分模型中，以波次内不同储位商品之间的引力大小衡量订单之间的相似度，从而进行订单的波次划分。拣货作业路径规划是否合理直接影响拣货作业的效率和人工成本，因此，研究者致力于优化拣货作业路线。Lu 等[6]任务订单的拣选是影响仓库业绩的关键因素，并提出了一种干预路由算法来解决动态路径规划问题。Hong等[7]介绍了一种采用S形路由方法并行-过道订单拣选（SRSB）的路径选择订单批量模型。郭兴海等[8]提出了一种两阶段的全局路径规划方法，促进了无人仓库高效运转。孙军艳等[9]提出并设计动态货位调整与人工拣货协同作业的动态拣货策略，针对双区型仓库，以拣货时间最短为目标函数构建数学模型，进一步提高拣货效率。王转等[10]构建基于节约里程的订单分批模型，有效地减少了拣货行走总距离和平均行走距离。

然而，少有学者同时从订单分配方式和路径规划两个层次对拣货作业规划进行研究。所幸，已有学者注意到上述差距。Giannikas 等[11]介绍了一种动态的拣货策略，在拣货周期中更新拣货路线和订单分配。王华东等[12]采用订单动态时间窗分拣策略，仓库拣货路径优化算法，重点对跨境电商保税仓库拣货流程进行分析与优化。基于此，本文的主要工作有：（1）针对不同订单分配方式下的拣货路径规划问题，以京东典型的双区型仓库为例，建立与之相适应的路径规划模型，并设计了算法——S型启发算法和遗传算法。（2）通过算例仿真，将不同订单分配方式下的结果进行对比，并比较分析两种算法下的仿真结果。（3）选择最优的订单分配方式和算法，组合形成较优的仓库拣货作业规划。

2 问题描述

如图1所示，首先确定了两种拣货方式，即单一拣货与批量拣货。其次，运用三元组α/β/γ 方法分析拣货路径规划问题特征与布局特点。然后根据双区型仓库的布局特点，建立以最小化拣货路径为目标的路径规划模型。最后，设计两种算法（S型启发式算法与遗传算法）进行算例仿真，对比两种算法下的路径，得出最优解。

图1 仓库拣货作业设计过程图

2.1 两种拣货方式

单一拣取即在同一时间，一名拣货员只拣取一个客户订单，一个客户订单相应形成一个拣货单，拣货员拣取完成后，可直接打包配送至客户。本文假设每一个订单中商品总量都小于或等于拣货车的最大装载商品数量，即一个订单只能够用一辆拣货车拣取。

批量拣取是将一些客户订单中的待拣商品集中起来在一张拣货单上呈现，并只由一名拣货员拣取，这减少了很多不必要的重复行走路线。由于拣货车的最大装载商品数量有限，且假设每一客户的订单不允许分割，若总订单中商品数量较大，则需要进行订单分批，使得每批订单中的商品总量都小于或等于拣货车的最大装载商品数量。本文采用订单包络算法[13]对总订单进行分批处理。

2.2 拣货路径规划问题与布局特征分析

（1）资源环境（α域）：拣货员从仓库的进/出口出发，按照拣货单去各个不同的货位拣取商品，直到拣货单上的所有商品拣取完成，回到仓库的进出口位置，意味着一次拣货作业的完成。结合调度理论在服务业中的应用，在这种情形下，仓库中的商品是资源，而对拣货员的路径规划服务是任务。（2）任务特征和约束（β域）：拣货员从仓库进出口出发，拣取完商品后，返回仓库进出口，具有再循环的特征。在问题中，存在一系列约束条件：拣货车有容量限制，一张拣货单的商品数量不能超过拣货车容量；任意两个待拣商品之间只有一条路线等。（3）调度目标（γ 域）：本模型的主要目标为最小化拣货路径。

3 拣货作业路径规划模型

在对客户订单的处理过程后列出相应的拣货单，拣货员拿着拣货单推着拣货车从仓库进/出口到各个待拣商品的储位拣取相应的商品，直到将拣货单上的所有货品拣取完，返回仓库进/出口。本文根据京东典型的双区型仓库布局的特点，建立以最小化拣货路径为目标的路径规划模型。

3.1 基本假设

假设1N为仓库中的总储位数，每个储位只能存放一种商品，一种商品只能放在一个仓库储位上。

假设2每一张拣货单最少有一种商品，最多包含Q种商品（Q为一辆拣货车的最大装载商品数量）。

假设3每位拣货员在同一时间内只负责拣取一张拣货单，每个拣货单中的商品数量不得超过拣货车的最大装载商品数量Q。

假设4在同一条巷道中拣货时从一边的储位转身另一边储位的距离忽略不计。

假设5拣货单上的待拣商品在仓库中均不缺货。

3.2 参数设置

建立数学模型的部分主要相关参数如表1所示。

表1 符号说明表

3.3 路径分析

对客户提供的商品订单进行处理后，形成多张拣货单，一张拣货单只能由一名拣货员进行拣取任务。一张拣货单内有n种商品(n∈[1,Q]) ，每种商品需拣取qi个，且一张拣货单的商品总数量不能超过拣货车最大装载商品数量Q。

在本文的仓库设定中，仓库被分为东、西两个半区，有一条主通道、两条边通道，巷道垂直于三条通道，在巷道的两侧是装载商品的货架，未开封的商品放在高层货架上，需拣取的商品全部放在底层货架的储位上。拣货员凭借拣货单在巷道内对商品进行拣取，沿着每条通道都可以进入任意巷道内。仓库只有一个进/出口，拣货员从该口出发，拣货完成后需返回该口。进/出口正对西半区的边通道，巷道从离进/出口由近到远一次为巷道1至巷道10，商品的储位宽度为D1、巷道的宽度为D2、储位深度为D3、主通道的宽度为D4。设用[x,y,z]来表示每个商品的储位位置，商品所在的巷道数用x来表示；y表示商品储位序号，yi∈[1,b],1 → 0.5b表示商品在仓库西半区范围，0.5b→b表示商品在仓库东半区范围；z表示巷道两侧商品，z∈( 0,1) ，z为1 时，拣取巷道内距离进/出口较远储位的商品，z为0 时，拣取距离进/出口较近储位的商品。因为拣货员在同一条巷道中拣货时从一边的储位转身拣另一边储位的距离忽略不计，商品储位坐标可以用[x,y]表示。该仓库基本结构如图2。

图2 双区型仓库基本结构图

仓库内任意商品储位用坐标表示为：

根据商品所在位置有所不同，分情况写出了任意两个商品之间的最短距离dij的表达公式（i、j表示拣货单上任意两个拣货商品）。

（1）当拣货单上任意两个待拣商品储位分布在同一半区时，即，则求解dij可分为以下三种情况：

①当拣货区的任意两个商品的储位都在同一半区、同一巷道内时，即xi=xj，y1,y2∈[1 , 0.5b]ory1,y2∈[0.5b,b]，则dij可表示为：

②当拣货区的任意两个商品储位位于仓库西半区、不同巷道内时，即xi≠xj，y1,y2∈[1,0.5b]，则dij可表示为：

③当拣货区的任意两个商品储位位于仓库东半区、不同巷道内时，即xi≠xj，y1,y2∈[0.5b,b]，则dij可表示为：

由仓库进/出口到达任意商品储位点的距离d0i的求取公式可表示为：

则拣货作业过程的总路径D的函数可表示为：

决策变量：

d01与dn0分别表示在一次拣货作业过程中，拣货员从仓库进/出口到拣取的第一个商品的距离；从拣取的最后一个商品到仓库进/出口的距离。

3.4 模型建立

综上所述，拣货作业路径规划模型如下所示：

在模型中，公式（9）为目标函数，求解在一次拣货作业过程中拣货员行走的最短总路径；公式（10）和公式（11）分别表示拣货员拣货过程中从商品i到商品j和从商品j到商品i的总次数都为1，也就是说：任意两个待拣商品之间只有一条路线；公式（12）表示在一次拣货作业时商品总量不能超过Q；公式（13）为分段函数，分别表示任意两个商品的储位“位于同一半区、同一巷道内时”“位于仓库西半区、不同巷道内时”“位于仓库东半区、不同巷道内时”“位于在不同半区时”这四种情况下仓库中两个待拣商品储位之间的最短距离；公式（14）为分段函数，分别表示由仓库进/出口到达位于西半区和东半区中任意商品储位点的最短距离。

4 算法设计

在一个调度问题中当机器和任务人多时，求解一个最优解的计算时间是难以估算的，因此寻找一个能在比较短的时间内找到较好调度的启发式算法是非常有必要的[14]。因此，本文采用了两种启发式算法求解路径规划模型，即S型启发式算法和遗传算法。其中S型启发式算法是一种较简单基础的寻找较优可行路径的方法，操作简单，容易实现，在许多仓库管理系统中得到了广泛的应用，而遗传算法的基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法，是应用领域广泛、计算能力较强的全局优化算法[15]，由此，将S型启发式算法得出的结果与遗传算法的结果相比较，从而可验证遗传算法的有效性。

4.1 S型启发式算法

此算法在拣货过程中行走路线的思路是：从距离进/出口最近的通道出发进入存在待拣商品的巷道，（1）当存在商品在该巷道中的储位离所在通道的距离大于巷道的一半长度时，则拣货员从所在通道由近及远拣取该巷道内的待拣商品然后走过该巷道，从另一端巷道接着进入下一巷道继续拣货；（2）当不存在商品在该巷道中的储位离所在通道的距离大于巷道长度的一半时，则先拣取离所在通道距离最远的商品，再由远及近拣取该巷道内的商品并返回到原来通道进入下一巷道继续拣货；（3）如果该巷道上没有商品可拣取，则跳过此巷道进入下一巷道继续拣货。重复以上三个规则，直到完成对拣货单上的商品的拣取。

本文以双区型仓库为例，提出了S 型启发式算法的具体操作，如图3 所示：从最接近进/出口的西边通道出发，按离进/出口由近及远的巷道顺序依次拣取西半区的待拣商品，拣取完西半区的所有商品后，然后再从主通道开始按离进/出口由远到近的巷道顺序一次拣取东半区的待拣商品，拣取完东半区的所有商品后返回进/出口。因S 型启发式算法的操作简单容易实现，所以在算例仿真中采用手动计算规划出的拣货总路径。

4.2 遗传算法

（1）染色体编码。将染色体定义为由拣货单中的待拣商品种类基因组成，根据拣货单整理出待拣商品种数，在进行数值仿真之前首先为其进行编号，设n为拣货单上的待拣商品的种数，且每一种待拣商品编号唯一，待拣商品编号由两位十进制数表示，对每一商品都有其对应的拣货次序，如染色体“01，03，05，02，04”代表该拣货单有5 种待拣商品，对于编号03 的商品，它对应的拣货次序是2，也就是说拣货员第2 个拣取的商品是03。

（2）种群初始化。根据拣货单可知待拣商品上的种类、数量及位置编号，设计代码程序求商品储位点到进/出口的距离以及仓库中任意两个商品储位点的最短距离。在生成拣货作业路径规划方案时，随机生成一组m个包含n个待拣商品储位编码号的初始方案，并且分别计算目标函数值。

图3 S型启发式算法拣货流程图

（3）适应度函数。本研究问题中目标为最小化拣货作业总路径，据此适应度函数为minD。

（4）遗传算子。

①选择。首先将初始种群进行适应度的评估，产生新种群后，以概率ps舍弃劣势个体，将适应度高的种群保留进入下一轮的自我复制。

②交叉。交叉运算在遗传算法中起着核心的作用，其有利于组合之间传递新的信息，通过信息的交换和组合，有利于快速得到最优解。本文根据交叉概率pc=0.85，从生成的种群中选择交叉的个体。例如，选取两个染色体A、B进行操作，使得生产的新染色体A′、B′。

式中，“|”为交叉点；“*”的填入方式为（以染色体A为例）：从染色体B的第1位开始向后依次比较，其若与染色体A的前2位数不同则填入染色体A的“*”中，若相同则跳过，将染色体A的“*”一一补齐，从而产生新的染色体。

③变异。根据变异率pm=0.02筛选出需要变异的个体。从每个被选择的个体中随机选择两个变异点，并交换两个变异点的信息以获得新的个体。

5 算例仿真

本文以双区型仓库环境为例，其中包含400个商品储位，由1条主通道、2条边通道和10条拣货巷道组成。假设每次的拣货量不超过30 件商品；储位宽度D1=2 m、深度D3=2 m；拣货巷道宽度D2=2 m；主通道宽度D4=4 m。假设在某一段时间内某仓库共收到了6个客户订单，订单中商品的位置及数量如表2所示。

5.1 单一拣取方式下的仿真结果

在一辆拣货车只拣取一个客户订单的情况下，6 个客户订单生成了6 个拣货单，运用遗传算法和S 型启发算法的仿真结果如表3所示。

5.2 批量拣取方式下的仿真结果

根据订单包络算法对6个客户订单进行分批，共分为三批，分别是[1，2]、[3]、[4，5，6]，即订单1 和2 在一张拣货单上，订单4、5和6在一张拣货单上，订单3在一张拣货单上，如表4所示。

3张拣货单运用遗传算法和S型启发式算法的仿真结果如图4和表5所示。

5.3 仿真结果

总订单的具体改善数据如表6所示。

仿真结果表明，订单分批后的总拣货路径比不分批的总路径改善了很多，说明订单分批策略能有效提升拣货效率；根据路径规划仿真结果将两种算法进行对比，不同的算法对拣货单上的商品的拣取次序有些不同，且遗传算法下的拣货路径规划较优，从而验证了遗传算法的有效性。因此将订单分批策略与遗传算法下的拣货路径规划相结合能得到较为合理的拣货作业规划。

表2 订单中商品的位置及数量

表3 单一拣取路径规划汇总表

表4 分批后拣货单中商品的位置及数量

图4 三张拣货单在两种算法下的路线图

表5 批量拣取路径规划汇总表

表6 总订单汇总表

6 结语

设计较为合理的拣货作业规划，不但能够解决目前物流配送效率低下的严峻问题，还能降低仓库的成本。因此，为了提升拣货作业效率，减少拣货成本，本文以双区型仓库为对象，讨论了不同订单分配方式和拣货路径规划，构建相应的模型，设计两种启发式算法进行求解，以实现较为合理的拣货作业规划。但是本文研究的不足之处是只考虑了订单分配的两种基本方法，没有深入考虑结合拣货策略后的多种分配方式；同时在对路径规划的过程中只研究了进行一次拣货作业过程中的路径规划，没有考虑多名拣货员同时进行拣货作业时的路径规划情况。因此，如何结合实际拣货作业情况选择更为合适的订单分配方式，并在路径规划模型之中添加多人的拣货路径规划将是下一步主要的研究方向。