【作者】 肖际伟；

【导师】 吴耀华；

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

【摘要】 我国社会物流总费用占国内生产总值的18%左右,远远高于美日等发达国家的11%,因此在我国降低物流成本具有巨大的效益和潜力。当前多品种小批量的市场特征,使通过配送中心周转货物成为降低运输、库存、分拣和配送成本的一项重要措施。在配送中心中,拣货成本占总成本的60%以上,拣货时间占作业总时间的35%左右。储位分配问题(Storage Location Assignment Problem, SLAP)是影响储存区拣货作业效率的一项重要因素,复合式自动分拣系统(Complex Automated Sorting System, CASS)因具有分拣速度快、准确率高、工人劳动强度低、性价比高等优点,使其在拣货区的拣货作业中逐步得到广泛应用。因此将拣货系统中的储位分配问题和复合式自动分拣系统的优化配置问题作为研究对象,对于提高配送中心作业效率、服务水平、降低物流成本具有重要意义。目前对储位分配问题的多数研究和应用都是以货物的存取频率(Turnover Frequency, TF)或单次取货存储空间指标(Cube-per-Order Index, COI)等平均存储特征作为储位分配的依据,没有考虑每个装载单元的储存时间特征。基于装载单元储存时间(Duration of Stay, DOS)的储位分配方法以每个装载单元的储存时间为依据进行储位分配,在理论上能够实现最优的储位分配方案,而现有方法要么为静态方法,很难应用到生产实际中；要么为基于分类存储策略的方法,没有充分利用装载单元的储存时间特性。本文对基于DOS的储位分配优化模型和启发式方法进行研究,以解决上述问题为目标提出基于DOS的动态储位分配方法,为进一步研究储位分配问题和配送中心改进拣货作业效率提供了新的方向和方法。单CASS的综合性能依赖于分拣机的组合。当前采用EIQ分析和ABC分类确定分拣机组合的方法,没有精确地把握分拣机组合和系统性能及成本之间的关系。本文运用数学分析方法研究CASS,通过建立并求解分拣机组合优化模型,为确定CASS的分拣机组合提供了定量方法。对于多CASS联合作业的系统配置和任务调度问题,目前尚无有效的规划设计方法。本文以对单CASS的研究为基础,建立了系统配置和任务调度优化模型,为规划和研究多CASS联合作业的分拣系统提供了新方法和基础。本文的主要工作及创新点如下：(1)对基于DOS的储位分配最优化数学模型和静态贪婪式储位分配方法进行分析和总结,结合储位分配问题的实际应用特点,给出基于DOS的动态储位分配方法,并对具体的实现步骤和所涉及到的货物参数、储位行走时间、实际DOS列表和虚拟DOS列表的确定及计算进行设计。首先计算和入库装载单元在储存时间上有重叠的装载单元,得出参与储位分配的装载单元序列,然后根据每个装载单元的存入和取出时间分配储位。该方法符合实际应用中存取任务随时间推移逐步产生的特点,计算时间复杂度较低,能够很容易地应用到实际生产中。(2)设计开发了基于DOS的动态存储、就近存储、分类存储和定位存储储位分配方法的仿真程序。程序为客户端／服务器结构,在服务器端用数据库保存仿真数据,用存储过程实现储位分配算法和任务的维护。在客户端采用面向对象设计方法,实现仿真过程的计算和图形显示。仿真程序的层次结构清晰,具有良好的可维护性和开放性。仿真动画直观、形象,能够真实地表现仓库的作业过程。基于货物需求ABC现象和经济订货批量模型的仿真方案设计,使仿真方案具有很好的代表性。仿真结果表明基于DOS的动态储位分配方法和就近存储、分类存储及定位存储储位分配方法相比,平均单程行走时间分别减少8.32%、9.29%和12.24%,总体上平均减少9.95%,并且到货入库次序的改变对平均单程行走时间影响很小,这充分验证了基于DOS的动态储位分配方法的有效性。(3)针对单CASS的分拣机组合优化问题,分析了分拣用时、分拣成本和分拣机组合的关系,以单位分拣成本最小化为目标,建立了分拣机组合优化模型。并依据设备特点推导出固定成本、最小可变成本和最小分拣用时的计算公式,从而简化了模型的求解。研究表明随着分拣系统中卧式分拣机数量的增加,单位时间上的设备成本、场地成本呈线性增加,固定配备人员成本不变,补货人员成本和分拣用时逐步减小,单位分拣成本呈出先降后升的特点。该方法避免了EIQ分析和ABC分类方法的主观性,明确了分拣机数量和各项成本之间的关系,可有效地用于指导CASS分拣机组合的选择。(4)针对多CASS联合作业的系统配置和任务调度问题,以单CASS的固定成本、最小补货成本和最小分拣用时的计算公式为基础,建立以分拣成本最小化为目标的优化模型,设计了搜索最优解的回溯法。根据问题特点,合理地设计了算法的分枝结构和定界函数,有效地缩小了解空间,降低了计算复杂度,缩短了求解时间。并利用设计开发的回溯法求解程序对应用实例进行了求解。实例结果表明分拣成本主要由固定成本决定,可变成本的影响较小,固定成本主要取决于分拣系统的套数。因此,在分拣系统规划中,可通过采用增加卧式分拣机数量,减少分拣系统套数的简化做法降低分拣成本。更多还原

【Abstract】 The total cost of social logistics in China is approximate 18% of GDP, significantly higher than the costs of the United States, Japan and other developed countries, which are estimated to be about 11%. So reducing logistics cost is of great benefit and potential. The current market characteristics of multi-items and small-quantities make turning over goods through the distribution center an important measure to reduce the costs of transport, storage, sorting and distribution. In the distribution center, the picking costs account for 60% of the total cost while the picking time occupies 35% of the total operation time. Storage Location Assignment Problem (SLAP) is a key factor that affects the efficiency of picking operation in reserve area and Complex Automated Sorting System (CASS) has been widely used for the picking operation in picking area. Therefore, research on SLAP and CASS is of great importance in increasing the working efficiency, improving service level and reducing logistics costs.Existing storage location assignment methods are mainly based on average storage features such as Turnover Frequency (TF) or Cube-per-Order Index (COI),regardless of the storage time of each load unit. Duration of Stay (DOS) based storage location strategy can come up with optimal solution. However, there is little research on it. This paper concentrates on mathematical model and heuristic algorithm of storage location assignment and provides a solid foundation for future study on storage location assignment problem and improvement of picking efficiency.The overall performance of single CASS depends on the combination of dispensers. Current combination methodology, which is based on EIQ analysis and ABC classification, does not take into account system performance and cost. Therefore, a new quantitative method of determining the optimal combination of dispensers is proposed in this paper. Combinatorial optimization model is established and then solved. Since there is no effective design and planning method for system configuration and task scheduling of multi-CASS-task problem currently, this paper establishes a corresponding optimization model based on th study of single CASS for multi-CASS picking system. And this provides new method as well as foundation for the research on multi-CASS picking system.Major work and innovation of this paper are as follows:(1) DOS-based storage location assignment optimization model and static greedy storage location assignment method are analyzed and summarized. According to the practical applications in storage location assignment problem, this paper comes up with a DOS-based dynamic storage location assignment method and presents concrete implementation steps as well as determination of the involved items parameters, storage travel time, actual and virtual DOS list. In the proposed method, load units that have overlaps in storage time with inbound load units are first forecasted and load units sequence, involved in the storage assignment, is obtained; then storage location is allocated based on the storage and rerieval time of each load unit. This approach is consistent with characteristics generated with access task in the practical application and can be easily applied to practice because of the low complexity in calculating the time.(2) To verify whether the DOS-based dynamic storage location assignment method is effective, a simulation program for the storage location assignment problem is developed based on dynamic storage location assignment, nearest open location, class-based assignment and dedicated assignment. The program uses Client/Serve (C/S) architecture. The server-side uses database to save the simulation data and several store procedures to realize the storage assignment algorithm and task maintenance; the client-side uses object-oriented design method to realize the simulation calculation and graphical display. The simulation program, the hierarchical structure of which is very clear, has good maintainability and openness. Simulation animation, which is intuitionistic and visual, is a representation of real warehouse operation process. Design of the simulation plan, which is based on the ABC phenomenon and the economic order quantity model, makes the simulation program representative and the simulation result persuasive strongly. Simulation results show that compared with the nearest open location, class-based assignment and dedicated assignment, in the DOS-based dynamic storage assignment method, the average one-way travel time is reduced by 8.32%,9.29% and 12.24% separately and the overall average is reduced by 9.95%. At the same time, the change of arrival sequence has little effects on the average one-way travel time, which fully demonstrates the effectiveness of the DOS-based dynamic storage assignment method.(3) Aiming at solving the problem of combinatorial optimization for dispensers, this paper analyzes the relationship of the sorting time, the sorting cost and dispensers’combination. An optimization model is developed to minimize the sorting unit cost. Moreover, the formulas of fixed cost, mini-variable cost and mini-soring time are deduced from the device characteristics, which simplifies the solution of the model. The results show that as the horizontal dispensers’quantity in the sorting system increases, the equipment cost and space cost per unit of time increase linearly, fixed staffing cost remain constant, personnel cost and sorting time gradually reduce with time, the increased or decreased degree is related with the number of associated horizontal dispensers. The sorting unit cost decreases at the first and then increases. The lowest point, which corresponds to the number and cost of horizontal dispensers, is the optimal combination of dispensers and smallest unit of sorting cost. This method avoids the subjectivity of the EIQ analysis and ABC classification and can be used to guide the choice of CASS dispensers combination effectively.(4) In order to solve the multi-CASS system configuration and task-scheduling problem, this paper establishes an optimization model by minimizing the total sorting cost and proposes a backtracking algorithm based on the single fixed cost of CASS, the mini-variable cost and mini-sorting time formulas. According to the characteristics of the problem, this paper rationally designs the branch structure and bound function, effectively narrows the space of understanding and reduces the computational complexity and computation time. An application example shows that the total cost mainly depends on the total fixed cost and less depends on the total variable cost. Total fixed cost mainly depends on the sets number of the sorting system. Therefore, by increasing the number of horizontal dispensers and reducing the sets number of the sorting systems, the total sorting cost can be reduced in the sorting system planning.更多还原