多搬运任务下考虑碰撞避免的AGV路径规划

为提升自动导引小车在“货到人”仓库中的运行效率,针对AGV-托盘任务分配、单AGV路径规划及多AGV碰撞避免三个子问题的研究,以最小化AGV行驶距离为目标构建数学模型。首先,根据AGV与托盘的双边匹配问题特点设计改进的匈牙利算法求解匹配结果。其次,提出一种二维编码机制的改进遗传算法（improved genetic algorithm,IGA）,采用一种局部搜索算子代替原变异操作,在提高算法搜索性能的基础上使其成功应用于单AGV路径规划问题。然后,利用时空数据设计一种三维网格冲突检测方法,并根据商品SKU数量设定AGV的优先级以降低多AGV执行任务时的碰撞概率。最后,在32 m×22 m的仓库中针对不考虑碰撞与考虑碰撞两种情形进行AGV路径优化分析,给出合理的行驶距离和碰撞次数。IGA与标准遗传算法的对比结果显示,IGA能够在合理的时间内获得更高质量的解,行驶距离减少约1.74%,算法求解时间缩短约37.07%。此外,针对AGV数量灵敏度分析,在不同目标托盘规模下测试不同数量的AGV对行驶距离和碰撞次数的影响,发现14~16台AGV数量是最佳配置,验证了模型的可行性和算法的有效性。

AGV path planning considering collision avoidance of multiple handling tasks

To improve the operation efficiency of automated guided vehicle in the "parts-to-picker" warehouse, aiming at the three sub-problems of AGVs-pallets task assignment, single AGV path planning and multi-AGVs collision avoidance, this paper built a mathematical model with the objective of minimizing the driving distance of AGVs. Firstly, it designed the improved Hungarian algorithm to solve the matching results according to the characteristics of bipartite matching problem between AGVs and pallets. Secondly, it proposed an improved genetic algorithm(IGA) with two-dimensional encoding mechanism, for which it designed a local search operator replace the original mutation operation. It successfully applied the algorithm to the single AGV path planning problem on the premise of improving the search performance of this algorithm. Then, it utilized spatiotemporal data to design a three-dimensional mesh conflict detection method, and set the priority of AGVs according to the number of commodity SKUs to reduce the collision probability when multiple AGVs execute tasks. Finally, it studied the AGV path optimization for the two scenarios of no collision and considering collision at the warehouse of 32 m×22 m, which gave reasonable driving distance and collision times. IGA was compared with standard genetic algorithm. The results indicate that the IGA can obtain the higher quality solutions in a reasonable time, which reduced the driving distance by about 1.74% and the solution time of the algorithm by about 37.07%. Furthermore, for the sensitivity analysis on the number of AGVs, it tested the influence of different numbers of AGVs on the driving distance and the number of collisions under different target pallets sizes. It was found that the number of 14~16 AGVs is the optimal configuration. These results verifiy the feasibility of the model and the effectiveness of the proposed algorithm.