自动分拣仓库中多载量AGV调度与路径规划算法

Multi-load AGVs scheduling and routing algorithm in automatic sorting warehouse

在自动分拣仓库中,多载量自动导引小车(AGV)具有强运输能力,但其多载量特征也增加了调度与路径规划的复杂性。针对多载量AGV调度与路径规划的协同优化问题,以最小化最大搬运完成时间为目标,建立了该问题的混合整数线性规划模型,并提出一种聚类协同优化算法。算法首先定义了包裹相似度,设计聚类算法划分包裹组,使每个包裹组可由多载量AGV在一次作业中完成分拣;进而针对问题的多决策特征,设计协同进化遗传算法对包裹组进行指派和排序,并将无冲突路径规划算法引入到协同进化遗传算法的解码方案中,用以搜索最优路径并解决多AGV路径冲突,从而实现了多载量AGV调度与路径规划的协同优化。通过不同问题规模的仿真实验验证了所提算法的高效性和稳定性。

In an automatic sorting warehouse,the multi-load AGV has strong transportation capacity,but its multi-load characteristic also increases the complexity of scheduling and routing.Aiming at the collaborative optimization problem of multi-load AGVs scheduling and routing,a mixed integer linear programming model was established with the goal of minimizing the maximum handling completion time.Then,a Clustering-Collaborative Optimization Algorithm(CCOA)was proposed.Firstly,the package similarity was defined,and a clustering algorithm was designed to divide the packages into several groups,so that the packages contained in each group could be sorted by a multi-load AGV in one operation trip.Furthermore,according to the multi-decision characteristics of the problem,a Co-evolutionary Genetic Glgorithm(CGA)was designed to assign and sort the divided groups,and the conflict-free routing algorithm designed was embedded in CGA to search the optimal route and resolve the conflicts between multiple AGVs,so as to achieve the collaborative optimization of multi-load AGVs scheduling and routing.Extensive simulation experiments with different problem scales were carried out to verify the efficiency and stability of the proposed algorithm.