Abstract: Focusing on the practical scheduling scenario of a single workstation task scheduling problem of “carton-transfer-unit” warehouse system under multi-path hybrid environments, this paper investigates a special  multi-trip mixed return vehicle routing problem. First, considering a hybrid path mode that includes both open and closed routes, it proposes an integer linear programming model to minimize the maximum completion time of mixed outbound and inbound tasks for robots. Next, based on the pick-and-place characteristics of robots performing, it integrates the population management mechanism of genetic algorithms to improve the adaptive large neighborhood search process, aiming to avoid premature convergence to local optima while balancing the trade-off between the convergence speed of neighborhood search and population diversity. Finally, the proposed model and method are numerically validated by simulations and comparative analysis using test instances of various scales. Experimental results against several baseline methods demonstrate that the proposed algorithm significantly improves convergence, stability, and convergence speed. The findings provide methodological reference and decision support for robot task scheduling in single-workstation settings in “carton-transfer-unit” warehouse systems.

Key words: semi-automatic storage and retrieval system, multi-path hybrid, genetic algorithm, large neighborhood search algorithm

摘要： 针对“货箱到人”仓储系统单工作台任务调度问题，特别是在多路径混合下的实际调度场景，研究探讨了特殊的多行程混合回程的车辆路径问题。首先，考虑开闭混合的路径模式，构建了旨在最小化机器人去/回程混合任务最大完成时间的整数线性规划模型。其次，基于模型中机器人执行出/入库任务的取放特征，提出混合遗传自适应大规模邻域搜索算法。该算法通过遗传算法的种群管理机制改进自适应大规模邻域搜索算法，以避免其过早陷入局部最优，同时平衡邻域搜索收敛速度与种群收敛性。最后，通过不同规模仿真算例的模拟与对比分析，验证了所提模型与方法的有效性，并与不同基线方法进行实验对比。结果表明，该算法在收敛性、稳定性及收敛速度方面均有显著提升。研究成果可为“货箱到人”仓储系统中机器人单工作台任务调度研究提供方法参考与决策支持。

关键词: 半自动存储检索系统, 多路径混合式, 遗传算法, 大规模邻域搜索算法