基于分区拣选策略的分拣机系统综合优化研究

发布时间：2020-07-12 12:35

【摘要】：随着我国经济的不断发展,配送中心的商品拣选日益呈现小批量、多品种、高时效的发展趋势,对订单处理时间提出了更高的要求。拣选系统是处理客户订单的关键环节,其工作效率往往成为制约配送中心吞吐能力的瓶颈。据统计,订单拣选成本可占到配送中心总作业成本的60%,订单处理总时间可占到总作业时间的40%左右。为有效降低订单处理总时间,越来越多的行业采用自动拣选系统,如卷烟、药品行业配送中心的分拣机系统。在各种自动拣选系统中,分拣机系统最适合处理多品种、小批量的订单货物。在不显著增加作业成本前提下,分拣机系统多采用分区拣选策略降低订单处理总时间。该策略下分拣机系统划分为若干拣货区,各区分拣机共同拣选同一订单货物并送至缓冲区,然后在恰当的时机合流货物,完成订单处理。因此,研究分区拣选策略下的分拣机系统优化问题,对于降低订单处理总时间,节约物流成本具有重要意义。然而,目前国内外学者关于此领域的研究存在若干问题。一是研究对象多集中在人工拣选系统,很少涉及到分拣机系统,而人工拣选系统中订单处理总时间构成与分拣机系统差别很大。二是关于分区拣选策略下的综合优化研究较少,多为单一影响因素优化,如品项分配优化。三是关于分拣机系统研究多集中在设备选型优化与改造方面,较少涉及对拣选策略和方法的优化。基于此,本文提出分区拣选策略下的分拣机系统综合优化问题。该问题以订单处理总时间最小为优化目标,研究内容包括该策略下影响订单处理总时间的各主要因素：拣货区数量、货物合流模式、品项分配、品项拆分。相比对单一因素的优化分析,本文研究问题更为复杂。在研究该问题过程中,本文主要内容与成果如下： (1)通过设计排队系统描述分拣机系统在分区拣选策略下的工作流程,建立了综合优化问题模型。设计了排队系统描述分区拣选策略下分拣机系统工作流程,得到了订单处理总时间的结构组成：货物拣选时问、分拣机暂停时间、货物合流时问；得到并分析了各主要影响因素：拣货区数量、货物合流模式、品项分配、品项拆分。以此建立了分拣机系统综合优化问题模型,优化目标为订单处理总时间最小,涉及变量包括各主要影响因素,该模型属于复杂整数规划问题。 (2)为降低模型求解难度,将优化目标转化为实现最佳订单拣选量分配结果,并将综合优化问题拆分为两大子问题,采取先独立讨论再综合求解的思路。通过线性规划松弛与代理松弛模型约束条件,得到订单处理总时间下界函数和最佳订单拣选量分配结果：各订单拣选量均匀分配到各拣货区。将该结果作为新的优化目标,降低了模型求解难度,扩展了求解方法。根据变量特点,将综合优化问题分解为品项分配与品项拆分子问题分别讨论,以便最终确定综合求解方法。此外,通过在不同合流模式下分析下界函数与拣货区数量单调性关系,得到了更小的拣货区数量范围,降低了解的遍历空间。 (3)品项分配子问题中,提出了基于拣选量均分的品项聚类目标,设计了复合聚类算法求解。首先介绍了学者Jane的聚类目标,分析其缺陷后根据最佳拣选量分配结果,提出了基于拣选量均分的聚类目标,并在向量空间中以曼哈顿距离描述。然后介绍了常用的层次聚类算法,分析其缺陷后提出了复合聚类算法。该算法通过改进最长处理时间优先算法(Largest Processing Time, LPT)的静态聚类算法得到良好初始解,再采用改进的K-means动态聚类算法优化初始解。最后实例分析证明了基于拣选量均分的聚类目标与复合聚类算法优越性。 (4)品项拆分子问题中,通过EIQ分析方法初步拆分品项,并提出子品项拣选量再分配问题,根据问题特点设计了回溯法求解。在初步拆分品项的EIQ分析中,将品项按拣选总量降序排序,并通过累加拣选量所占比例确定拆分品项。然后各选定品项都拆分为两个子品项,将其在各订单拣选量平均分配。为优化初步品项拆分结果,提出子品项拣选量再分配问题。以最佳订单拣选量分配结果为优化目标,建立了数学模型并提出回溯法求解。根据问题特点,在组织和搜索解空间过程中两次降低了解的搜索范围。最后实例分析证明了回溯法的有效性。 (5)根据各子问题讨论结果,提出分拣机系统综合优化问题的综合求解方法。综合求解方法结合了枚举法与多种启发式算法,首先初步拆分品项并确定拣货区数量范围,然后进行品项分配优化与子品项拣选量再分配优化,最后通过判断算法结束条件迭代优化,得到了两种合流模式和拣货区数量范围内的有限组解,通过比较各解对应的订单处理总时间确定最佳求解结果,既降低了综合优化问题的求解难度,又在较大空间中搜索了可行解。实例分析证明了该方法的有效性和优越性。
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：N945.15
【图文】：

系统布局,分拣机,策略,拣货

输送带的工作速度要明显高于分拣机各通道的拣货速度。此外，如图2一1所示，分区拣选策略下，分拣机系统还需配备缓冲区，以暂存输送带上的拣出货物。缓冲区入口处位于拣货区内输送带末端，由动力式输送带或重力式滑道构成，进入缓冲区的货物在重力或摩擦力作用下实现密集排列。缓冲区出口处与合流输送带连接，并装有挡板机构。分拣机系统通过控制挡板打开与关闭，将暂存货物送入合流输送带，完成货物合流工作。2.2订单处理总时间分析为得到订单处理总时间的结构组成，需要分析分区拣选策略下的系统布局与工作流程。如图2一2所示，分区拣选策略下，分拣机系统划分为多个独立拣货区，一条主输送带连接各拣货区末端的缓冲区。处理订单时，各拣货区内分拣机共同拣选同一订单货物并送入缓冲区，然后在合流输送上完成货物合流并送至包装系统。由于各拣货区内的分拣机并行工作，故降低了订单处理总时间。

时间分布,模式图,拣货,订单处理

山东大学博十学位论文恢复工作。据此可得到各拣货区合流流程，如图2一4所示;也可得到各拣货区在处理每份订单的时间分布，如图2一5所示。l号拣货区2号拣货区…z号拣货区砂}拣选匆雨薄贾物卜，尸刊病;选薪行革贾骊卜，户}拣选新订单货物}归乙<不羌成互<了先成瓦<汽七辰备是暂停皿_作等待z号拣货区货物合流杏是暂停工作等待1号拣货区货物合流杏是暂停工作等待z一1号拣货区货物合流完成完成完成+是货物合流_乡是货物合流令是货物合流完成图2一4串行合流模式下各拣货区工作流程号拣货区.订单l’-1拣选时间口暂停时间订单i.合流时间订单r·…亩口图2一5串行合流模式卜各拣货区订单处理时间分布根据货物合流条件及图2一4、2一5，可知暂停时间等于相邻前一拣货区货物合流完成时刻减去木拣货区货物拣选完成时刻，由此可得到各拣货区在处理各订单

工作流程,拣货,货物,暂停时间

图2一7并行合流模式下各拣货区子订单处理总时间分布根据货物合流条件及图2一6、图2一7，可知暂停时间等于最晚的拣货区货物拣选完成时刻减去本拣货区货物拣选完成时刻。由此可得到各拣货区在处理各订单的暂停时间，如式(2一9)所示:哎·肥畔)一《，1‘i丛r，l以勺(2一9)

【参考文献】