可移动货架仓储系统中的货架位置优化方法

Method of Locating Racks in Mobile-Rack Warehousing System

可移动货架仓储系统极大增强了商品储位的灵活性,有利于显著提高具有“一单多品”特征的电商订单的拣选效率。然而,也正是由于货架的可移动性,货架的位置如何摆放才能有效地应对电商订单拣选的挑战,又成为电商仓库决策者亟待解决、制约该类仓储系统优势发挥的新的难题。由于该类仓储系统中每个货架存储着不同种类和数量的商品,如何根据顾客对商品的订购规律,以最大化订单拣货效率为目标,实现每个货架在仓库中的合理定位,是解决这一难题的关键。为此,基于顾客订单建立了货架热度和关联度生成模型,并以这两个属性为基础,建立了考虑机器人重载和空载行驶距离最小化的双目标整数规划模型,设计了禁忌搜索启发式求解算法。分别利用不同规模的算例对模型和算法的科学性与有效性进行了验证,并通过敏感性分析,为该类仓库的决策者提供了管理启示。

The increasing e-commerce customer orders bring great challenges to the operation efficiency of warehouses.To handle the customer orders each of which usually has multiple small-sized items,a kind of storage system with mobile racks is gradually booming.In this kind of warehouses,racks can be moved anywhere and a fleet of robots are employed to carry racks to picking stations,where human workers pick items from racks for customer orders.After the items are picked,robots will carry racks back to its location and go to carry other racks until all customer orders are picked.In the picking process,the time spent by robots in moving the rack placed in different positions is very important for the picking efficiency.And the moving time depends on the locations of racks.If a rack that is frequently used is located far away from the picking station,much time would be spent by robots carrying it to picking station,and the picking efficiency would be obviously low.If a rack is often carried after another to the picking station,they should be located close to each other;otherwise,robots have to travel a long way between them.Therefore,the rack location scheme directly affects the traveling time,as well as the picking efficiency.In order to reduce the traveling time of robots as much as possible,this paper studies the location problem of mobile racks.The problem is different from the storage location problem in a traditional warehouse with fixed racks.The traditional storage location problem studies the locations of goods in racks.While the problem of this paper is focused on the locations of racks in a warehouse and each rack has been loaded with a set of items.The problem is difficult because the using frequency of racks and the relationship of racks are closely related to the pattern that customers ordered items.How to reveal the using frequency and the relationship of racks remains a basic and key problem for locating racks.Racks cannot be well located if historical customer orders are not well studied.To handle the rack location problem,customer orders are analyzed and an integer-programming model(Model 1)to generate the using frequency(popularity degree)and the relationship(relevance degree)of racks is constructed.Based on the degrees of rack popularity and relationship,a bi-objective integer-programming model(Model 2)that successively minimizes the traveling distances of heavy-loaded robots and non-loaded robots is built.The two objectives of this model can be solved one after another by using an integer-programming solver.Due to the NP-hardness of Model 2 with the second objective,a tabu search heuristic is developed to handle the real-world large-sized problems.To solve the rack location problem,a three-stage algorithm is proposed.In the first stage,the algorithm obtains the degrees of rack popularity and relationship by solving Model 1 using a solver for integer-programming models;and in the second and third,it solves Model 2 with the first and the second objectives using the solver and the tabu search heuristic respectively.The proposed algorithm is then implemented and tested using real-world customer orders.It is first compared to an integer-programming solver(Gurobi)which is used to solve all the models on small-sized instances.The experimental results show that,for the small-sized cases,our algorithm can almost find all the optimal solutions,and at the same time spends much less time than Gurobi.Then,an algorithm is compared to a representative algorithm in the literature,the partheno-genetic algorithm which is used to handle Model 2 with the second model,on large-sized instances.Results show that our algorithm outperforms the genetic algorithm in both solution quality and running time.Finally,a sensitivity analysis on the number of item types in the rack is made.It is found from the analysis that the racks with more item types are generally nearer to the picking station than those with less item types.This founding is also affected by various factors,e.g.customer order structure and the combination of item types in racks.The finding provides managerial insights for decision makers of such warehouses.