移动货架系统多机器人“存-取货架”调度优化方法  

Multi-robot scheduling problem of robotic mobile fulfillment systems:An adaptive matheuristic

作　　者：庄燕玲 孙玉姣 朱涛[1] 胡祥培[1] ZHUANG Yanling;SUN Yujiao;ZHU Tao;HU Xiangpei(School of Economics and Management,Dalian University of Technology,Dalian 116024,China;School of Business Administration,South China University of Technology,Guangzhou 510641,China)

机构地区：[1]大连理工大学经济管理学院,大连116024 [2]华南理工大学工商管理学院,广州510641

出　　处：《系统工程理论与实践》2023年第2期488-508,共21页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(重点项目(71931009),重点国际(地区)合作研究项目(72010107002));广东省基础与应用基础研究基金(2021A1515110635)。

摘　　要：近年来,机器人移动货架系统已成为我国智慧物流与智能仓储的重要发展方向,多机器人“存-取货架”调度优化问题是影响该系统运行效率的挑战性难题.本文以减少机器人总行驶距离为目标,对机器人“存货架”和“取货架”进行联合决策,构建了多机器人“存-取货架”调度优化模型.针对该问题具有决策耦合性、解空间巨大的难点,设计了限定宽度的动态规划算法获取初始解,并将所构建的整数规划模型嵌入自适应大邻域搜索启发式框架中,通过两种分解算子将原模型转化为较小规模的子模型,提出自适应数学规划启发式算法,能够快速生成近似最优的调度方案.数值实验表明,与分别优化“存货架”和“取货架”调度相比,本文的联合调度优化方法能够减少约60%的机器人总行驶距离;与实践中普遍应用且性能表现最好的就近指派规则对比,本文方法可降低10%至15%的机器人总行驶距离.本文结论可为指导企业的仓库布局与调度提供借鉴,对我国智能仓储的发展具有重要意义.In recent years,robotic mobile fulfillment systems have become an important development direction of intelligent logistics and warehousing in China.However,the efficiency of this system hinges on the multi-robot scheduling procedure.In this paper,we integrate the decisions of rack storage and retrieval.We formulate an integer programming model to minimize the total distance of robots.To solve the problem,we first present a dynamic programming method based on beam search to find an initial solution quickly.We then embed the integer programming model into the adaptive large neighborhood search framework and propose an efficient adaptive matheuristic,which can find a near-optimal solution within small computational runtimes.The results show that the proposed integrated optimization approach can reduce about 60%of the traveling distance of robots compared with those methods that consider the two problems separately.In addition,our method can reduce 10%to 15%of the traveling distance of robots compared with the nearest assignment rule.This paper provides a theoretical guidance and decision support for the warehouse layout configurations,which has important practical significance for the development of the intelligent warehouses of China.

关 键 词：移动货架系统 存-取货架联合调度 多机器人 动态规划 自适应启发式算法 

分 类 号：C934[经济管理—管理学]