并行自动分拣系统分拣任务及补货缓存优化研究

发布时间：2020-04-17 14:14

【摘要】：随着产品生命周期的逐渐缩短,以批量为特征的市场逐渐细化,小批量、多品种、高时效的货物需求不断增加,这种趋势导致配送中心的分拣作业成本逐渐增加。为有效降低分拣作业成本,适合处理多品种、小批量订单的自动分拣系统逐渐代替人工拣选系统,大大缩短了货物拣选时间,降低了作业劳动强度,提高了货物拣选准确率和作业效率,目前越来越多行业的配送中心开始采用自动分拣系统,如：卷烟、医药等。随着自动分拣技术的发展,为了减少其它作业工序对分拣效率的影响,降低各作业工序之间的耦合性,出现了具有预分拣功能的复合式并行自动分拣系统。该系统利用单个分拣机不分拣的时间,提前把下个订单的货物预分拣完毕,当分拣到该订单时,快速把货物分拣到输送系统上。目前并行自动分拣系统同一品项分拣量拆分时广泛采用均分法,此方法快速有效、便于实施,但同一分拣线上分拣机间会出现大量的等待时间,降低分拣作业效率；分拣调度常采用以配送线路为基本分配单位的总量均分法,增加了分拣机品项停机调换次数,大大延长了分拣作业时间。因此,研究并行自动分拣系统的优化问题,对减少分拣作业总时间、节约物流成本、提高配送中心的服务效率具有重要的意义。然而,国内外学者关于货物分拣(拣选)领域的研究主要针对人工拣选系统,而人工拣选系统的作业模式与自动分拣系统的作业模式差别很大。目前针对自动分拣系统的研究,主要集中在分拣机设备的改造、多种形式的分拣机选型及配置优化方面,很少涉及自动分拣系统的分拣策略和分拣作业任务分配方法的优化研究；针对分拣系统中补货的研究主要是在其固定补货设备下的补货路径优化,很少涉及指导自动补货系统相关设备设计规划的优化研究。基于此,本文综合利用迭代优化、聚类分析等工具对订单进行分析,针对并行自动分拣系统品项分拣量拆分优化、分拣作业调度优化、补货缓存优化三个重要子问题进行深入研究。本文的主要研究内容与成果如下： (1)并行自动分拣系统建模。在研究并行自动分拣系统作业流程的基础上,建立了并行自动分拣系统分拣作业总时间的数学模型。首先,利用虚拟视窗理论描述了并行自动分拣系统的作业流程,建立了货物分拣作业时间模型；其次,对影响分拣作业时间的关键因素——分拣延迟时间进行深入分析,建立总分拣延迟时间最短的分拣量分配目标模型。 (2)并行自动分拣系统分拣量拆分优化。在品项拆分问题中,拆分的品项数量越多,分拣系统的作业效率越高,但是分拣机的数量会大幅度增加,进而增加了配送中心投入设备的成本。本文研究了在较少品项拆分条件下,优化所拆分品项对应分拣机的分拣量,减少分拣作业总时间,提高分拣作业效率。首先,在分拣量拆分优化前,通过EIQ (Entry, Item, Quantity,订单品项数量)方法确定订单中的拆分品项；其次,针对需要拆分的品项,依据拆分前后分拣延迟时间的改变,建立了基于延迟时间的分拣量拆分优化模型；最后,鉴于订单个数比较多以及拆分品项的分拣量相对比较大的特点,提出了品项拆分优化的三个必要条件并予以证明,设计了启发式自适应遗传(Heuristic Adaptive Genetic Algorithm, HAGA)算法对分拣量拆分优化模型求解,仿真实例结果表明了分拣量拆分优化比均量拆分方法减少9%左右的分拣作业时间。 (3)并行自动分拣系统分拣调度优化。本文将分拣调度优化问题归结为订单分批聚类问题,设计了复合式聚类求解算法。首先,根据分拣调度的特点,提出了按照订单品项结构相似度并以配送线路为基本单位进行聚类的方法,其步骤为：将各品项描述为多维向量空间中的向量,空间维数等于拆分品项的个数,向量在各维的值等于各品项在配送线路订单中的分拣量标准转化后的数量,利用欧氏距离,建立了各个簇之间均方差最小的聚类目标模型,从而将分拣调度问题转化为订单分批聚类问题；然后,针对层次聚类法遍历范围广和K-均值聚类法初值敏感等缺陷,提出了基于层次和划分的复合聚类算法,其步骤为：通过简化的层次聚类法得到初始可行解,进而利用改进的基于划分的动态聚类算法对初始解进行优化,较好平衡了扩展搜索空间与提高求解速度的关系；最后,用实例验证了基于均方差最小的聚类目标模型与复合聚类算法的优越性。 (4)自动补货系统中补货缓存长度优化。在自动分拣线的自动补货系统中,补货缓存过短,将影响分拣系统的作业效率,补货缓存过长,则会增加设备投入成本。本文针对补货缓存长度的优化问题深入研究。首先,在全面分析自动分拣系统中的自动补货作业基础上,建立了货物在输送设备上达到输入输出平衡的数学模型,提出了补货缓存的长度满足分拣作业的最优条件及临界条件并予以证明；然后,根据备货系统与分拣系统之间的布局关系,建立了补货缓存中货物到达过程的数学模型和补货缓存长度优化模型；最后,以补货任务序列中两品项出库时刻的平均差值作为品项相关度值,设计了“先聚类,后排序”的启发式聚类方法,得到备货系统品项分配的优化方案,缩短了货物从备货区到补货缓存区的到达时间,从而缩短了补货缓存长度。为验证所提方法及算法的有效性,本文以某物流科技有限公司为烟草行业设计的瀑布式自动分拣系统为研究对象,采用多个地市级卷烟物流配送中心的客户真实订单数据,进行实例验证。计算结果表明,本文提出的优化模型及求解算法很好地解决大规模订单的自动分拣系统作业任务优化及补货缓存长度的设计优化问题。
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP273;TH69

【引证文献】