基于改进GA和CBS算法的多Agent路径优化方法研究

作     者：苗卓 

作者单位：深圳大学 

学位级别：硕士

导师姓名：程涛

授予年度：2022年

学科分类：080202[工学-机械电子工程] 08[工学] 0804[工学-仪器科学与技术] 0802[工学-机械工程] 

主      题：多Agent 多配送中心 路径规划 任务分配 两阶段混合优化算法 

摘      要：技术的进步带动机器人的大规模应用,自主移动机器人在智能制造、仓储系统、医用配送等环境中正逐步代替工人。随着社会的发展和消费的转型升级,客户对机器人的服务时间等有着更高的要求。配送的时效性等,作为评价客户消费体验的重要指标变的越来越重要。在物流运输过程中,各物流企业为提升运输效率,采用无人仓分拣运输系统,以自主移动机器人为载体进行分拣与配送。无人仓分拣运输系统一般规模较大,存在多个配送中心。同时,仓储系统往往需要多个自主移动机器人在避免碰撞的情况下协作完成订单配送任务。本文在具有多配送中心的无人仓分拣运输系统中,进行带时间窗和载重量约束的多Agent任务分配和路径优化问题研究。本文考虑快件具有服务的时间窗和机器人的载运量约束,从带软时间窗的路径规划问题(Vehicle Routing with Soft Time Windows,VRPSTW)出发,建立仓储环境下支持多Agent路径优化的带软时间窗的多Agent的任务分配问题数学模型,并采用遗传算法求解。针对遗传算法局部搜索能力不足的特点,在遗传算法中引入大规模邻域搜索,改进了算法求解质量。本文在带软时间窗的任务分配问题基础上,设计物流分拣中心场景抽象地图,以仓储配送网全局路径最优为目标,构建仓储环境中具有多配送中心的快件配送优化模型。设计了相同尺寸约束的均匀聚类算法,提出一种基于聚类的配送区域划分方法,在配送区域划分基础之上进行多Agent任务分配。该基于两阶段的任务分配方法,在满足配送约束的前提下,降低了配送网络的路径成本与车辆密度,提高了系统运行效率。本文在大规模智能体路径规划(Multi-Agent Path Finding,MAPF)问题中,引入时间窗约束(Time window constraint,TWC),将时间窗惩罚函数作为MAPF的优先级(Prioritizing conflicts,PC)评估准则,改进基于冲突的搜索算法(Conflict-Based Search,CBS),解决多Agent之间的冲突问题;设计先进行多Agent任务分配,再求解连续的大规模智能体路径规划问题(Lifelong MAPF)的两阶段混合优化算法,实现了多Agent在满足多约束情况下的总体路径最优。最后,搭建模拟试验系统,进行两阶段混合优化算法的仿真与结果分析,验证了所提算法优越性。