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

A New Scheduling Algorithm for High-speed Sorting System of Light and Small Packages

作　　者：苏志远 谭树勇 李金澎 程彬 韦凌云 SU Zhi-yuan;TAN Shu-yong;LI Jin-peng;CHENG Bin;WEI Ling-yun(School of Modern Post,Beijing University of Posts and Telecommunications,Beijing 100876,China)

机构地区：[1]北京邮电大学现代邮政学院,北京100876

出　　处：《系统工程》2024年第4期123-138,共16页Systems Engineering

摘　　要：新型轻小包裹高速分拣系统综合应用两种不同类型的机器人(分拣机器人、料箱搬运机器人),首先分拣机器人将包裹先分拣至分拣区域内的周转料箱中,当周转料箱满箱后,料箱搬运机器人将之搬运至装箱区域打包。该系统可以基于分拣需求的变化动态调整分拣系统中机器人数目以及分拣区域面积大小,有利于降低分拣作业设备损耗及系统能耗。本文针对这种新型轻小包裹高速分拣系统调度问题展开研究,首先建立了综合考虑两种机器人、两阶段分拣过程(先分拣到周转料箱,再搬运周转料箱至打包位置)和动态分拣料口(分拣区域内周转料箱放置点不是固定的)的基于最低分拣成本的三维度调度模型;其次针对该调度模型两阶段三维度调度的特点,设计了一种两段三层可行解整数编码,及一种基于编码编辑距离(Levenshtein距离)的计算种群多样性的方法;然后,设计了一种结合两种变邻域算子(交换算子、贪心算子)和禁忌搜索的混合分散搜索算法,对模型进行求解;最后使用改进的MAPF基准测试数据集,对上述模型和算法进行了验证。实验结果表明:本文提出的模型有效,能满足实际使用要求,求解算法的求解精度相较于标准遗传算法、标准分散搜索算法分别提升了10.3%和6.5%,收敛速度相较于标准分散搜索算法提升了15.5%,且数据集规模越大,本算法的收敛速度优势越突出。A new high-speed sorting system for light and small packages comprehensively applies two different types of sorting robots(sorting robot and bin handling robot)in this paper.First,the sorting robots sort the packages to the bin in the sorting area.When the bin is full,the bin handling robot carries it to the packing area for packaging.This system can dynamically adjust the number of robots and the size of the sorting area based on the change of sorting requirements,which is conducive to reduce the loss of sorting equipment and system energy consumption.In this paper,the scheduling problem of this new high-speed sorting system for light and small packages is studied.At first,a three-dimensional scheduling model based on the lowest sorting cost is established,which comprehensively considers two kinds of sorting robots,a two-stage sorting process(first sorting to the bin,and then transporting the bin to the packaging area)and a dynamic sorting material port(the location of the bin in the sorting area is not fixed);Secondly,according to the characteristics of the two-stage three-dimensional scheduling model,a two segment and three layer integer coding of feasible solution is designed,and a method to calculate population diversity based on editing distance(Levenshtein distance)is designed;Then,a hybrid scatter search algorithm combining two variable neighborhood operators(exchange operator,greedy operator)and tabu search is designed to solve the model;Finally,the improved MAPF benchmark dataset is used to verify the above models and algorithms.The experimental results show that the model proposed in this paper is effective and can meet the requirements of practical use.The solution accuracy of the algorithm is 10.3%and 6.5%higher than that of the standard genetic algorithm and the standard scatter search algorithm respectively,and the convergence speed is 15.5%higher than that of the standard scatter search algorithm.The larger the data set,the more prominent the convergence speed advantage of the algorithm.

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

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]