Assigning parcel destinations to drop‐off points in a congested robotic sorting system
研究在拥堵的机器人分拣系统中，如何将包裹目的地分配到投递点以最小化吞吐时间，通过构建开放排队网络和自适应大邻域搜索算法，平衡机器人行驶距离和拥堵，并验证了算法有效性。
Abstract Autonomous mobile robots are increasingly used for order picking, order delivery, and parcel sorting. This article studies a robotic sorting system that uses robots to transport parcels from loading stations to drop‐off points. While this system provides more flexible throughput capacity than conventional sorting systems, its performance is significantly affected by the robot travel distance and robot congestion. We study the problem of assigning parcel destinations to drop‐off points to minimize the throughput time, trading off travel distance and congestion. First, an open queuing network (OQN) with finite capacity queues is constructed to estimate the congested throughput time. A decomposition method based on the analysis of the tandem queuing network of each aisle is developed to solve the OQN. Second, using the obtained throughput time as an objective and the destination assignments as decisions, we formulate an optimization model and solve the problem using an adaptive large neighborhood search (ALNS) algorithm. We validate the accuracy of the OQN by simulation and verify the efficiency of the ALNS algorithm by comparing it with Gurobi, a tabu search algorithm, several heuristic assignment rules, and the rule used by our case company, that assigns high demands close to loading stations. The results show that the ALNS solution provides a relatively low throughput time by dispersing destinations with high demands over drop‐off points. In addition, we investigate the effects of different system layouts and travel path topologies. We also show that the ALNS assignment rule produces substantially lower operational costs than the heuristic assignment rules for a given required throughput capacity.