基于启发式算法的订单分批问题研究，本文主要内容关键词为：启发式论文,算法论文,订单论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
doi：10.3969/j.issn.1674～4993.2015.11.041 【中图分类号】F253 【文献标识码】B 【文章编号】1674～4993(2015)11～0105～04 1 引言 在物流中心的各项活动中，分拣是最为重要的一项活动，其成本约是整个中心运营成本的50％～65％[1]，分拣的效率不仅关系到整个运营的成本还直接影响到客户服务水平。而订单分批通过将多个订单合成一个批次或更大的订单以提升拣选设备的利用率并减少工作量，使得分拣过程得以更有效地实施。随着订单数目的增加，可行批次的数量以及决策变量的数量呈指数增长，许多基于最优化算法的研究都具有比较大的局限性，所以采用启发式算法解决订单分批问题得到了广泛的共识。早期的研究主要凭借以往的经验对订单分批过程进行优化。例如对客户订单按照某种事先确定好的优先级进行分批，先到先服务(First Come First Serve，FCFS)准则是其中最常用的一种。Elsayed[2]在1981年提出种子算法的概念，该算法对每个批次选定一个种子订单，余下的订单将按照某种配对原则添加到批次中。Ho和Tseng[3，4]等对种子的选取规则以及订单配对原则的选取进行了深入的研究。李诗珍对种子算法以及节约算法进行了初步的探讨[5，6]。Elsayed和Unal[7]在节约算法的基础上提出了一种有效的算法用于求解订单分批问题，通过比较每两个客户订单合并后的路程节约量进行分批，从节约量最大的订单对开始，余下的订单对按照节约量非增的顺序被分配到下一批次中，每次分配订单的时候都重新计算节约量。 综上所述，订单分批问题的求解方法是国内外研究的重点，一些经典的启发式方法如先到先服务、种子算法、节约算法在实际中得到了广泛的应用，这些算法的特点是直观易行并且计算快速，常用来求得问题的初始解或作为检验新算法有效性的基准。本文提出一种降批次启发式方法，并与经典的算法进行比较。 2 问题描述和模型建立 订单拣选可以说是物流中心最耗费时间的作业，根据以往的经验，减少拣选所花费的时间能够有效节约人力成本。同时，拣选时间是交付提前期的重要组成部分，减少拣选作业时间能减少客户订货周期从而提升客户服务水平。 当客户订单到达，为了完成客户订单所指定的物品的拣选，拣货人员需要花费的时间也被称作订单处理时间，其中行走时间对整个订单处理时间的影响最大。假设拣货人员在拣货过程中采用匀速行走，减少行走时间可以等效为减少总的拣选路程。 订单分批是这样一个过程：待拣选的物品被安排到每一次往返于仓库的行走过程中，每次往返拣选一方面受限于拣选设备的容量，另一方面也取决于订单所包含品项占用的空间大小。客户订单尽量被安排到一次拣选路程中直到拣选设备的容量被用尽为止，这些需要在一次往返路程中完成的订单为一个批次。许多文献中拣选设备容量有不同的意义，既可以指订单的数目也可以是物品的数目，本文指的是物品的数目。综上，订单分批问题可以描述如下： 对于给定的拣选设备容量以及路径策略，如何将客户订单以及所要求的有固定储位的待拣选物品分批在一次往返拣选中完成从而使得所行走的路程最短? 本文采用Gademann和van de Velde[8]提出的订单分批模型，该模型具有简洁直观的特点非常适合用来进行订单分批问题的探讨，该模型明确考虑到每个可行的批次，设订单集合O有n个订单需要拣取，每个订单中含有一定数量的物品，并设B为可行的批次集合，可以建立如下数学优化模型： 目标函数：
该模型要求每批次订单在一次往返拣选路径中完成，以使得所有批次总的拣选路程最短。约束条件(2)保证了每批订单所包含的品项数不超过拣货设备的容量，约束条件(3)和(4)则保证了每个订单必须且只能被分配一次。 3 路径策略下的计算方法 上述优化模型的目标是最小化拣选路径，对于启发式算法的评估依赖于相应的路径策略，由于具体选择哪种路径策略并不会对评价分批结果的好坏产生影响，本文的算法采用S型路径策略。在实际应用中，S型路径策略是最为常见的，采用S型路径策略计算拣选路程不仅直观而且易于实现。本节讨论一种S型路径的计算方法，该方法灵活易于扩展，而且最为重要的是不影响我们对订单分批问题的讨论。一个典型的单区型无交叉走道的货架摆放如图1所示：
图1 仓库货架摆放示意图 则拣货人员在拣选过程中通过的路程可近似计算如下：D=LENGTH[，_OF_RACK]×(Nl+λ)+WIDTH×Nw+CORNER×Nc
其中： LENGTH_OF_RACK：货架(走道)的长度； WIDTH：货架的宽度； CORNER：拣货人员到达通道尽头的转角距离；
：人员通过的走道数目； Nc：拣选设备转过拐角的数目； Nw：拣选设备通过货架两侧的次数即通过货架宽度的次数； Last：拣选设备通过的最远的通道数。 λ的取值取决于需要穿过的通道的数目，当需要穿过的通道数目为奇数时，拣货人员需要多穿越一次。值得注意的是，当拣货员通过的最远通道数为一即只有第一个通道有货物需要拣选时，最好拣选方法是返回策略即拣完最后一个货物就返回，本文在此进行了简化，认为此时拣货员需要通过整个通道再返回，即： D=LENGTH_OF_RACK+CORNER。图2表示当Nl=2，last=3时路程的计算情况，蓝色的方块表示拐角被计算一次，红色的方块表示货架宽度被计算一次，粉色的区域表示走道被通过。
图2 路径计算方法示意图 4 启发式分批算法 4.1 根据优先级规则进行分批 通常拣货员在进行拣选作业之前会对订单进行简单的分类，比如按照时间顺序，品项数目多少的顺序等，然后对这些订单按照某种规则制定拣选的优先级，先到先服务(FCFS)是最常用的一种基于优先规则的分批算法，FCFS按照订单到达的顺序对订单进行分批。 4.2 种子算法 种子算法自从1981年被Elsayed提出，种子含有“最初”的意思，即种子订单是每个批次的初始订单。种子算法是一种连续生成订单批次的方法，因此，初始批次的选取对后面的分批有很大影响，种子算法进行分批主要有两个过程：一是种子订单的选取；二是根据订单的相似度进行配对。使用种子算法进行订单分批，首先对初始批次选择一个种子订单，然后按照配对原则从剩余订单中选出一些订单加入该批次，加入时要考虑拣选设备的容量，如果当前批次无法容纳更多的订单，则考虑一个新的批次直到所有订单都在某个批次内。 4.3 节约算法 种子算法忽略了与具体目标函数的联系，使得算法性能具有某种不确定性，节约算法通过计算每两个订单合并后路径的节约量来匹配订单，所有订单间的路径节约量被存放在一个被称为节约矩阵的矩阵里，其行和列均代表订单的编号，索引为(i，j)的元素表示第i个订单与第j个订单合并产生的节约量。节约算法的思想来自于Clark和Wright对车辆调度问题的研究，每次将订单安排进某个批次就对节约矩阵进行更新，使得批次中的订单与剩余订单重新计算节约量，这样剩余订单更可能选择那些能获得最大节约量的批次加入。 4.4 降批次启发式算法 本节根据订单分批问题的特点提出一种降批次算法用于求解分批问题。在分批问题中，订单的分批数量是影响优化结果的一个关键性的指标，分批数量越少则结果可能越好，每个批次在一次拣选路径中完成，则越少的批次意味着越少的拣选次数，拣选的总路程也相应更少。受拣选设备容量的限制，理论的最小批次数为订单集合的物品总数与拣选设备容量的比值，一般要在理想情况下才能取到这个值。降批次算法正是出于上述考虑提出的，该算法的过程如下所述：首先将一系列订单进行排序，排序将订单按品项数从大到小排列。然后依次将订单放入每个批次中，第i个订单放入第i个批次，批次的数量等于订单的数量，然后依次对最高的批次进行降批即逐步减少批次数量，将高批次数中的订单放入任意低批次中并检查是否满足约束条件，如果不满足则将其作为一个独立的批次，重复上述过程直到无法再进行降批次操作，算法停止。
图3 降批次算法伪代码 降批次算法不同于前面几种方法，无论FCFS还是种子算法或是节约算法均是采用连续产生批次的方法，降批次算法采用一种逆向的思路，先将订单分成批次，然后对批次的内容进行调整，相当于每个订单都是一个种子，从而减少了选择种子的过程。 5 启发式方法求解性能比较 考察上述启发式方法在不同订单集合下的优化性能，通过设置不同的订单数量测试算法的适应性，对FCFS算法、种子算法、节约算法和降批次算法进行了比较，其中种子算法选用最小通道数目的选择策略和随机的匹配策略，节约算法按照节约矩阵选择种子订单对，然后根据随机原则将未分配订单加入到已有批次中。表1显示了在订单数目分别为10、15、20、25、30、35时各算法平均最小批次数量以及平均路径改善率的情况，这里每个订单品项数均随机产生且均匀分布在[10，30]区间上，拣选设备容量为40，仓储布局为传统的单区型仓库拥有6条纵向走道240个储位，采用S型路径策略和随机存储策略，表中的值为10次试验所取平均值。算法路径改善率随订单数目变化情况如图4所示。由图4可看出在随机产生订单的情况下不同的算法得到的结果的优异程度，节约算法的路径改善率是四种算法中最大的，降批次算法则具有几种算法中最少的分批数量。种子算法则显得中规中矩，FCFS的结果最糟糕。然而并不能据此得出某个算法比另一个更好的结论。 表2显示了在同等条件下拣选设备容量为60时的情况。算法路径改善率随订单数目变化情况如图5所示。 表中节约算法的批次数量最大，但是仍然获得了很好的路径改善率，可见批次数量少并非是路径改善率高的必要条件，种子算法在这种情形下的表现最好。当拣选设备容量为60而订单品项数均匀分布于[10，50]区间上，其结果如表3所示。算法路径改善率随订单数目变化情况如图6所示。
可见，算法的性能受拣选设备容量以及订单品项分布情况共同的影响，当品项数分布接近拣选设备容量上限时，节约算法和降批次算法具有更好的性能，当品项分布远小于容量的限制，FCFS和种子算法则较以往有更好的表现。综合来看，在两种情况下节约算法和降批次算法都提供了更好的分批结果，尤其是节约算法，这与以往的研究结果一致。降批次算法在一些拣选设备有限的情形则可能有更好的表现。 6 结论 本文分析了订单分批问题及其求解思路，然后介绍了三种启发式分批算法，并在此基础上提出了一种旨在减少批次数量启发式算法——降批次算法，最后对上述四种算法进行了比较，发现在最小化路径模型的分批问题中节约算法和降批次算法具有比较好的性能。启发式方法还受到订单品项分布和拣选设备容量限制共同的影响，采用不同的启发式算法的性能具有差异性。
标签：启发式算法论文; 算法论文;
