一种基于分步遗传算法的多无人清洁车区域覆盖路径规划方法

作者：罗志远; 丰硕; 刘小峰; 陈俊风; 王瑞

来源：电子测量与仪器学报, 2020, 34(08): 43-50.

DOI：10.13382/j.jemi.B2002917

• 多无人清洁车
• 区域覆盖
• 多旅行商问题
• 聚类算法
• 遗传算法

为了解决不规则区域内多无人清洁车区域覆盖路径的全局规划问题,提出一种基于分步遗传算法的区域覆盖方法。首先,将目标区域依据清洁车大小进行栅格化,将多车辆区域覆盖路径规划问题转化为多旅行商(MTSP)问题。然后,使用分步遗传算法求解多旅行商问题:第1步采用模糊c均值聚类方法将求解多旅行商问题转化为求解多个单旅行商(TSP)问题;第2步使用了分步遗传算法对每个单旅行商问题进行求解,并使用杂草入侵算法中子父代共存的思想对遗传算法的选择机制进行改进。最后,分别在模拟的校园场景和小区场景中进行仿真实验。实验结果表明,在两个场景中提出的方法能够实现多无人清洁车完成区域路径覆盖,提出的分步遗传算法比分组遗传算法收敛速度更快;在校园场景中,提出的分步遗传算法相比于分组遗传算耗时减少54%,最优解路径长度减少38%;在小区场景中,提出的分步遗传算法相比于分组遗传算耗时减少55%,最优解路径长度减少44%。

• 单位
  河海大学; 中国铁道科学研究院集团有限公司