关键词: 可移动货架, 货架位置优化, 热度和关联度, 目标规划, 禁忌搜索

Abstract:

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.

Key words: mobile racks, rack location problem, degrees of popularity and relevance, goal programming, tabu search