【作者】 王艳艳；

【导师】 吴耀华；

【作者基本信息】 山东大学 ， 控制理论与控制工程， 2012， 博士

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

【Abstract】 As the shorter product lifecycle, the market with the characteristic of batch becoming gradually thinning and the trend of increasing commodity requirement including small batch, variety and shorter lead time leads to the gradual increase of picking cost in distribution center. To reduce the total cost of order picking effectively, the manual picking system was replaced by the automated picking system that is suitable for dealing with variety, small batch orders and works quickly, as a result, the picking time and labor intensity is reduced greatly, as well as the working efficiency and picking accuracy are increased greatly, hence more and more distribution centers of various trade have adopted the automated picking system.With the development of automated picking technology, in order to reduce the influence of each working process on picking efficiency and the coupling between picking process and replenishment process, the complex parallel automated picking system with the presorting function appears. This system takes advantage of time when single sorter is free to presort the next order. It will rapidly sort the commodity required by an order to the transport system.The average method of the each SKU picking quantiy is widely used by the parallel automated picking system, and this method is fast and effective, easy to implement, but a lot of waiting time appears to reduce the picking efficiency. The total equalization allocation method based on each distribution line is used in sorting scheduling policy, which increase the number of chanaging sorter SKU and greatly extend the total picking time. Therefore, studying parallel automated picking system is pretty meaningful for reducing total picking time, which can save logistics cost and promote service efficiency of the distribution center.However, the research on picking (sorting) field by domestic and overseas scholars mainly focuse on the artificial picking system while the picking mode between artificial picking system and automated picking system is greatly diverse. The research on automated picking system mainly concentrates on the transformation of sorter, selection and configuration optimization of picking equipment, while it rarely involves the studying of picking strategy and picking task allocation methods of optimization about automated picking system. In picking system of replenishment research mainly focuses on replenishment path optimization on the condition that the replenishment equipments are fixed, rarely on the design of optimization of relating equipments of automated replenishment system.Based on these, this paper deeply studies on the subproblem of automated picking system optimization including SKU splitting optimization, sorting scheduling policy optimization, restocking buffer optimization by the comprehensive utilization of order analysis, iterative optimization, clustering analysis and so on. During the researching process, the main content and achievement are below:(1) The modeling of parallel automated picking system.The mathematical optimization model of parallel automated picking system is established by analyzing its working flow. Firstly, the working flow of parallel automated picking system is described by virtual window theory and the picking time task model is established. Secondly, the mathematical model with respect to picking delay time of all picking machines and its quantity is established by analyzing picking delay time as one of the key factors which influence picking time deeply.(2) The SKU split optimizing of parallel automated picking system.In items of the SKU splitting, the more SKUs need to be splitted, the easier the efficiency of picking system improve while lead to increase the number of picking machines, and greatly increase the investment of distribution center. To promote picking efficiency on the condition of splitting less SKUs, it is needed to make the picking quantity of picking machine correspond the SKUs splitted. Firstly, the SKUs splitted by EIQ method before SKUs splitting optimization are determined. Secondly, according to the change of delay time before and after splitting SKU aiming at the SKUs splitted, three necessary conditions accordding with quantity of picking are put forward and proved. The SKU splitting optimization model based on delay time is established. Lastly, in view of the characteristics of the larger number of orders and the larger quantity of SKU splitted, this paper designs a Heuristic Adaptive Genetic Algorithm to solve the SKU split optimization model, and the simulation results of reducing about9%total picking time show that the optimization model and HAGA Algorithm of SKU splitting.is superior.(3) The sorting scheduling policy optimization of parallel automated picking systemThe Sorting scheduling policy optimization problem of picking system is tranformed to clustering problem and solved by designing a composite clustering algorithm in this paper. Firstly, it is put forward to cluster through choosing the distribution lines as the basic unit in accordance with the SKU structure similarity of orders based on the characteristics of the sorting scheduling. Here the step as belows: all the SKUs are described as vectors of multidimensional space. The space dimension is equal to the number of distribution lines. The vector in each dimension is equal to the transformed standard SKU picking quantity of the orders of distribution lines. Minimum variance clustering target model is established between each cluster. By use of the Euclidean distance, this paper translates the sorting scheduling policy optimization problem into order batching clustering problem. Secondly, basing upon the defect of hierarchical clustering method and k-means clustering method, the composite clustering algorithm based on hierarchy and partition is put forward, here the step as follows:the initial feasible solution is got by simplifying the hierarchical clustering method. The initial solution by using the improved dynamic clustering algorithm is optimized. It balances the relationship between expanding the search space and improving the velocity of solution very well basing on the division. Lastly, the superiority of clustering target model basing on minimum variance and composite clustering algorithm is proved by using examples.(4) The restocking buffer length optimization of automated restocking system.In terms of the automated restocking system corresponding with the automated picking system, if the restocking buffer length is too short, it will influence the efficiency of picking system, while if the restocking buffer length is too long, it will increase the total investment of equipments. The optimization of restocking buffer design is studied in this paper. First of all, according to the overall analysis to working flow of the automated restocking buffer in the automated picking system, a balanced mathematical model of the commodity on conveying equipment input and output is established, as well as the optimal condition and critical condition when restocking buffer length contenting the picking task are put forward and proved. Secondly, according to the layout relationship between the restocking system and the picking system, the mathematical models reflecting the process of the arrival of the commodity and the restocking buffer length optimization is established. Lastly, the heuristic clustering method of "first clustering, ranking after" is designed on the condition that it makes the difference of average outbound time of two SKUs basing on mission sequence as the correlation of the two SKUs, then, preparation system SKU distribution optimization that can reduce the arrival time of commodity from restocking system to shorten the restocking buffer.In order to validate the proposed method and the high efficiency of the algorithm, this paper takes the waterfall automated picking system designed for the tobacco industry by a logistics technology Co.LTD. as the research object. The algorithms and models are confirmed by some examples based on the real customer order data of multiple regions’s cigarette logistics distribution center. The calculation results show that the proposed algorithm and the optimization model can solve not only the automated picking system task optimization of mass orders but also the design of restocking buffer length optimization problems very well.更多还原