Abstract: 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.

Key words: multi-load automated guided vehicle, scheduling, routing, collaborative optimization, automatic sorting warehouse

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

关键词: 多载量自动导引小车, 调度, 路径规划, 协同优化, 自动分拣仓库