一种新型轻小包裹高速分拣系统调度算法

作者：苏志远^*; 谭树勇; 李金澎; 程彬; 韦凌云

来源：系统工程, 2023, 1-21.

• 轻小包裹分拣
• 机器人调度
• 变邻域
• 禁忌搜索
• 混合分散搜索

新型轻小包裹高速分拣系统综合应用两种不同类型的分拣机器人（分拣机器人、料箱搬运机器人），首先分拣机器人将包裹先分拣至分拣区域内的周转料箱中，当周转料箱满箱后，料箱搬运机器人将之搬运至装箱区域打包。该系统可以基于分拣需求的变化而动态调整分拣系统中机器人数目以及分拣区域面积大小，有利于降低分拣作业设备损耗及系统能耗。本文针对这种新型轻小包裹高速分拣系统调度问题展开研究，首先建立了综合考虑两种分拣机器人、两阶段分拣过程（先分拣到周转料箱，再搬运周转料箱至打包位置）和动态分拣料口（分拣区域内周转料箱放置点不是固定的）的基于最低分拣成本的三维度调度模型；其次针对该调度模型两阶段三维度调度的特点，设计了一种两段三层可行解整数编码，同时设计了一种基于编辑距离(Levenshtein距离)的计算种群多样性的方法；然后，设计了一种结合两种变邻域算子（交换算子、贪心算子）和禁忌搜索的混合分散搜索算法，对模型进行求解；最后使用改进的MAPF基准测试数据集，对上述模型和算法进行了验证。实验结果表明：本文提出的模型有效，能满足实际使用要求，求解算法的求解精度相较于标准遗传算法和标准分散搜索算法分别提升了10.3%和6.5%，收敛速度相较于标准分散搜索算法提升了15.5%，且数据集规模越大，本算法的收敛速度优势越突出。

• 单位
  北京邮电大学