基于遗传算法的拣选系统调度优化研究

纪佳溥，岳秀江，赵剑道，蔡 苗，王欣旋

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

0 引言

随着物流行业的发展,订单拣选已成为物流系统中的关键环节之一,是影响作业效率的重要因素。高效的订单拣选不但能在最短的时间内使用最少的成本完成拣选作业,还能提高客户满意度、提高整个供应链的服务水平。

传统分拣系统按下单时间来分配分拣任务,忽视了订单之间的耦合和各分拣工位的布局,容易造成各工位分拣任务不均衡现象,导致不同工位在不同的时间段任务量差别过大。分拣量大的工位拣选人员忙不过来,积压大量任务；分拣量小的工位拣选人员无事可做,只能等待。空闲时间的增加,导致系统拣选完成时间过长,不但浪费了人力与设备利用率,还降低了系统的整体性能。严重的话更会导致现场物流堵塞,影响客户满意度。

分拣环节已成为提高物流系统整体运行效率的主要瓶颈,企业生产方式已由传统的面向库存生产转变为面向订单生产,如何提高订单拣选的准确性和时效性,是物流系统亟待解决的问题。国内外学者对该问题展开了广泛的研究,主要集中在仓储布局、路径策略、拣货策略等方面。Prata[1]等以最小化最大完工时间为目标研究客户订单调度问题,提出了基于混合整数线性规划模型的FVLA和CSA算法。Jason[2]等提出了一种基于整数规划的松弛算法,通过将算法下界转换为模型可行解来对问题进行求解。吴颖颖[3]等以耦合因子为参数、订单拣选顺序为决策变量构建订单排序优化模型,并用改进的K-Means算法进行求解。

本文从物流系统实际出发,采用订单拣货策略,研究订单排序对拣选完成时间及效率的影响,用周转箱代表订单,以订单上线顺序为决策变量、拣选等待时间为限制条件,建立订单排序优化模型,并用遗传算法进行求解,将结果与先到先服务（FCFS）规则进行比较,验证遗传算法在优化订单拣选顺序问题上的有效性。

1 问题描述

以某分拣中心的分拣系统为例,拣货区由n个分拣工位组成,每个工位由1名分拣人员负责,每个工位对应固定的分拣货物。系统分拣方式为摘果式分拣：订单拣选时,订单对应到每个周转箱,订单顺序即为周转箱上线顺序。周转箱按指定顺序上到输送线,以顺时针方向移动到指定工位。分拣人员根据提示从货架取出货物,完成分拣任务,随后周装箱流向下一工位,不断重复此过程,直至该周转箱对应的订单分拣完成,此时周转箱从分拣区域流出。订单拣选完成时间随订单的内容和订单顺序的不同而有所差异,任务分配不均衡也会拖慢分拣速度,导致分拣完成时间增长。因此,调度的主要目标在于合理安排各个订单对应的周装箱在各工位的拣选顺序,使得各分拣工位任务量均衡,完成所有订单的时间最短,提高按时交单率。

对于要研究的物流系统,有如下假设：

1）拣选的货物充足,不需要补货。

2）拣选货物单位时间一致,不考虑货物在货架上位置的影响。

3）每个周装箱只能对应一个订单。

4）一个订单对应一个或多个周转箱。

5）输送系统速度稳定。

6）空周装箱充足。

7）模型为静态拣选系统,订单信息在分拣开始前已知。

2 订单排序优化模型

订单排序问题的目标是订单拣选完成时间最短,而拣选完成时间分为二部分：拣选时间、等待时间。其中,拣选时间指拣选人员拣选货物的时间,一般与拣选次数（拣选量）成正比；等待时间是指订单上线后,由于上一订单尚未结束、占用拣选工位而产生的空闲时间。

构建n维向量V表示n个订单分拣顺序向量如式(1)所示。

其中,λi(1≤i≤n)是两两不同且位于[1,n]的自然数,表示分拣顺序为i的订单号。传统订单拣选顺序遵循FCFS原则,按照下单时间来分配订单任务,相应的拣选顺序为V=(1,2,3,…,n-1,n)。

构建m维向量Xi表示第i个订单在各工位需要分拣的任务量如式(2)所示：

其中,m表示分拣工位的个数,xij(1≤i≤n,1≤j≤m)表示订单i在工位j所需的拣选数量。如果不需要,则取值为0。

假设拣货员拣选一个商品或者做一次拣选工作所需要的时间恒定,用tv表示,可以得到第i个订单在第j个分拣工位消耗的时间tij如式(3)所示：

假设输送系统速度稳定,则周转箱从i-1工位到i工位所用时间的时间恒定,用tw表示。

周转箱到达指定工位后,若上一订单对应的周转箱若还未完成分拣任务,则本次周转箱需要在缓存区等待,相应的等待时间用表示。由两部分组成,一是线体上移动所用时间,即tw；二是上一周转箱分拣所耗时间t(i-1)j。理想情况下,本次周转箱到达时,上一周转箱已经离开,此时不存在等待时间,取值为0。考虑到上述两种情况,

由式(4)表示：

综上,本文讨论的订单排序优化模型如下所示：

目标函数如式(5)所示：

约束条件如式(6)～式(11)所示：

目标函数式(5)表示最小化订单拣选完成的总时间；式(6)表示订单在各工位拣选工作消耗的时间之和；式(7)表示由于分拣任务不均衡导致的等待时间之和；式(8)表示第i个订单在第j个分拣工位分拣所用时间；式(9)表示第i、j个订单由于拣选顺序引起的等待时间；式(10)和式(11)分别代表需要分拣的订单总数、分拣工位数量。

3 算法设计与实现

订单排序问题可视为旅行商问题（Travelling salesman problem,TSP）的变种,求解过程属于NPHard难题,通常难以在多项式时间内得到最优的订单拣选序列,因此,在参考前人相关研究的基础上,本文采用遗传算法进行求解,具体过程设计如下：

3.1 编码

编码方式是遗传算法的基础,合理的编码对算法质量和求解效率有很大影响。工程中常用的编码方式有二进制编码、十进制编码、实数编码等。在订单排序时,把订单拣选顺序向量作为单个染色体进行处理,向量由从1开始的整数组成,同时考虑到订单对货物的需求量都是从0开始的整数,且二进制编码有其明显的局限性,所以编码方式选择实数编码。通过选择实数编码,不但省去了解码这一繁琐步骤,还能有效避免海明距离这一问题。

3.2 种群初始化

传统的遗传算法中,初始种群中的个体是随机产生的,这很可能导致结果陷入局部最优,不利于问题求解。为了避免这种情况,使得初始种群中的个体均匀分布在解空间,本文以海明距离为优化方向,来对随机生成的初始种群进行选择。

1）随机生成3n个染色体个体；

2）通过FCFS方式生成初始订单序列,作为初始种群中第一个个体；

3）计算未被选中个体与初始种群中染色体个体之间的海明距离之和,选取距离最大值对应的个体加入初始种群；

4）重复3)中操作,逐渐增加初始种群规模,直到初始种群包含n个染色体个体。

3.3 适应度函数

适应度函数用于对个体进行评价,体现了目标函数的变化趋势,是进化过程中个体选择的唯一依据。订单拣选顺序优化问题的目标是最小化拣选完成时间,属于最值问题,适宜采用目标函数映射法,即将目标函数变换成适配值函数,因此,适应度函数设计为目标函数的倒数如式(12)所示：

3.4 选择操作

选择是从群体中选择适应度高的个体、淘汰适应度低的个体的操作。目前常用的方法主要有：比例选择、排序选择和联赛选择等。本文采用比例选择法（也称轮盘赌）对个体进行选择,这是目前遗传算法中最常用的选择方法,其基本原理是根据每个染色体适应度值的比例来确定被选中的概率,将适应度按从小到大的规则排序,个体适应度越大,被选中的概率就越大,反之亦然。设种群大小为N,个体i的适应度为fi,则个体i被选中的概率如式(13)所示：

3.5 交叉操作

交叉是将两个父代个体的部分结构加以替换重组而生成新个体的操作。通过组合出的新个体,提高了遗传算法在在解空间的全局搜索能力,降低了对有效基因的破坏概率,是遗传算法区别于其他启发式算法的重要特征。

实数编码遗传算法与二进制遗传算法相比,可用的变异算子种类更多,常用的算子有离散重组、算术交叉、部分匹配交叉（PMX）和循环交叉（CX）等。对于订单排序优化问题,每条染色体个体代表了一种分拣顺序,交叉操作可能会产生不符合实际情况的序列,如同一订单出现多次、缺少某个订单等。从编码-交叉设计原则出发,本文选择顺序交叉(Order crossover,OX),该算子的优点是交叉后不会出现重复的订单序号、不需要进行冲突检测,因而在实数编码的遗传算法中得到广泛应用。顺序交叉算子的具体操作过程如下所示：

对于两个包含9个订单的父代个体P1、P2,随机选择两个交叉点“|”,交叉前的父代染色体为：

顺序交叉后,最终得到的子代染色体情况如下所示：

3.6 变异操作

变异是在染色体个体上产生微小扰动来维持种群多样性的操作。通过变异操作,遗传算法的局部搜索能力得到加强,选择、交叉过程中丢失的基因得到修复和补充,有利于增加种群的多样性,在一定程度上预防了早熟收敛现象。

常用的变异算子有：位点变异、逆转变异、对换变异等。由于染色体基因值的固定范围且两两不同的自然数,不宜采用位点变异、对换变异等算子。本文选择了两点法,即在一个个体中随机选择两个点,使两点的位置互换,基因值互换,代表相应的订单分拣顺序互换,达到了变异的目的。对于一个染色体p,随机选择两个变异点“|”,变异前染色体为：

变异后子代染色体情况为：

3.7 算法终止条件

实际应用时,不允许遗传算法无休止的计算下去,因此需要设定收敛准则来终止算法。本文设计的终止条件为最大迭代次数：当迭代次数等于最大迭代次数时,算法停止搜索过程,输出最优解。

4 实例分析

交叉概率范围一般是0.6～1,变异概率通常是0.1或者更小。经过多次仿真计算,本文实现的遗传算法相关参数设定为：交叉概率Pc=0.8,变异概率Pm=0.003,最大“停滞”次数为10,最大迭代次数设为500,种群规模为N=100。

需要分拣的订单总数n取值范围为50、100、200,分拣工位数量m取值为6,各订单在不同工位的分拣量取值范围为[0,20]。

多次迭代,取较优结果,并计算不同订单数量下的订单拣选时间、订单等待时间,绘制分拣时间时间趋势图,实验具体结果如表1所示。

表1 订单拣选时间 （单位：s）

表1为遗传算法对模型求解之后得到的结果。从实验结果可看出,订单排序拣选可有效缩短订单拣选时间。相比于订单顺序拣选,总的拣选完成时间分别缩短了7.1%、7.9%和3.8%,说明本文实现的算法对不同的订单规模均有一定的优化效果。

表2为优化前后系统分拣等待时间对比。从表中可看出,订单排序后系统分拣等待时间大幅度缩短,表明订单排序可有效均衡不同工位工作量,减少了堵塞现象,进而缩短了系统整体分拣完成时间,为提高分拣效率提供了合理性指导。

表2 分拣等待时间 （单位：s）

图1、图2和图3为订单规模为50、100和200时的订单分拣总时间。从趋势可以看出,随着迭代次数的增加,订单总分拣时间在逐渐缩短,最后趋于稳定,证明了订单排序这一策略的有效性。

图1 订单数量N=50时分拣时间随迭代次数增加而变化的趋势图

图2 订单数量N=100时分拣时间随迭代次数增加而变化的趋势图

图3 订单数量N=200时分拣时间随迭代次数增加而变化的趋势图

5 结语

本文对分拣系统调度优化问题进行了研究,指出了订单排序问题的必要性。从订单的拣选顺序入手,以订单分拣完成时间最短为目标建立了相应的订单排序优化模型,利用基于实数编码的遗传算法对模型进行求解,获得了较优的订单拣选顺序。与订单顺序拣选相比,本文提出的算法可有效均衡各工位工作量、缩短工人等待时间,进而缩短系统分拣完成时间,对于提高分拣系统运行效率具有一定的指导意义。

单一目标函数的模型往往难以满足各种系统的实际需求,冲突性的多目标或众目标是未来的研究方向。因此,对于目标函数的更细化考量,还有待进一步完善,这也是本文未来工作之一。