爱华网[关键词]供应链管理；人工拣选；粒子群算法
[DOI]10.13939/j.cnki.zgsc.2017.12.251
1 引 言
随着电子商务的迅速发展，大批量、小额以及个性化的订单的配送成为人们普遍思考的问题，拣选作业在配送中心的整个作业流程中占的比例较大，有效地减少拣选所用的时间对于提高整个配送中心物流效率具有重要的意义。通过优化订单分批方式以及拣选员的行走路径能够有效地减少配送中心的配送成本，提高顾客的满意度。[1]
2 粒子群算法
在求解订单分批的问题中粒子群算法具有独特的优越性，本文应用粒子群算法对订单分批问题进行求解，在PSO算法中，粒子群中的每一个都是在一个n维空间中搜寻，其中每一个粒子所处的位置都可以看成模型的一��解，每个粒子通过速度更新公式不断调整自己的位置，每一个粒子对形成的最优解具有记忆力，记作Pid，粒子群运动过程中最好位置，记作Pgd，每一个粒子都有自己的一个速度V。粒子群算法的基本公式如下：
PSO算法是一种进化计算方法，采用一代一代迭代的方式进行更新，在这个过程中，粒子群体中的粒子通过初始化赋予每个粒子初始位置，根据速度更新公式，产生下一代更好的个体，新一代粒子群体在前一代的基础上产生，经过比较后，用适应度更好的粒子来取代当前粒子。PSO算法其余的启发式算法一样具有快速的寻优能力，其次可以改变其中的参数对算法进行调整适应性强，算法简单。
3 PSO算法模型仿真
3.1 编码设计
对于像分批这种离散问题，采用数字对所有的订单进行编码，把每一个批次用一个自然数字串与之对应，在该自然数字串中有不同或者相同的数字，分别表示order所在的batch，设有订单解数字序列（O1，O2，…，ON），该数字序列对应着N个位置，由该数字串生成的每一个基本数字串都代表这一个基本的批订单粒子，比如X={x1，x2，…，xN}表示一个批订单，每一个批订单数字串xi=j，j∈（1，2，…，batch），数字串里的每一个元素表示当前订单被分配到哪个批次中去。[2]
3.2 粒子群的拓扑结构
粒子通过一次次的更新迭代，调整自己的行为，同时也根据自己对整个群体的认知情况调整自己的行为，每个粒子都可以决定自己向群体中的哪个粒子进行学习，如果这个粒子是整个群体中的，则把他称为精英粒子，如果是该粒子周围的粒子则称为邻近精英粒子，如何选择精英粒子进行学习决定了整个算法的收敛速度，经过试验验证，采用向整个群体中具有最好适应值的精英粒子进行学习具有更好的收敛性。每一个粒子学习的粒子数量还可以不只是一个，可以是多个精英粒子，精英粒子越多，收敛速度也就越快。
3.3 位置更新方式
订单分批问题是典型的离散值更新公式，学者刘建华[3]通过对PSO算法公式进行了适用于分批的改造，每个粒子的位置采用一种二进制数表示，每个批订单粒子通过sigmoid函数映射到区间[0-1]上去。在这些的基础上进行了改进：前面采用了自然数而不是0和1对每组分批订单进行了分批的编码，因此每一组粒子位置向量的解向量取值就不是0和1，而是订单分为几批就有几个自然数，如果订单分为8批，出现的批次数为1，2，3，4，5，6，7，8这8个自然数，如果某一位为m则表示第i个订单被分到了第m批次中。而粒子的运动过程是由粒子的速度决定的，而订单的分批过程中没有这个概念，这里将每个粒子的速度映射为概率串，它表示每一位增加或者减少的可能性，位置的改变同样不再是加上速度，通过设定一定的概率，每一个粒子依据这个概率进行加减一个常数操作，这里的常数设为C是一个预设的常量，如果订单的数目较少的话，C的取值可以较小，如果订单数目较多，可以适量增大C的值以加快收敛速度。
其中rand（）的值在[0-1]之间取值，通过速度映射函数的图像可以看出，如果速度的取值过大，也就是接近于1的话，那么位置一定会改变，订单分批方式一定会改变，这样的分批就失去了随机性，因此必须随速度值进行限制，这里做出如下规定，即速度值最大为6。
3.4 可行解保证
经过速度位置公式的变更可能产生一些不满足要求的解，因此必须对解的范围进行限制，比如说可能产生这样的解，X=（0，1，-5，3，7，5，17），在这个数据串中的每一个数字代表的是订单所属编号，但这里出现了类似负数这种不合理的编号，这明显是不符合分批要求的，但却是合理的，如果仅用不同的 数字表示不同的批次是有意义的，只需要保证批次的编号是连续的。将X按照升序进行排列得到Y=[-5，0，1，3，5，17]，依次检查X中的每一个分量，将X中的分量与Y中的分量一一对应，如果X中的第m个分量等于Y中的第n个分量，那么久将X中的第m个分量变为n，Xi=（4，2，1，2，3，3，4），通过这个变换后，没有了负数以及较大的数，但是还是无法保证完美，为了更好地在分批中应用，这里加入一个条件，通过把数据代入到一个改正函数中去，从而使得数据具有可行性。
3.5 参数设置
在PSO算法速度更新公式中有w、C1、C2三个参数，这些参数用来调节粒子对局部粒子的学习能力和全局粒子的学习能力，根据Shi和Eberhart最早提出一个权重系数来控制上代粒子对当前粒子的影响程度，他们建议将w的值取在[0.9-1.2]之间，这样由于数值较为接近1，表明上一代粒子的速度影响程度，这个值越大，粒子的局部搜索能力就越强，然而这样设置到了后期容易陷入局部最优，因此Shi和Eberhart把对参数的设置进行了改造，决定重要性的参数不再是一个常数，而是一个可以变动的数值，算法在刚开始进行迭代计算的时候采用的是Wmax，伴随着总的计算量的增加，参数逐渐变小，最小值设为Wmin.
学习因子定义了粒子的学习能力，这个因子分为两部分，其一是向局部粒子的 学习能力，其二是向全局粒子学习的能力，分别用参数C1和C2来表示，之前的文献中有的取值C1=C2=2，这里同样采用，初始惯性权重值设为w=1.2，通过下图可以看出当C1=0，C2=3也就是C1取值较C2小时，在第50代就取到了最优值，说明有良好的局部搜索能力，当C2=0，C1=3时，路径值收敛到了一个较大的值，这说明粒子具有良好的向精英粒子学习的能力，因此为了找到更好的解，这里设置C1=1，C2=3，这样不仅搜索范围更大，且具有良好的局部搜索能力。这里对具体参数设置如下：惯性权重w=1.2，学习因子C1=0，C2=3，种群数量50，迭代次数300。
4 结 论
当C1=0，C2=3时，算法的收敛速度较快，在第50代左右就收敛到了最小值，算法收敛到1600。当C1=3，C2=0是粒子群算法收敛到了一个较大的值2100，原因是C1的值比较大，算法强调向周围精英粒子学习，容易陷入局部最优，由于C2=0，对全局精英粒子不学习，因此收敛的值比较大，不是最优的收敛结果。当C1=1，C2=3时，算法收敛到1500左右，明显优于以上两种情况，这是由于算法在计算的时候，即向局部精英粒子学习，又根据全局精英粒子对自己的位置进行调整。这时对应的batch size为5次，比之前模型求出的结果6相差不大，通过参数的设计最终收敛于1500m，相对于其他的记过有明显的路径方面的节省，通过对订单分批进行了粒子群算法的优化，记过表明，通过应用启发式算法，确实能够明显减少订单拣选时间，产生明显的效果。采用粒子群算法，比先到先服务（FCFS）、固定时间窗分批、节约算法（SAVING）这些方法，PSO算法能有20%左右的改善，并且还具有良好的适应性，因此采用粒子群算法具有良好的效果。
参考文献：
[1]李泽.电子商务（B2C）作业下人工拣选成本分析[J].电子商务，2014（5）.
[2]陈曦.离散粒子群算法的改进及其应用研究[D].合肥：安徽大学，2014.
[3]刘建华.粒子群算法的基本理论及其改进研究[D].长沙：中南大学，2009.
