基于遗传算法的订单分批策略研究

秦 馨，赵剑道，任 楠，李佳顺，马洪泽

（1.北京机械工业自动化研究所，北京 100120；2.北自所（北京）科技发展有限公司，北京 100120）

0 引言

随着电商的飞速发展、物流效率的极大提升，市场需求开始呈现出多样化的趋势，销售订单也逐渐向零散化进行转变。为了适应市场变化，更好的提升企业竞争力，很多企业开始通过建立自动化工厂来实现仓储管理、备料配送等功能，物流配送向自动化、智能化发展，从而降低物流成本、提高仓储效率。但是由于订单的随机性、差异性比较大，分拣作业依旧以人工作业为主，机械化程度比较低，严重影响着物流配送效率的提升，因此如何提高分拣作业的效率，成为了自动化物流管理的重要研究方向。经过众多学者的研究，选择一种合理且有效的订单分批策略，在优化分拣作业流程、减少作业处理时间方面起着关键的作用。

1 订单分批

分拣作业是指库房在接收到一定量的订单后，按照订单内容将每个订单所需的物料分拣至订单对应的载具中。订单分批则是将大量的订单按照一定的策略划分至不同的批次，每个批次中包含一定量的订单，然后同一个批次中的订单将所需物料合并来同时进行分拣。因此每批次中不同订单需要相同物料时可以一次性拣出，不必重复分拣，能够减少拣选时的行走距离，有效的提高分拣效率。

1990年，Kenneth最早提出了订单分批的概念。传统的订单分批策略主要是基于个人经验来进行选择，一般是基于时间顺序来进行分批拣选，这种方式优化效果较为有限。随后，大量学者在这个方面进行了深入的研究探讨，先后提出了基于订单相似性的各种启发式算法，包括种子算法、节约算法、包络算法和聚类算法等。但是随着订单数目的增加，算法受初始订单影响较大，优化效果不稳定，而且这些研究大部分都是基于“人到货”的模式，对于当前更为流行的“货到人”场景适配性不足，因此对“货到人”应用场景的订单分批策略值得进一步探索。

本文基于“货到人”的实际应用场景，采用基于遗传算法的订单分批策略，以最小化货物搬运次数为目标构建了订单分批问题的数学模型，通过设定初始种群、选择、交叉、变异等一系列遗传操作设计得到了有效的分批结果。

2 模型与假设

在“货到人”的模式下，人员不需要在货架间行走，而是在固定的拣选工位进行拣选，货物则由输送设备从库房送到拣选台，因为现实工作中每个拣货员的拣选速度和每种物料的拣选时间都无法控制，因此所有订单的拣选时间只与货物的运输距离相关。由于货物随机存储在货架上，不同储位到拣选工位的距离基本相等，则总的货物的搬运距离基本和货物的搬运次数线性相关。因此，本文订单分批的总目标为，订单分批后进行拣选作业时总的搬运货物次数最少。根据实际工程应用场景，有以下约束条件：每个订单中最少包含一种货物；每个订单不允许被分割，也不允许重复分配；每个拣选工位每批可拣选订单数固定；每批订单只能在一个工位进行拣选；不存在缺货情况。

假设库房中共有M种物料，现有N个订单Xi（i=1，2，…，n）需要进行拣选，每批分拣订单数为C，共可分为T批，总的搬运次数为L，第j批的搬运次数为Lj（即第j批中包含的订单合并后所有物料的搬运次数），xij表示订单Xi的分批结果，若xij为1则该订单分配到第j批中。综上，该订单分批问题建立的数学模型为：

目标函数：

约束条件：

3 算法

遗传算法（Genetic Algorithm）是一种随机搜索算法，是通过对基于达尔文生物进化理论与遗传学机理的自然选择和生物进化过程进行模拟搜索得到最优解的方法。已经大量应用于函数优化、图像处理、生产调度、机器学习和组合优化等不同的领域中。不同于传统的搜索算法，遗传算法是一种基于概率进行搜索的寻优方式，它不需要提前确定搜索规则，可以自适应的调整搜索方向，实现自动获取搜索空间并进行优化指导。

本文采用的遗传算法从待解决问题随机生成的部分解集开始，这个解集包含一定数目的个体，这些个体一般采用一串数据或者数组来表示解的编码，称之为染色体。然后利用适应度函数来衡量这些染色体的优劣，并以此为依据借助遗传算子选择初始种群中的部分染色体，并进行交叉和变异操作，从而形成新的种群。根据优胜略汰的进化原理不停的进行迭代，这种进化过程将在若干代以后使得种群中染色体的适应度值逐渐增大，即算法将收敛于表现最出色的染色体，这就是我们所寻求的最优解。因此，遗传算法的主要内容包括：初始编码设计、确定适应度函数、选择、交叉、变异、设置终止条件。

采用遗传算法解决订单分批问题就是通过一定的遗传进化原理，将所有订单分成不同的批次，然后对每一批的订单进行集中拣选，其目的是减少货物的搬运次数。

3.1 初始种群

3.1.1 编码设计

一维染色体编码是遗传算法中目前最为常用的编码技术，它是对问题的解的元素进行编码后，形成染色体，这些染色体中的元素成一维排列。由于本文中订单数量比较大，基因特征较为复杂，采用实数编码能够更加精确的描述订单分批的结果。

本文将每一个订单都视为染色体的一个基因，该订单在整个订单分批之后的批次序号即为此基因的特征，所有订单的批次集合组成了一条染色体。则n个订单编码后形成的染色体集合为：

其中：yi表示订单Xi的分批结果，若该订单被分配到第j批中，取值为 j。

根据约束条件(2)、(3)、(4)，染色体表达式(5)有约束条件(6)、(7)：

3.1.2 生成初始种群

每一种分批结果都视为一条染色体，则随机生成的若干条染色体的集合形成初始种群，为了防止初次选择时同一染色体的重复出现影响遗传过程中算法的收敛效果，应保证初始种群中任意两个染色体之间都不相同。假设初始种群大小为H，则初始种群的表达式为：

初始种群的选择不仅决定着最终解的好坏，也对算法计算效率有着很大影响。如果初始种群规模过小，则种群内染色体的多样性就会减小，算法很可能最终选取的是局部最优解，而不是最优结果或者附近；如果初始种群规模过大，那么进化过程中每次迭代所需要的计算量及时间都很大，会影响算法效率。

3.2 适应度函数

适应度是指某个生物对于外部环境的适应程度，即用来衡量群体中个体性能的指标。适应度函数通常由目标函数来确定，通过它来计算个体的适应值，若适应值越大，则代表该个体的性能越优异，越能够作为新一代遗传的父本。

本文采用的目标函数为最小化货物的搬运次数L，因此选取目标函数的倒数来作为适应度函数，当目标函数值越小时，适应度函数值就越大。适应度函数即为：

3.3 遗传操作设计

3.3.1 选择

选择是指从种群中按照一定的概率选择出若干个染色体，是一种基于适应度值将种群收敛于优异个体的过程。本文采用结合适应度比例法和最佳个体保留法的策略来进行选择。

适应度比例法的主要思想是从群体中选择个体的概率与其适应度评价有关，个体对应的解求取的适应度越高，得到的目标函数值就越大，选择的概率也越大。假设初始种群大小为H，即染色体编号为1，2，…，h，其中，个体 r 的适应度值为fr，个体 r 被选中的概率设为pr，累计概率设为qr，则：

从[0，1]区间产生一个随机数 e，那么被选中的个体为：

从父本选择出染色体进行交叉变异后，形成子代种群，根据适应度从父代和子代中分别筛选出50%的适应度最高的个体组合成新的种群，既能使优秀个体参与交叉变异操作，有利于突变产生更优个体，又能保留父本中的优秀个体，避免错失更优解，同时加快收敛速度。

3.3.2 交叉

交叉是指将父代中选取的两个个体交换部分基因重新组合成新的子代，用于保证种群中个体的多样性。本文采用两点交叉的方式，从交配池中两两选择父体，然后在每对中随机指定两个基因位置进行交叉，从而产生新的一对个体，直到交叉全部结束，形成新的种群。例如，选中个体y、z进行交叉，交叉前后的染色体编码分别为：

3.3.3 变异

变异是选取部分染色体中的某些基因做出变化，增强了群体的多样性，有效防止算法提早进入收敛状态。

由于拣选工位每批订单数固定为C，而在经过交叉操作后，很可能使得某个染色体中分配到同一批次的订单数量大于C，因此本文通过变异操作，将染色体中的订单分批结果进行调整，使其满足实际应用的约束条件，具体步骤如下：

1）查找交叉操作后的染色体，统计其基因中所有同一编码值的个数。

2）统计其中数量超过C的编码j1、j2，与数量少于C 的编码k1、k2。

3）将编码值为j1或j2的其中一个基因变异为k1或k2，使得最后的每批订单数均为C。

3.3.4 设置终止条件

经过选择、交叉、变异后，我们得到了新的种群，而在持续的选择、交叉、变异下，如果不设置终止条件，遗传算法会一直计算下去，因此需要设定可靠的终止条件。

本文设置的终止条件为：

1）当算法运行次数达到最大迭代代数后停止运行。

2）当算法成熟收敛，种群中染色体种类剩余一种时停止运行。

3.4 算法流程

根据以上分析使用遗传算法进行订单分批的具体算法流程如下：

1）随机将订单分批，生成初始种群，并根据编码规则进行编码。

2）根据每个订单所包含的货物品项计算分批后订单组的总品项，然后计算适应度函数。

3）根据适应度函数计算累计概率，并进行选择、交叉、变异，然后将子代中的优秀个体与父本中的优秀个体组成新的种群。

4）判断是否满足算法的终止条件，若不满足，重复第2）、3）步不断进行迭代进化，若满足，则停止迭代，选取当前种群中适应度值最高的分批结果作为最终分批方案。

4 仿真

4.1 实验方案

假定共有50种货物，然后随机生成2000个包含这50种货物的订单作为实验数据，每个订单包含2到20种货物。根据现实使用场景，同一批次同时拣选订单数量最多为5个。

本文采用基于遗传算法的分批策略进行研究，衡量该算法在订单分批问题中的优化效果。并且为了更好的验证本文提出的遗传算法在订单分批问题中的优势，将相同的数据分别采用不分批的策略和先到先分批的策略进行计算，作为本文所提出算法的对照参考组。

将这2000个订单随机分为10组，每组包含200个订单数据。每次实验都从10组数据中分别随机抽取20、40、50、75、100、125、150、175、200个订单来进行分批计算，每组数据采用遗传算法进行分批时重复实验计算5次，取其平均值作为该组的货物搬运次数，然后再将这10组数据取其平均结果作为最终分批方案。

4.2 参数设置

选取一组订单数据，采用遗传算法，计算在设置不同的初始种群大小及不同的迭代次数时，最终的货物搬运次数。每种参数设置都重复5次取其平均值作为最终结果，当订单数为20时，结果如表1所示。

表1 货物搬运次数（订单数为20）

由表1可得货物搬运次数与迭代次数和初始种群大小之间的关联情况。不同迭代次数下货物平均搬运次数与初始种群大小的关系如图1所示。由图1可得当初始种群H小于70时，货物搬运次数随着初始种群数量的增加而显著减少，当H大于70时，搬运次数趋于平稳，基本不会随着H的增加而继续减少。因此设定当订单数为20时，本文实验设置初始种群大小H=70。

图1 不同迭代数量的平均搬运次数

初始种群数量不同时，货物平均搬运次数随着迭代次数变化如图2所示。可得，货物搬运次数随着迭代次数的增加而减小，但是当迭代小于25时，搬运次数与迭代次数的负相关性较为明显，当迭代次数大于25时，货物搬运次数受迭代次数影响较小。考虑到算法的运算效率将随着迭代次数的增加而降低，因此订单数为20时，本文采用遗传算法的终止条件为迭代次数大于等于25次。

图2 不同大小初始种群的平均搬运次数

根据上述方式，分别计算出不同订单数量下，选取的初始种群大小与迭代次数的参数如表2所示。

表2 参数设置

4.3 实验结果分析

实验采用了基于遗传算法的分批策略、先到先分批的策略和不分批策略三种方案进行计算，对比验证不同方案的拣选效率。通过计算分批问题的目标函数值，即所有订单品项总的搬运次数作为衡量分拣效率的指标。对10组数据的实验结果计算其平均值如表3所示。由表3可得，在不同规模的数据集下，不采用订单分批策略的方案最终的品项搬运次数最高；采用先到先分批策略进行订单分批后，搬运次数有所下降；而基于遗传算法的分批策略，使得订单总的搬运次数最少。因此，基于遗传算法的分批策略在订单分拣作业中，对拣选效率有着很大提升。

表3 平均货物搬运次数（全部实验数据）

图3为不同的分批策略下，最终的货物搬运次数与不分批策略搬运次数的比值。由图3可得，在不同规模的订单数据集下，先到先分批策略对于拣选效率的优化效果比较稳定，比值在65%左右，基于遗传算法的分批策略对拣选作业的优化效果有着显著提高，比值在55%到60%左右，而随着订单规模的增加，算法的优化效果有所下降。

图3 分批策略与不分批策略的搬运次数比

5 结语

本文在基于“货到人”的自动化物流中心的工作模式下，针对订单分批问题，构造了以最小化订单品项总的搬运次数为目标函数的数学模型，并且搭建了基于适应度度量的遗传算法模型，与不分批的策略和传统的采用先到先分批的策略进行比较，本文提出的算法能够有效的减少货物搬运次数，明显提高了作业效率。

本文主要针对同种货物单个储位的自动拣选，无需考虑同一货物储存于多个储位时对于拣选效果的影响，未来可对不同货架承载货物种类大小不一致、单一品项拥有不同储位的拣选作业进行进一步的研究。