如今,自动导引车(Automated Guided Vehicles,AGVs)广泛用于制造业和仓储业等领域。例如,在自动化仓储系统中,占总成本最多的是AGV的运输成本,AGV以电能为能源,配合合理的调度策略和良好的AGV路径规划策略,能显著降低运输成本、提升运输效率。因此,本文构建了一种分布式多AGV系统,并针对多AGV的任务排序问题和路径规划问题提出了解决方案,主要的创新点如下:(1)在AGV任务排序问题中,对于具有N项任务的AGV,现有的基于2-opt局部搜索算符的解决方案需要O(N ~3)的复杂度来评估所有O(N ~2)种可能的2-opt移动,存在复杂度高、计算时间长等缺点。因此,本文引入一系列辅助数据结构将该方法的时间复杂度从O(N ~3)降低到O(N ~2)。实验证明,采用辅助数据结构的高效2-opt移动算符可以大大降低估算2-opt移动所需的复杂度,从而显著提高搜索效率。(2)为了解决AGV的动态多任务排序问题,本文提出一种动态蒙特卡罗树搜索算法,利用历史信息来加快排序过程,及时适应动态变化;其次,使用2-opt移动和3-opt移动构成的邻域交替搜索局部空间,优化动态蒙特卡罗树搜索算法生成的解决方案。实验证明,基于动态蒙特卡罗树搜索和变邻域局部搜索算法能显著提升AGV的运输效率,减少运输成本,从而提高企业的经济效益。(3)为了解决多AGV路径规划问题,本文提出了两阶段路径规划方法。首先,采用改进的A*算法为各个AGV规划一条从任务起点到任务终点且不与静态障碍物碰撞的路径。其次,若AGV沿着规划路径行驶时发生冲突,AGV通过携带的传感器提前感知其周围两个单位内的其它AGV的运行状态,然后采用基于博弈论的方法消解冲突,避免AGV之间的相互碰撞,更快速的完成任务。