电商RMFS系统订单分配与路径规划联合优化方法

Joint optimization of order allocation and path planning in e-commerce robotic mobile fulfillment system

随着电子商务的蓬勃发展,海量客户需求和高频率、多品种、小批量的订单特性为订单拣选业务带来巨大挑战。在物流智能化的趋势下,大量电商企业采用移动机器人拣货系统(Robotic Mobile Fulfillment System,RMFS)进行订单拣选。订单分配和拣选路径规划是影响仓库订单拣选效率的关键决策。为了提高电商RMFS系统拣选效率,降低仓库运营成本,基于电商企业多订单、多货架、多拣选站下的拣选业务场景,以最小化机器人负载距离为目标,构建订单分配与路径规划联合优化模型,设计两阶段的A*算法和自适应大领域搜索算法(Adaptive Large Neighborhood Search,ALNS),在ALNS算法原有框架的基础上提出新的移除和修复算子以适应订单分配问题,并针对30个不同规模算例进行计算分析。计算结果表明,所提出的优化方法收敛快、性能稳定,能够有效缩短机器人行走距离,相比先到先拣选策略最大可缩短47.6%的机器人负载距离。同时,也可在更短时间内获得与CPLEX求解质量相近的解。尤其是当订单数量增长时,相比CPLEX具有突出时间优势,可以实现电商仓储资源的合理调度和配置,从而为电商企业仓储智能化提供有效决策指导。

With the vigorous development of e-commerce, massive customer demands and the characteristics of high-frequency, multi-variety, and small-batch orders have brought great challenges to the order picking process of distribution centers. Under the trend of intelligent logistics, a large number of e-commerce companies use the Robotic Mobile Fulfillment System(RMFS) for order picking. Order allocation and path planning are key decisions that affect the efficiency of order picking in warehouse. In order to improve the picking efficiency of ecommerce RMFS and reduce warehouse operating costs, a joint optimization model of order allocation and path planning was built based on the picking operation scenario of e-commerce enterprises with multiple orders,multiple racks and multiple picking stations, aiming at minimizing the robot loaded distance. Then, a two-stage A* algorithm and Adaptive Large Neighborhood Search(ALNS) algorithm were designed. Based on the original framework of ALNS algorithm, new remove and repair operators were proposed to adapt to order allocation problem. Meanwhile, 30 examples were simulated and solved. Calculation results show that the proposed optimization model and algorithm can shorten the robot loaded distance by up to 47.6% compared with the firstcome-first-service strategy, and can obtain a solution with similar quality to the CPLEX solver in a short time.When the number of orders increases, the algorithm has obvious advantages over CPLEX in terms of time, and has the characteristics of fast convergence and stable performance. In conclusion, the research can effectively shorten the robot walking distance, realize the reasonable scheduling and allocation of storage resources of ecommerce enterprises. It can provide effective decision-making guidance for the intelligent warehouse operation of e-commerce enterprises.