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

摘要： 架空机器人紧凑型仓储系统是一种密集型仓储系统,该系统在拥有超高存储密度的同时还保证了较高的存取速度。为解决架空机器人紧凑型仓储系统中的单轨道取货这一基本问题,以最小化翻箱次数和拣选机器人负载移动距离为目标,建立了整数规划模型,并设计了基于集束搜索的启发式算法(BSH)。数值实验表明,对于小规模算例,整数规划模型可以在合理时间得到最优解,启发式算法也可以在短时间得出近似最优解并且与整数规划模型的gap维持在1%左右;对于中到大规模算例,整数规划模型无法在合理的时间得出最优解,BSH算法可以在短时间得出优质解,与企业常用的贪心算法对比均能降低20%以上的取货成本;与传统的集束搜索算法相比,BSH算法的性能提升了7%到12%,证明了BSH算法改进的有效性;在系统配置方面,得出了随着轨道中货位数量增加,最优堆栈层数也在增加的结论,为企业的实际应用提供决策支持。

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