优化配送中心订单拣取路径的一种动态规划方法

订单拣取过程是配送中心最耗时耗力的作业环节，因此提高拣货作业效率成了大多数配送中心努力的方向。而优化拣货路径则是提高拣货作业效率的有效措施之一，所以本在传统拣货规则的基础上，提出了一种采用动态规划方法优化订单拣取路径的方法。该方法是优化配送中心订单掠取路径的一种新的思路和方法，且其确定的拣货路径是在既定规则下的最优拣货路径。针对不同的拣货单采用不同的拣货路径，能有效缩短拣货行走的距离，对提高配送中心的拣货效率具有现实意义。     

带时间窗的多配送中心协同配送问题研究

研究了多个配送中心协同配送下的车辆路径问题,建立运力和时间窗约束下的运输成本和时间惩罚成本之和最小化模型.考虑多配送中心路径优化问题的复杂性,提出了基于预分割和再调整的两阶段优化策略,采用罚数分配法分割需求点集合,将问题分解成多个单配送中心路径问题,启发式构建初始解,设计禁忌搜索算法求解.在调整阶段,将各集合中未分配的需求点重新分割,变邻域禁忌搜索再次优化路径.最后给出算例分析,验证了模型的合理性和改进算法的有效性.     

考虑订单合并和货物转运的多式联运路径优化研究

为了获得运输的规模经济效应,本文研究了一种考虑订单合并和货物转运的零担多式联运路径优化问题。首先,以总运输成本为目标函数,以网络中的运输工具容量、可以提供的运输工具最大数量、运输工具服务的关闭时间以及订单时间窗为约束,构建混合整数规划模型,在模型中允许多个订单进行合并运输并考虑运输过程中的转运成本。其次,由于多式联运路径优化问题是典型的NP-hard问题,为了快速求解该模型,开发了一种可以快速为该问题提供近似最优解和下界的列生成启发式算法。最后,生成并测试了大量算例,结果表明所开发的列生成启发式算法可以在较短的时间内提供高质量的近似最优解。文章所构建的模型和开发的列生成启发式算法可以为零担自营多式联运物流企业提供高效的决策支持。     

考虑车载容量的多区型仓库拣货路径优化研究

拣货作业是仓库核心作业之一,占据仓库运营大量的时间成本和资金成本.针对多区型仓库拣货路径优化问题,对多区型仓库布局、货位坐标、路径等问题进行了定义,构建了多区型仓库拣货路径优化建模,接着通过大量实验确定了人工鱼群算法在求解拣货路径问题时的最优算法参数组合,通过演示性实验验证了模型与算法的有效性,最后从波次订单对实验结果的影响、车载容量对实验结果的影响和算法对比分析3个方面验证了人工鱼群算法的实用性和优越性.结果表明,所建立的多区型仓库拣货路径优化的模型及其求解方法,能够有效提高仓储拣货作业效率.     

带批次和临时库存的越库配送车辆路径问题研究

从零售业供应链整合入手,构建供应商、配送中心和零售点构成的协同配送网络,研究带批次和临时库存的越库配送车辆路径问题.将越库过程分为取货、分拣和配货三个阶段,考虑配送中心分拣能力,分批次设置车辆协同到达配送中心的服务时刻,据此建立以最小化车辆运输成本、临时库存成本和固定成本为目标的数学模型.考虑问题特征,设计一种混合变邻域搜索粒子群算法求解,并将结果进行横纵向比较.结果表明,所提算法有效且可靠,能够为带批次和临时库存的越库配送问题提供解决方案.     

基于两阶段启发式算法的物流配送选址-路径问题研究

为了解决配送中心选址与带时间窗的多中心车辆路径优化组合决策问题,利用双层规划法建立了配送中心选址与车辆路径安排的多目标整数规划模型,针对该模型的特点,采用两阶段启发式算法进行了求解。首先,通过基于聚集度的启发式算法对客户进行分类,确定了备选配送中心的服务范围;然后,基于双层规划法,以配送中心选址成本最小作为上层规划目标,以车辆配送成本最小作为下层规划目标,建立了多目标整数规划模型;最后,利用改进的蚁群算法进行了求解。通过分析实例数据和Barreto Benchmark算例的实验结果,验证了该模型的有效性和可行性。     

基于情景分析的应急两级车辆路径问题研究

为研究应急配送过程中次生灾害情景下的车辆路径问题,考虑当地配送中心最后完成救援物资配送任务的时间期望最小化为目标,构建了最小最大两级车辆路径随机规划模型.针对面临的塌方道路抢通时间是随机变量的情况,提出了解决该随机规划的三阶段决策方法:首先建立受灾区域配送点组合情景与随机抢通时间组合情景的关系模型,提出了路径计划策略;其次,提出了针对最小最大两级车辆路径问题的启发式算法;最后,确定每种情景发生的概率,得到最后当地配送中心最后完成救援物资配送任务的时间期望最小化的近似最优解.实验算例验证了该方法的可行性.     

基于偏离度的仓储中心拣货路径优化方法研究

针对现代仓储作业中广泛使用的双区仓库,为提高拣选作业的质量和效率,首先应用RFID技术对仓储作业中货物的入库、定位、拣选、出库等进行自动化识别,实现管理数据库的实时更新,减少订单中货物搜索时间.在此基础上,提出了一种基于偏离度的路径优化方法,通过与传统穿越策略、S型启发式算法进行仿真对比.结果表明,在双区仓库的路径拣选中,基于偏离度方法对仓库作业优化效果显著.     

装备维修器材生产路径双目标问题优化决策方法研究

在装备维修器材供应保障中,针对精确保障背景下部队用户对器材保障精度的要求,构建了最小化总成本和最大化订单精准执行率的双目标优化决策模型。在ε-约束法框架内,开发可生成近似Pareto前沿的两阶迭代启发式算法,并采用模糊逻辑决策法选择符合决策者偏好的折中最优解。随机实例测试结果表明所提出的模型和算法可以很好地应用在双目标优化问题的研究中,并在求解不同规模实例时表现出优异的性能。     

基于组合赋权TOPSIS模型的物流配送中心选址研究

物流的发展离不开配送中心的建设,配送中心建设的首要问题是选址,通过分析影响物流配送中心选址的各种因素,建立了包括自然条件、经营环境、基础设施、成本因素等因素的配送中心选址指标体系.采用层次分析法(AHP)和熵值法组合确定各指标的权重,依据逼近理想解排序(TOPSIS)法的基本思路,建立物流配送中心选址模型.通过对物流配送中心进行选址的实例研究,证明方法的有效性并选出最优方案.     

The impact of order batching and picking area zoning on order picking system performance

This paper proposes an approximation model based on queuing network theory to analyze the impact of order batching and picking area zoning on the mean order throughput time in a pick-and-pass order picking system. The model includes the sorting process needed to sort the batch again by order. Service times at pick zones are assumed to follow general distributions. The first and second moments of service times at zones and the visiting probability of a batch of orders to a pick zone are derived. Based on this information, the mean throughput time of an arbitrary order in the order picking system is obtained. Results from a real application and simulation show that this approximation model provides acceptable accuracy for practical purposes. Furthermore, the proposed method is simple and fast and can be easily applied in the design and selection process of order picking systems.     

Design and control of warehouse order picking: A literature review

Order picking has long been identified as the most labour-intensive and costly activity for almost every warehouse; the cost of order picking is estimated to be as much as 55% of the total warehouse operating expense. Any underperformance in order picking can lead to unsatisfactory service and high operational cost for the warehouse, and consequently for the whole supply chain. In order to operate efficiently, the order-picking process needs to be robustly designed and optimally controlled. This paper gives a literature overview on typical decision problems in design and control of manual order-picking processes. We focus on optimal (internal) layout design, storage assignment methods, routing methods, order batching and zoning. The research in this area has grown rapidly recently. Still, combinations of the above areas have hardly been explored. Order-picking system developments in practice lead to promising new research directions.     

Optimizing a dynamic order-picking process

This research studies the problem of batching orders in a dynamic, finite-horizon environment to minimize order tardiness and overtime costs of the pickers. The problem introduces the following trade-off: at every period, the picker has to decide whether to go on a tour and pick the accumulated orders, or to wait for more orders to arrive. By waiting, the picker risks higher tardiness of existing orders on the account of lower tardiness of future orders. We use a Markov decision process (MDP) based approach to set an optimal decision making policy. In order to evaluate the potential improvement of the proposed approach in practice, we compare the optimal policy with two naïve heuristics: (1) “Go on tour immediately after an order arrives”, and, (2) “Wait as long as the current orders can be picked and supplied on time”. The optimal policy shows a considerable improvement over the naïve heuristics, in the range of 7–99%, where the specific values depend on the picking process parameters. We have found that one measure, the slack percentage of the picking process, associated with the difference between the promised lead time and the single item picking time, predicts quite accurately the cost reduction generated by the optimal policy. Since relatively small-scale problems could be solved by the optimal algorithm, a heuristic was developed, based on the structure and properties of the optimal solutions. Numerical results show that the proposed heuristic, MDP-H, outperforms the naïve heuristics in all experiments. As compared to the optimal solution, MDP-H provides close to optimal results for a slack of up to 40%.     

考虑商品数量和商品拣选成本的AGV智能仓库订单分批问题研究

AGV(Automated Guided Vehicle,自动导引车)智能仓库是一种基于“货到人”拣选模式的自动化仓库。本文考虑了订单中商品的需求量和货架上商品的存储量,以极小化货架搬运成本和商品拣选成本为目标,建立了AGV智能仓库订单分批问题的整数规划模型。本文针对订单分批问题的特点,提出了一种基于订单和货架交替选择的贪婪求解算法。对比CPLEX求解器的精确最优解,本文提出的贪婪算法的误差百分比不超过10%,平均误差百分比为5.38%;对比基于相似性的分批算法的求解结果,本文提出的贪婪算法不仅运算时间更短,解的质量也更好。进一步地,对比不考虑商品拣选成本的订单分批模型,本文提出的模型在不明显增加货架搬运成本的前提下,可以大幅度降低商品拣选成本。因此,在订单分批模型中考虑商品拣选成本是非常必要的。     

基于AGV的智能仓库系统订单分批问题研究

研究了基于自动引导小车(AGV)的“货到人”智能仓库订单分批拣选问题, 在同时考虑工作人员拣选商品成本和AGV搬运货架成本的前提下, 建立了以总成本极小化为目标函数的订单分批问题整数规划模型。根据订单中包含的商品信息和商品所在的货架信息构建了描述订单之间关系的加权相似度指标, 分析了加权相似度与总拣选成本之间的正相关关系。基于订单之间的加权相似度设计了求解模型的贪婪算法。利用具体算例进行模拟计算, 分析了加权系数的变化对订单分批结果的影响, 以及加权系数λ的取值与工作人员拣取一件商品的成本c₁和AGV搬运一次货架的成本c₂之间的关系, 得到了贪婪算法中加权系数λ的确定方法。进一步分析了贪婪算法的计算时间和计算效果, 结果显示, 通过适当选取加权系数, 利用贪婪算法可以在短时间内得到订单分批问题的近似最优解;对于小规模算例, 贪婪算法在最坏情况下近似比不超过1.35。利用本文的模型和算法进行订单分批, 兼顾了工作人员拣取商品的成本和AGV搬运货架的成本, 可以有效提高订单拣选效率, 降低订单拣选总成本。     

Travel time estimation and order batching in a 2-block warehouse

Order batching problem (OBP) is the problem of determining the number of orders to be picked together in one picking tour. Although various objectives may arise in practice, minimizing the average throughput time of a random order is a common concern. In this paper, we consider the OBP for a 2-block rectangular warehouse with the assumptions that orders arrive according to a Poisson process and the method used for routing the order-pickers is the well-known S-shape heuristic. We first elaborate on the first and second moment of the order-picker’s travel time. Then we use these moments to estimate the average throughput time of a random order. This enables us to estimate the optimal picking batch size. Results from simulation show that the method provides a high accuracy level. Furthermore, the method is rather simple and can be easily applied in practice.     

A branch and bound algorithm for class based storage location assignment

Class-based storage implementation decisions have significant impact on the required storage space and the material handling cost in a warehouse. In this paper, a nonlinear integer programming model is proposed to capture the above. Effects of storage area reduction on order picking and storage space cost are incorporated. A branch and bound algorithm is developed to solve the model. Computational experience with randomly generated data sets and an industrial case shows that branch and bound algorithm is computationally more efficient than a baseline dynamic programming algorithm. It is further observed that the class based policy results in lower total cost of order picking and storage space than the dedicated policy.     

Batch picking in narrow-aisle order picking systems with consideration for picker blocking

This paper develops strategies to control picker blocking that challenge the traditional assumptions regarding the tradeoffs between wide- and narrow-aisle order picking systems. We propose an integrated batching and sequencing procedure called the indexed batching model (IBM), with the objective of minimizing the total retrieval time (the sum of travel time, pick time and congestion delays). The IBM differs from traditional batching formulations by assigning orders to indexed batches, whereby each batch corresponds to a position in the batch release sequence. We develop a mixed integer programming solution for exact control, and demonstrate a simulated annealing procedure to solve large practical problems. Our results indicate that the proposed approach achieves a 5–15% reduction in the total retrieval time primarily by reducing picker blocking. We conclude that the IBM is particularly effective in narrow-aisle picking systems.     

基于聚类和动态规划的组合路径策略

为提高电商仓库的拣货作业效率,本文提出了基于聚类和动态规划的组合路径策略,实现了生成路径消耗时间和路径长度之间的平衡,并将这一策略成功地应用到多区型仓库。该策略分四步:首先,根据待拣储位分布特征,运用聚类分析法对其进行分类;然后,以各类的首末储位作为节点,运用动态规划法对已得分类进行排序,得到相应的类序;其次,得到各类内部路径;最后,依次拣取待拣商品,并返回出发点完成拣货作业。在提出新的路径策略后,通过仿真方法将新策略与三种传统路径策略(穿越策略、最大间隙策略和混合策略)和一种优质算法(蚁群算法)进行了对比分析,结果表明:该策略具备良好的适用性和实用性。     

基于遗传算法的多通道密集式移动货架订单拣选研究

密集式移动货架越来越多地应用到仓储实践中,提高了仓储空间利用率,但增加了订单拣选的时间成本。本文根据密集式移动货架的仓储布局特点,针对多条通道可同时打开的情况,将货架移动时间转换成通道移动距离进行计算,提出了多条通道依次移动的优化规则,以整批订单拣选所耗费的总时间最少为目标,建立了订单拣选顺序优化的数学模型。针对该模型的特点,设计了实数编码且全局寻优的遗传算法,并进行了不同规模的算例模拟。计算结果表明,该算法具有较强的适用性,针对不同规模的问题,均有显著的优化效果;货架数量、订单数量以及移动通道数量的小幅度增减,将会导致总拣选时间较大幅度的波动;多条移动通道初始位置居于中部或均匀分散,总拣选时间略优于其集中于仓储系统一端。