【作者】 刘鹏；

【导师】 吴耀华；

【作者基本信息】 山东大学 ， 系统工程， 2011， 博士

【摘要】 随着社会经济的不断发展,配送中心内部多品种、小批量、高时效的货物拣选需求日益增多。在已有的拣选技术中,通道式自动分拣系统最适合处理多品种、小批量订单货物的快速分拣,能够在提高分拣准确率及分拣效率的同时降低人员劳动强度,目前已逐渐开始应用于烟草、医药等行业的配送中心。通道式自动分拣系统是一类由多种不同吞吐量的通道式分拣设备组合而成的自动分拣系统。该系统的使用虽然可以提高分拣效率,但同时需要增加较多的设备固定投资、人员补货成本并占用一定的空间。因此,设计者和使用者都希望找到一种优化的配置方式,在保证分拣效率的前提下,最小化这种系统的设备投资、人员成本及占地面积。通道式自动分拣系统的配置优化问题包括通道配置优化、品项配置优化、品项分配优化三个子问题。其中,通道配置优化指确定通道的最优长度、最优数量；品项配置优化指确定采用通道式自动分拣系统进行分拣的品项(品项优选)、确定品项与通道的对应关系(品项拆分优化)和确定品项占用通道的数量(通道配比优化)；品项分配优化指确定品项的最优布局。同时,配送中心所需要处理的品项数量往往较多,这使得配置优化问题的求解变得更加复杂,亟需一种定量且快速的计算方法,帮助设计者和使用者做出决策。已有的研究工作往往只在人工补货模式下解决了通道式自动分拣系统配置优化问题的一个方面或者仅仅针对通道式自动分拣系统的一个组成部分进行了配置优化的研究,提供的方法也多为定性的分析方法,无法提供一个全面且易于实践应用的解决方案。基于此,本文提出通道式自动分拣系统的配置优化问题,并综合运用订单分析、排队理论、聚类分析、迭代优化方法等工具,从自动补货和人工补货两个角度对实际规模的问题进行了全面的研究和探讨。在研究该问题过程中,本文的主要内容与研究成果如下：1.基于订单分析的自动补货通道配置优化。首先全面分析了由两种自动补货通道组成的通道式自动分拣系统的工作原理；其次从品项单订单需求量和订货总量两个角度对原始订单数据进行了深入分析,引入“虚拟通道”的概念,将通道配置优化问题拆分成两个子问题,提出了一种“先集中、后拆分”的两阶段方法。第一阶段,假设一个品项仅占用一个较长的虚拟通道,且通道的长度不受限制。在此基础上,根据订单的订单品项数量(Entry-Item-Quantity, EIQ)分析,在模盒循环补货和穿梭车往复补货两类自动补货模式下,分别求解了每个品项对应虚拟通道的最优缓存量。第二阶段,根据实际设备的参数,以设备成本和场地成本之和最小为目标,建立了整数规划模型,将虚拟通道拆分成多个实际的拣选通道。某地市级卷烟物流配送中心的实际应用案例表明,采用本章提出的通道配置优化方案,能够在满足订单需求的基础上有效降低占地面积和设备投资成本,提高配送中心的场地及设备利用率。2.模盒循环补货模式下的品项分配优化。主要研究模盒循环补货模式下,如何求解满足补货需求的最少模盒数,以及能够提高模盒工作效率、减少模盒运行过程中停滞时间的品项分配优化方法。求解过程分成两个阶段：第一阶段,假设模盒能一直不停滞地补货,利用排队论模型求解满足补货需求的最少模盒数,通过实例验证,模盒从原来的42个减少到25个,在满足补货需求的基础上充分提高了模盒的利用率,大大降低了设备投入；第二阶段,考虑模盒在补货过程中会出现停滞的环节,采用“先聚类、后排序”的方法,先将补货请求产生时间接近的品项进行聚类,再按照品项订货总量排序,得到品项分配的优化方案。利用仿真平台IMHS Sim/Animation对品项分配优化前后的方案进行补货过程的仿真,结果表明品项分配通过先聚类后排序的优化后,补货过程中模盒的停滞时间得到了有效地降低,这也使得第一阶段求解出的最少模盒数在实际应用中更具有参考价值。3.人工补货模式下的品项配置优化。在全面分析DAOPS-2PD-MR系统补货模式的基础上,考虑安全库存,提出了补货成本的估计方法。基于扩展的流模型,以某种类型的通道式分拣设备的总补货成本最小为目标,以每个品项分配该类设备的通道数为参数,考虑场地约束,建立了非线性规划数学模型,求解高吞吐量分拣设备和低吞吐量分拣设备的通道配比优化问题,并采用数学归纳法进行了证明。同时,为了确定每类分拣设备通道所占的最优空间,讨论了通道式自动分拣系统快速拣选区缓存空间资源的最优配比问题。最后,考虑通道式自动分拣系统的总体补货成本,解决了品项拆分优化子问题。根据通道式自动分拣系统的固有特点,设计了基于流量序列的启发式算法,有效降低了求解大规模问题的时间复杂度。实例分析证明,相比传统的“订单-品项-数量”(Entry-Item-Quantity, EIQ)方法,本文所提出的启发式算法在求解实际问题时计算效率更高,且所得的优化配置方案在一年的订单周期内为某市的卷烟物流配送中心节省了18.9%的总补货成本。4.综合考虑成本及效率的品项配置优化。在第四章的基础上,综合考虑人员补货成本、设备成本和分拣效率,讨论了DAOPS-2PD-MR系统的品项配置优化问题。首先,深入分析了DAOPS-2PD-MR系统的品项适应度及系统分拣效率的制约因素,并通过5个定理证明了品项适应度与系统分拣效率的相关性。其次,以人员成本和设备成本之和最小为目标,考虑场地约束,建立了混合整数规划模型,求解品项优选问题、品项分配优化问题和通道配比优化问题,并得到了最优的设备投资。最后,针对大规模实际问题,在构造DAOPS-2PD-MR系统分拣效率测算方法的基础上,结合作者多年从事通道式自动分拣系统方案设计、项目实施及运营管理中积累的经验,提出了瓶颈度、粘滞度、需求量、分拣效率四个度量指标,并分别设计了六种品项配置调整算法,以满足实际分拣效率的要求。基于27组实验数据,通过分析需求偏度、需求集中度、分拣效率提升量对六种调整算法的影响,得出考虑品项配置定期变化的粘滞度调整策略为最优的启发式调整策略的结论。为了验证本文所提方法的有效性,以山东兰剑物流科技有限公司为烟草行业和医药行业研发的瀑布式自动分拣系统为研究对象,基于多个地市级卷烟物流配送中心和某医药行业物流配送中心的客户真实订单数据,采用本文第二章至第五章提出的配置优化思路和算法进行计算。四个实例的计算结果均表明,本文所提出的方法在处理实际规模的通道式自动分拣系统配置优化问题时,能够在合理的计算时间内获得较为满意的结果。本文所作的研究工作是“快速分拣理论”的有益补充,能在不增加设备固定投资的前提下平衡人员成本和分拣效率,为解决多种类型分拣通道组合模式下的配置优化问题提供了一种定量且易于实践应用的方法,可以指导配送中心内通道式自动分拣系统的前期设计和后期运行,具有广泛的理论研究意义和实践应用价值。目前,本文的研究成果已经在以济南烟草物流中心为代表的32个烟草行业地市级卷烟物流配送中心中得到了推广应用,取得了良好的经济效益和社会效益。更多还原

【Abstract】 As the social economy keeps growing, the large-diversity, small-batch and high-turnover commodity picking are needed more frequently. Among the existing order picking technologies, Dispenser-based Automated Order Picking System (DAOPS), which can improve the picking accuracy and efficiency without increasing the labor intensity, is most suitable for this case and is recently adopted by many industries such as tobacco, pharmaceutical, etc.DAOPS is a kind of automated order picking system composed of multiple -volume picking dispensers. Although DAOPS can increase the picking efficiency, we should note that it can also generate a lot of infrastructure investiment, labor restocking cost and occupies a certain space. Therefore, decision makers are eager to find an optimal slotting strategy to minimize the infrastructure cost, space cost and labor cost under the throughput constraints.The slotting optimization problem of DAOPS is consist of three sub-problems, that is dispenser configuration, SKU disposition and SKU allocation. Dispenser configuration is to determine the dispenser’s optimal length and quantities. SKU disposition is to determine which SKU should be dispensed from DAOPS (SKU inclusion), which SKU should be assigned to which kind of dispenser referring to its volume (SKU assignment) and for how many dispensing channels each SKU should be allotted in its assigned dispenser type (SKU-Dispenser allocation). SKU allocation is to determine the optimal layout of each SKU. Meanwhile, number of SKUs is often large, which makes the slotting optimization problem of DAOPS much more complicated. Thus, a quantitative and effective algorithm is needed to help decision makers find the optimal slotting strategy.Existing research, which are all based on manual restocking, either foucs on one aspect of the DAOPS slotting optimization problem or solves the slotting optimization problem for only one part of DAOPS. And most of the proposed methodologies are qualitative analysis, such as EIQ-ABC analysis, which can not deal with the practical industrial-sized problem.To the best of our knowledge, there is no literature addressing the comprehensive problem. Therefore, the DAOPS slotting optimization problem is proposed in this paper. Based on Order-Analysis, Queuing Theory, Clustering Analysis, and Iterative Optimization methodologies, industrial-sized practical problem is then studied under automated restocking and manual restocking respectively.During the researching process, the main content and achievement are as follows:1. Auto-restocking-dispenser configration optimization based on order analysis. Firstly, the working principle of DAOPS-2PD-AR is annlyzed in general. Then customer order is deeply analyzed according to demand for a certain SKU in a certain order and demand for a certain SKUs in all orders. Virtural Dispenser and the "Centralize First, Split Second" two-stage method is proposed to divide the dispenser configuration problem into two sub-problems. As for the first stage, assuming that one SKU is assigned only one Virtural Dispenser, the length of which is within no limit. Based on the result of EIQ analysis, the optimal picking buffer volume of each Virtural Dispenser assigned to each SKU is determined under the case-cycling restocking condition and shuttle-rereciprocating restocking condition. As for the second stage, according to the dispenser’s real parameters, an integer programming model is developed by minimizing the sum of infrastructure cost and space cost with respect to the number of dispensers. A real life instance from a city-level tobacco distribution center shows that the proposed solution can improve the space and infrastructure utilization siginificantly.2. SKU allocation under case cycle-restocking. The main research is, as under case cycle-restocking, how to determine the least case quantity that can meet the demand of replenishment and what is the most appropriate optimal method for SKU allocation that can improve the efficiency of case cycle-restocking and reduce the case-waiting. Solving process is divided into two stages. The first stage is, assuming case is cycle-restocking without waiting, then using queuing model to determine the least case quantity that can meet the demand of replenishment. Through solving the examples, the case quantity is reduced from 42 to 25, so the utilization of case is improved adequately and the equipment investment is also reduced. The second stage is, considering the case-waiting in cycle-restocking, then using a " first clustering then ordering" method, clustering the SKU whose replenishment requests coming in the similar time, then ordering all SKUs by total order quantity, so the optimization scheme is achieved. Using simulation platform IMHS_Sim/Animation to simulate the restocking process in the two different schemes before and after optimization, and the results show that after the SKU allocation optimization, the case-waiting time in cycle-restocking is reduced efficiently, and this also improves the reference value of case quantity obtained in first stage.3. SKU disposition under manual-restocking. Based on the comprehensive analysis on restocking activities of DAOPS-2PD-MR, a method to estimate the restocking cost is proposed considering the safety stock. Based on extended fluid model, a nonlinear mathematical programming model is developed to determine the optimal volume allotted to each stock keeping unit (SKU) in a certain mode by minimize the restocking cost of that mode. Conclusion from the allocation model is specified for the storage modules of high-volume dispensers and low-volume dispensers. Optimal allocation of storage resources in the fast-picking area of CAOPS is then discussed with the aim of identifying the optimal space of each picking mode. The SKU assignment problem referring to the total restocking cost of CAOPS is analyzed and a greedy heuristic with low time complexity is developed according to the characteristics of CAOPS. Real life application from the tobacco industry is presented in order to exemplify the proposed slotting strategy and assess the effectiveness of the developed methodology. Entry-item-quantity (EIQ) based experiential solutions and proposed-model-based near-optimal solutions are compared. The comparison results show that the proposed strategy generates a savings of over 18.9% referring to the total restocking cost over one-year period.4. SKU disposition under cost and throughput considerations. Based on chapter four, SKU disposition problem for DAOPS-2PD-MR is then discussed considering the labor cost, infrastructure investment and system throughput. Firstly, SKU inclusion and system throughput are analyzed and then the interaction between them is proved to be mutual exclusion by five theorems. Secondly, a mixed interger programming model with space constraints is developed by minimizing the sum of labor cost and infrastructure investment to solve the SKU disposition problem. Finally, as for the large-scale practical problem, throughput considerations are addressed explicitly by developing analytical models for the throughput of DAOPS-2PD-MR. Based on the experience from the real-life DAOPS-2PD-MR implementation projects, four metrics including bottleneck-rate, severity, demand, and throughput are then proposed. Additionally, six heuristics for the throughput allocation adjustment model are presented and compared against optimum solutions.In order to verify the effectiveness of the proposed methods, Water-fall Automated Order Picking Systems developed by BlueSword Logistics Company for tobacco and pharmaceutical industry are employed and real customer data from these two industries are imported as the source data for our model. Computational results show that the proposed method can get the satisfactory conclusion for real-life problem within a reasonable computational time.As the beneficial supplement to the Fast-picking Theory, the strategy proposed in this paper, which can handle the multiple dispenser types, provides a practical quantitative slotting method for DAOPS and can help picking-system-designers make slotting decisions efficiently and effectively. The research results, which have been applied to 32 city-level tobacco distribution centers, have achieved good economic benefit and social benefit.更多还原