关键词: 调度, 紧致化仓储系统, ORCSRS, 整数规划模型, 启发式算法

Abstract: A compact warehousing system holds substantial significance for enterprises and it is also an important field for the development of intelligent warehousing in China. Overhead Robotic Compact Storage and Retrieval System (ORCSRS) has emerged as a new type of high-density automated warehouse. Theoretically, the ORCSRS can maximally meet the personalized and timely needs of consumers for products and services due to land resource scarcity. Currently, there is a research void on the retrieval scheduling problem for this warehousing system. So, this article fills in the gap in this field. Because the system is composed of multipleindependent picking tracks, the single-track pickup problem is its basic problem, and the problem of single-track pickup is the foundation for solving the pickup problem of the system. Therefore, this article studies the single-track pickup scheduling problem of the system.
The ORCSRS single track-pickup problem is similar to the block relocation problem and can be regarded as a variant of the block relocation problem. However, it differs from existing block relocation problems in the following aspects: (1)Different constraint conditions: existing block relocation problems generally have strict pickup orders and complete retrieval, while this study does not have a pickup order and incomplete retrieval. (2)The optimization objectives are different. Due to the small system size of block relocation problem, the time spent on the crane’s movement can be ignored, and the number of relocations is a key factor affecting the pickup time. However, due to the large scale of the system and the large number of stacks, the moving distance of the picking robot during each relocation becomes an undeniable influencing factor. This work focuses on the objective of minimizing pickup time. The picking time is related to two factors: the number of relocations and the distance traveled by the picking robot. So, the optimization objective of this work is to minimize the sum of the number of relocations and the load moving distance of the picking robots. Firstly, we establish an integer programming model for this problem, which can only solve small-scale problems. Then, we design a heuristic algorithm based on beam search (abbr BSH) for large-scale problems. The algorithm makes some improvements on the branching operations of the first step and preserves some of each layer’s sub nodes based on beam search to enhance algorithm performance. Finally, we use Python to call Gurobi to solve integer programming model. Then, the BSH is compared with the integer programming model as well as the greedy algorithm commonly used in enterprises to validate the effectiveness of the algorithm. The BSH is compared with traditional beam search algorithms to validate the effectiveness of the improved algorithm.
All numerical experiments are coded by Python. The extensive experiments show that the integer programming model can solve a small-scale problem with 5 stacks and 4 levels within 1000 seconds, the gap between the BSH algorithm and the integer programming model solution is within 1%, and the solving time of BSH is significantly faster than that of the integer programming model. For medium and large-scale problems, the model cannot find the optimal solution within a reasonable amount of time. The BSH algorithm can solve an instance with 50 stacks and 8 levels in a few tens of seconds and its performance is about 20% better than that of the greedy algorithm commonly used in enterprises. Compared with traditional bundle search algorithms, the performance of BSH algorithm has been improved by 7% to 12%; in terms of system configuration, it has been concluded that as the number of storage spaces increases, the optimal number of stack layers also increases, providing decision support for enterprise applications.
In the future, the research can be conducted in the following areas: (1)This article only studies the single-track pickup problem and can focus on the multi-track pickup problem of this system. (2)This article only investigates the pickup problem of only one robot per track, so we can study the pickup problem of multiple robots.

Key words: scheduling, compact storage and retrieval system, ORCSRS, integer programming model, heuristic algorithm