Abstract: In the era of “Industry 4.0”, robot technology has become an important method to assist the transformation and upgrading of labor-intensive industries. For the past years, the ministry of industry and information technology has pointed out that, it is necessary to build intelligent logistics systems with a focus on robots and improve the digital level of commercial logistics. Robotic mobile fulfillment system (RMFS) is a new type of “goods to picker” sorting system based on robot technology. Due to its high flexibility, high storage density, high efficiency, and high responsiveness, RMFS is widely used in industries such as e-commerce, retail supermarkets, pharmaceuticals, and has become a research hotspot for scholars. Task allocation is a key decision-making problem that affects the efficiency of RMFS. The task allocation problem of RMFS is to decompose a batch of orders into a set of transportation tasks and then allocate them to a group of robots according to certain rules. At present, the researches on the task allocation problem of RMFS mainly focus on innovation in model transformation and algorithm optimization, ignoring the gap between the model itself and the actual system. These issues include: 1)For business scenarios with differentiated customer rating characteristics, there are differences in timeliness and importance between customer orders, and distribution centers need to prioritize orders with high customer ratings. Therefore, it is necessary to introduce customer order priority constraints into mathematical models. 2)The acceleration, deceleration, turning, lifting shelves, queuing and waiting of robots during task execution can bring significant time cost which dynamically changes with different task allocation methods. Existing literatures often use Manhattan distance or Euclidean distance when calculating make span, without considering the impact of dynamic task cost, resulting in significant deviation from reality. 3)In the actual operation process, the seeding wall capacity in the picking station is limited, and it is one of the key parameters that restrict the efficiency of the picking station. However, most studies ignore the seeding wall capacity when modeling.
Based on the above issues, this article investigates the task allocation problem of RMFS that considers dynamic task cost and limited seeding wall capacity. A centralized task allocation method based on a hybrid heuristic algorithm for business scenarios with differentiated customer rating characteristics is proposed.First of all, a task allocation optimization model with the goal of minimizing the maximum make span is established under the constraint of customer order priority. Secondly, considering the dynamic task cost caused by acceleration, deceleration, turning, lifting shelves, queuing and waiting of robots during the task execution and the constraint of the seeding wall capacity, the maximum make span generation scheme is designed. The generation scheme dynamically corrects the cost of sub tasks under the given task allocation method, and determines whether the task allocation method meets the constraint of the seeding wall capacity.Then, the memory elite population based catastrophe adaptive large neighborhood search algorithm (MEPCALNS) is proposed to solve the optimization model, which improves the search depth and efficiency of the traditional adaptive large neighborhood search algorithm (ALNS). On the basis of ALNS, MEPCALNS dynamically maintains a search population based on catastrophe operator and an elite population with memory. The search population uses ALNS for neighborhood search, and actively abandons continuously unimproved solutions through catastrophe operators to prevent falling into local optima. The elite population adopts a probability-based update mechanism to preserve the high-quality solutions generated by the search population, compensating for the memoryless nature of the ALNS search process. By using catastrophe strategies, these high-quality solutions can re-enter the search population and search in new directions, which improves the search depth of ALNS.Finally, numerical experiments are conducted to demonstrate the effectiveness and stability of the algorithm.
MEPCALNS is compared with dispatch rules method and ALNS, and each heuristic algorithm is independently run 10 times to obtain the best result. The experimental results show that ALNS and MEPCALNS outperform dispatch rules method in all cases. Therefore, the dispatch rules method is used as a benchmark to discuss the optimization capabilities of the two algorithms. For all cases, the optimization performance of MEPCALNS is superior to ALNS with an average increase of 3.3%. Among them, the improvement effect is most significant at RAND3-3, with an increase of 5.27%. Also, the experimental comparative analysis has demonstrated that the characteristics of dynamic task cost and the constraints of seeding wall capacity are essential for task allocation problems.
This article does not consider conflicts and deadlocks between robots when designing the maximum make span generation scheme. In practice, conflicts and deadlocks may occur when the number of robots exceeds a certain value leading to an increase in task cost, resulting in a deviation between problem modeling and the actual situation. Therefore, incorporating conflicts and deadlocks into the maximum make span generation scheme to make the model more practical is the focus of future research.

Key words: robotic mobile fulfillment system, task allocation, dynamic task cost, adaptive large neighborhood search, catastrophe operator

摘要： 任务分配是影响移动机器人拣货系统效率的关键决策问题。针对具有差异化客户评级特征的业务场景,考虑系统的动态任务耗时特性和拣选站播种墙容量约束,提出了一种基于混合启发式算法的集中式任务分配方法。首先,在客户订单优先级约束下构建以最大完工时间最小为目标的任务分配优化模型。其次,考虑机器人在任务执行中因加减速、转弯、升降货架、排队等待导致的动态任务耗时以及播种墙容量限制,设计最大完工时间生成方案。随后,开发基于记忆精英种群的灾变自适应大邻域搜索算法(MEPCALNS)对模型进行求解,提高了传统自适应大邻域搜索算法的搜索深度和搜索效率。最后,通过数值实验证明了算法的有效性和稳定性。研究成果有利于提高移动机器人拣货系统的分拣效率。

关键词: 移动机器人拣货系统, 任务分配, 动态任务耗时, 自适应大邻域搜索, 灾变算子