基于粒子群与遗传算法的排序区拣选优化研究

张岩

摘要：影响物流时效的核心环节是拣选作业，其对物流成本及竞争力都有着非常重要的影响作用。目前，我国多数的物流企业均是人工分拣。但是随着分拣量的增加、分送点的增多，配货响应时间的缩短和服务质量的提高，单凭人工分拣必将无法满足大规模拣货的要求。针对车间内既需要排序同时又需要拣选的操作来说，存在着人员行走距离较长，路线交叉，拣错零件的风险高等问题。分析后对此问题提出了利用使用灯光拣选与多层货架结合的方式替代现有的拣选方式，构建数学模型，并通过遗传和粒子群的混合算法对其进行求解，进而对拣选的路径进行优化，最终设计出成本最低的拣选方案。 

Abstract： As the core link that affects the effectiveness of logistics， picking operation， which has a very important impact on logistics cost and competitiveness. At present， most of the logistics enterprises in China are manual sorting. However， with the increase of sorting volume， distribution points， distribution response time and service quality， manual sorting alone will not meet the requirements of large-scale picking. For the operation of sorting and picking in the workshop， there are many problems， such as long walking distance， cross route and high risk of picking wrong parts. After analysis， this paper proposes to use the combination of light picking and multi-layer shelf to replace the existing way of picking， build a mathematical model， and solve it through the hybrid algorithm of genetic and particle swarm optimization， then optimize the path of picking， and finally design the lowest cost picking scheme.

關键词：排序区;灯光拣选;遗传算法;粒子群算法;拣选路径

Key words： sorting area;PTL;GA;PSO;Picking Path

中图分类号：TP18                                          文献标识码：A                                  文章编号：1006-4311（2020）19-0249-05

0  引言

作为影响物流时效的核心环节，拣选作业对物流成本和竞争力有着至关重要的影响作用[1]。在物流领域内，拣选是指拣选式配货作业，是拣选人员或拣选工具在各个储存点内行走并将待拣选的货物取出，完成拣选任务的相对运动[2]。作仓储运营系统中的重要环节，拣选技术的发展日新月异，从传统的拣选人员手持拣货单拣货到使用PDA扫描拣货，从射频识别技术到电子标签辅助拣选技术，从货到人系统到机器人自动拣货技术，琳琅满目。企业在设计仓储运营系统时，面临越来越多的选择。

一般需要物流拣选操作的车间，进行的都是拣选作业。而某些汽车企业不同，物料零部件并不是直接从仓库直接运送到生产线上进行装配的。汽车零部件从原料区到生产线旁，都是需要经过配套排序区的一系列拣选排序的操作的在该区域内拣选作业人员不仅需要将零件拣放到指定的位置，还需要对这些零件按照订单上的顺序进行排序，保证生产。在这个过程中，除了拣选零件需要一定的时间外，还增加了零件的排序时间。其中，配套排序区，就是指根据生产订单排序， 从不同的零件族拣选出一些零件，放到同一台车的配套器具里（KC）， 或是从同一个零件族中拣选出差异的零件放到一个排序器具里（SQ）。配套（KC）：配套是把不同类别的多个零件根据系统的生产订单顺序放入一个配套器具中。排序（SQ）：排序是将同一类别的多个零件（通常种类不小于3种）根据系统生产订单顺序放入一个排序器具中。

1  问题的提出

M汽车企业的总装车间拥有着柔性的生产线，该企业用四年的时间实现了每小时40台车的产能，而这个产能效率还在不断提升，到目前，产能为60台车每小时，按照车型、高低配等的不同，可能在这条生产线下线的产品有近百种。为了生产这些产品，需要准备的原材料需要几千种。物流部门每天需要将超过3000000零部件及时的分配到各条装配生产线上，这就要求信息的传递必须是正确的，相关的流程必须是合理的，高效的，关键是成本必须是在一个可控范围，这样才能保证汽车的正常生产[3]。而庞大的数字只是物流工作面对的维度之一。实际上，物流是生产系统的核心，是极其重要的。要确保一切都在同步进行，在正确的时间，把正确的零件送到正确的地点，这样才能汽车才能顺利诞生。因此在这样先进的企业中，高效物流系统是不可缺少的，而汽车制造流程复杂，科学的物流至关重要。在该工厂里，每天都有几千立方米的原料需要被运送到相应的生产环节，若是原料大批堆积将很大程度的降低生产效率拣选。

在对总装车间排序区拣选作业进行研究后，发现以下几种情况出现。

①现有拣选作业流程不合理，导致排序拣选作业时间较长，工人劳动效率较低，会出现满足不了生产的情况。

目前，在该汽车总装车间内，随着系统自动生成订单，配套排序区的打印机自动打印出拣选领料单，当这些领料单攒到一定数量时，拣选操作人员需要将领料单进行手动排序，再将信息汇总到手抄纸上，接着带着领料单推着拣选小车到存放汽车零部件的架子处进行拣选作业，当领料单上的零件拣选完毕时，操作人员再将小车中的零件依次放入到待发走的拖车中，完成此次拣选任务。

整个流程中，出现了人员先将零部件按照顺序放入拣选小车中，再将零件取出，依次放入到待发走的拖车中，整个过程中拣选小车仅是起着过渡的作用，并非必须使用的器具。由于拣选作业流程中存在这种无用不产生实际价值的操作，导致拣选作业时间过长。

②同一区域，多名作业人员并行接力式拣排序拣选（最多有10个人），不仅会出现信息交接偏差，重复作业等，还会出现交叉作业，相互影响等情况。

③人工抄写拣选信息，增加了错拣的风险。

拣选作业人员将领料单按照零件放置的位置进行排序，再将排序后的零件信息抄写到手抄单上。在抄写时，作业人员经常出差错，拣选信息抄写错误，直接导致拣选作业人员拣选错误的零件，若没有及时发现，有可能会造成停线等严重的后果。

故将信息手动抄写这种方式，会增加零件错拣的风险，甚至造成更加严重不可挽回的结果。于此同时，作业人员作业时为了尽量降低错拣漏拣的情况发生需要集中注意力，从人因角度来说这样是非常不合理的。此外，在长时间拣选作业后，随着作业人员疲劳程度的增加，错拣的几率会增加很多。

④人工排序时，对现场熟悉成都要求高。

由于系统产生的订单是由需求决定的，并无规律可言，故可将其看作是随机产生的订单。当订单产生并攒够一定数量时，拣选人员将根据零件装入拖车的顺序将领料单进行排序，因此领料单上需要拣选的零件会分布在不同的货架上。此时，拣选人员需要熟悉现场零件的摆放位置等，之后根据经验判断所需要拣选的零件所在的位置再进行拣选作业。

若作业人员未接收良好的培训或对现场环境不够了解，容易混淆零件，严重时甚至拣错零件。

⑤每天打印的纸质单据，大量消耗纸张和墨盒，造成资源的浪费。

排序区拣选作业的时间要求是十几分钟就要排完拣选完一个器具，一般器具平均有十几二十几张的纸质单据，而每班最少生产8小时，最多10.65小時，两班制生产，每周工作6天，计算下来每周物流排序区会产生四五千张排序单需要处理。生产操作工人除了要做排序拣选任务外，还要额外增加处理纸张的工作，增加了作业人员的工作量的同时还增加了成本。除此之外，也影响了车间现场5S管理。

⑥拣选效率低，现场拣选作业人员多，人工成本增加。

2  建模与求解

针对M汽车企业生产过程中发现的上述问题，在符合物流中心布局以及工艺要求的条件下，应用现存的技术，以最小的成本对拣选进行改进提升。

为此智能拣选系统可以解决大多数的问题，本文针对这些问题提出相应的智能拣选方案。首先，从排序拣选信息的处理入手，将物料的需求进行整合，尽可能的减少拣选操作的数量。整合同一类型的订单，使得可以一次完成对一张订单的拣选，并且缩短了时间。其次，对排序拣选方式的类型和零件的存储方式进行优化，将地面件放置到多层料架上，减少物料的存储空间，避免空间的浪费。同时，采取智能的排序拣选方式，灯光拣选的电子标签式的辅助拣选方式，利用灯光指引的方式指导拣选作业人员先拣选何种零件，放置到何处，当该种零件拣选完毕后，再依次按照顺序对订单待排序拣选的零件进行操作。减少拣选人员的自主判断，还能缩短查找与检查的时间等。对现阶段的拣选模式进行分析，明确拣选的目的，进而优化拣选配送过程。最后，对拣选的路径进行优化研究。

在灯光拣选的智能拣选方式的基础上，对其中亮灯待拣零件的拣选路径进行优化，主要针对现阶段重复路径多，产品类型转换带来的额外决策时间等。使用科学，系统的拣选方法，减少重复路径。使用智能技术对拣选路径计算，优化拣选过程的路线，使拣选作业人员按照智能拣选系统提供的路径进行拣选，可以进一步减少移动的重复距离，提高拣选的效率。

2.1 数学模型的构建

从拣选作业的流程上看可以把拣选作业路径简化归纳成如下问题：在该区域内有P个拣选人员，每个人拣选人员都会在拣选单打印处领到1张拣选单，而这1张拣选你单上有n个拣选任务，即有n个待拣选的储位，拣选作业人员从初始点出发，分别到达n个储位点，且每个储位点只去一次，最后回到起点，求拣选作业人员行走的最短路径。系统打印出来的拣选单是与生产线上需要装配的汽车的零件信息是一一对应的，这就存在着和排序区的架位置不一致，而每个人的拣选任务数量是一致的，故本文可以将问题简化为1个拣选人员对应n个拣选任务，m个货架。

相类似的可将本文的问题归纳为旅行商问题，并根据实际情况添加约束条件。规定拣选人员推着拣选器具需从空/满车点出发，订单中的拣选任务出现的储位都要被走到，并且只走到1次，最后拣选器具要返回空/满车点。需要在满足以上几点的约束条件之下，制定出合理的拣选路线。最优的路线代表着拣选时间最短，拣选效率最高，继而代表着拣选的成本最低。

2.2 算法的设计

Grenfenstette提出的遗传算法从代表问题可能潜在解集的一个种群（Population）开始，对种群反复进行选择（Selection）、交叉（Crossover）以及变异（Mutation）操作，估计各个个体的适应值（Fitness），根据“适者生存、优胜劣汰”的进化规则，使得群体越来越向最优解的方向进化[4-6]。其在计算过程中的前期有较大波动、计算结果变化大，在经过了一定代数的迭代后计算结果的波动逐渐减小并最后趋于稳定。基本遗传算法在迭代过程中易陷入局部最优。

粒子群算法是一种比较年轻的算法，在1999年由電气工程专家Eberhart与社会学专家Kennedy所提出[7]。其算法简单，收敛速度快，并且易于实现但后期容易出现早熟收敛的情况[8]。而遗传算法在全局性的最优解的搜索上有其独特的高效性，但是作为一种群体并行搜索的全局寻优算法，在局部搜索能力上有明显的不足，本文主要通过在粒子群算法中引入一算算法的交叉算子，使得成对的粒子可以互相交换信息，以便粒子具有向新的搜索空间飞行的能力。在粒子群算法中引入遗传算法的变异算子来增强粒子群算法跳出局部小的能力。

粒子群优化算法的计算过程是没有波动，并且它们也是分阶段的逐渐向最优解收敛的[9]。遗传算法与粒子群算法在优化方面具有很强的互补性[10]。遗传算法的探索精度与求变能力很强，其求解全局搜索能力很强，但局部搜索能力不足，而粒子群算法在全局寻优算法中具有随机的特性，其优点在于对优化目标的函数不要求可解析性。本文主要通过在粒子群算法中引入遗传算法的交叉算子，使得成对的粒子可以互相交换信息，以便粒子具有向新的搜索空间飞行的能力。为了实现增强粒子群算法能够跳出局部求解的能力，可以将遗传算法的变异操作引入到粒子群算法中，这种方式不仅增强了粒子的全局搜索能力，除此之外还保留了收敛速度快的优点。

组合算法示意图如图1所示。

具体的算法实现步骤如下：

①粒子编码：对于拣选路径的优化求解问题，实现混合粒子群算法的关键环节就是对粒子进行编码。将该问题的粒子编码方式设置为整数编码，每个粒子代表一个解，相当于每个粒子是解空间的一个所有储存位置信息的排列。

假设有1-20，共20个待拣选的零件，假设某个粒子的编码为[16 13 1 2 5 7 4 20 3 18 12 14 15 6 8 10 9 11 17 19]，这个编码代表了拣选作业人员需要行走的路径是从16开始的，接下来一次顺序为13，1，2，5，7，…，19。

②适应度函数：粒子的适应度函数 代表行走完整个拣选路径的长度。

③交叉：粒子通过将当前所在的位置与个体极值或群体极值进行交叉操作，来 更新更新目前的位置。交叉的操作方法使用整数交叉法。首先，在所选择的粒子中选择两个地方要进行交叉操作，接着将其与个体极值或群体极值进行交叉，随机诞生两个交叉点3与10，交叉的具体方法如下所示：

粒子当前值：[16 13 1 2 5 7 4 20 3 18 12 14 15 6 8 10 9 11 17 19]。

个体的极值：[12 3 20 14 11 17 18 8 9 10 15 6 1 4 2 5 7 13 16 19]。

交叉后个体：[16 13 20 14 11 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

粒子当前位置的从第3个基因至第10个基因的一段基因为[1 2 5 7 4 20 3 18]，而个体极值的从第3个基因至第10个基因为[20 14 11 17 18 8 9 10]，将这两段基因进行交叉操作，即可得到新的个体。而使用该种交叉操作后，会出现位置重复的情况，此时需要对新个体进行适当的调整，消除重复位置。具体调整的方法为，将交叉后的个体内已经重复夫人储存位置用还未包含的储存位置进行替换，具体操作如下：

交叉后的个体：[16 13 20 14 11 17 18 8 9 10 12 14 15 6 8 10 9 11 17 19]。

对其进行更改：[16 13 20 14 11 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

重复的位置分别为第12位，第15位，第16位，第17位，第18位及第19位。将这些位置分别用5，7，3，1，2，4进行替代，对所得到的个体保留了最优个体，只有当新得到的粒子的适应度值比原来的粒子的适应度值更优的情况再更新粒子的当前位置。

④变异：本文在变异操作，是通过对粒子的内部的随机两个基因进行互相交换位置的方式实现的。首先，在粒子中随机选取两个位置1和2，要对其采取变异操作，再将这两个基因的位置互换，，针对上面的粒子，随机选取两个要产生变异的位置，第2位和第5位，变异的操作方法如下所示：

变异操作前的粒子：[16 13 20 14 11 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

变异操作后的粒子：[16 11 20 14 13 17 18 8 9 10 12 5 15 6 7 3 1 2 4 19]。

对所得到的个体保留了最优个体，只有当新得到的粒子的适应度值比原来的粒子的适应度值更优的情况再更新粒子的当前位置。

2.3 仿真验证与结果分析

假设改建后的排序区料架有15排15列（15×15）。将左下角的货位设立为坐标原点，建立直角坐标系，（X，Y）代表货架的第X列第Y排，初始插取点坐标为M（0，1）。则距离远点最远的点为（15，15）。在该区域内有十个不同的货物需要拣选，并且这是个货位的位置已经明确，分别为A（8，2），B（12，8），C（1，9），D（5，5），E（5，13），F（2，6），G（10，5），H（15，10），I（9，12）与J（2，7）。

按照前述公式，任意两个货位间的拣选作业时间成本可以求得如表1所示。

若不经过改善，直接按照车间目前的现状及标准流程，当有这10个拣选任务时，拣选人员需要一次对其进行拣选以完成此次拣选任务。则其拣选路径即为M→A→B→C→D→E→F→G→H→I→J→M，总时间成本为109.6。该拣选作业的路线如图2所示。

而经过改善，通过计算机编程求解最终，得出最优路线为M→D→F→B→H→E→I→C→J→G→A→M，总时间成本为44。该拣选作业的最优方案如图3所示。

经过改善，拣选成本由原来的109.6降低到44，降低了60%。

3  结论

本文在对在智慧物流的大环境下，利用先进的物流设备，灯光拣选和多层料架结合的方式，降低拣选人员的寻找，检查等动作，从而达到降低成本的目的。在上述改善思想的前提下，建立了以最低拣选成本为目标的数学模型，采用遗传算法与粒子群算法相结合的方式对其进行求解。验证提出的方案是有效的合理的，大大降低了拣选成本。

参考文献：

[1]聂剑平，凌四根，彭发恒，等.一种新型的拣选技术——Flowpicking[J].物流技术，2017，36（2）：51-55.

[2]李悦来.智能型自动分拣机的设计[J].机械设计，2011，28（7）：76-83.

[3]王柏松.名华与宝马的协同管理on site模式应用研究[D].兰州：兰州理工大学，2013.

[4]Goldberg D E. Genetic Algorithm in search[J]. Optimization and Machine Learning， 1989， （11）： 3-26.

[5]Holand  J.H.  Adaptation  in  Natural  and  Artificial  Systems  [M].Massachusetts： MIT Press， 1975.

[6]马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012，29（4）：1201-1206.

[7]J Kennedy， R C Eberhart. Particle Swarm Optimization[J]. Proc. IEEE International Conference on Neural NetworksUSA， IEEE Press. 1995，4： 1942-1948.

[8]DAS P K， BEHERA H  S， PANIGRAHI B K. A  hybridization of an improved partivle  swarm optimization and gravitational search algorithm for multi-robot path planning[J]. Swarm and Evolutionary Computation. 2016，28： 11-28.

[9]陳曦，蒋加伏.免疫粒子群优化算法求解旅行商问题[J].计算机与数字工程，2006，34（6）：10-13.

[10]张鑫源，胡晓敏，林盈.遗传算法和粒子群优化算法的性能对比分析[J].计算机科学与探索，2014，8（1）：91.