罗志远,丰 硕,刘小峰,陈俊风,王 瑞.一种基于分步遗传算法的多无人清洁车区域覆盖路径规划方法[J].电子测量与仪器学报,2020,34(8):43-50 |
一种基于分步遗传算法的多无人清洁车区域覆盖路径规划方法 |
Method of area coverage path planning of multi-unmanned cleaning vehicles based on step by step genetic algorithm |
|
DOI: |
中文关键词: 多无人清洁车 区域覆盖 多旅行商问题 聚类算法 遗传算法 |
英文关键词:multi-unmanned cleaning vehicles area coverage MTSP clustering algorithm genetic algorithm |
基金项目:江苏省重点研究开发项目(BK20192004, BE2018004-04, BE2017071,BE2017647)、东南大学生物电子学国家重点实验室开放研究基金(2019005)项目资助 |
|
|
摘要点击次数: 265 |
全文下载次数: 736 |
中文摘要: |
为了解决不规则区域内多无人清洁车区域覆盖路径的全局规划问题,提出一种基于分步遗传算法的区域覆盖方法。 首
先,将目标区域依据清洁车大小进行栅格化,将多车辆区域覆盖路径规划问题转化为多旅行商(MTSP)问题。 然后,使用分步
遗传算法求解多旅行商问题:第 1 步采用模糊 c 均值聚类方法将求解多旅行商问题转化为求解多个单旅行商(TSP)问题;第 2
步使用了分步遗传算法对每个单旅行商问题进行求解,并使用杂草入侵算法中子父代共存的思想对遗传算法的选择机制进行
改进。 最后,分别在模拟的校园场景和小区场景中进行仿真实验。 实验结果表明,在两个场景中提出的方法能够实现多无人清
洁车完成区域路径覆盖,提出的分步遗传算法比分组遗传算法收敛速度更快;在校园场景中,提出的分步遗传算法相比于分组
遗传算耗时减少 54%,最优解路径长度减少 38%;在小区场景中,提出的分步遗传算法相比于分组遗传算耗时减少 55%,最优
解路径长度减少 44%。 |
英文摘要: |
In order to solve the problem of global planning of multi-unmanned vehicle coverage paths in irregular areas, a regional
coverage method based on stepwise genetic algorithm is proposed. First, the target area is rasterized according to the size of the cleaning
vehicle, and the multi-vehicle area coverage path planning problem is transformed into a multi-travel agent (MTSP) problem. Then, the
multi-traveler problem is solved by using the stepwise genetic algorithm. The first step is to transform the multi-traveler problem into the
multi-traveler (TSP) problem by using the fuzzy C-means clustering method. In the second step, a stepwise genetic algorithm is used to
solve each single traveling salesman problem, and the selection mechanism of the genetic algorithm is improved by using the idea of
neutron parent coexistence of weed invasion algorithm. Finally, simulation experiments are carried out in the simulated campus scene and
community scene respectively. The experimental results show that the proposed method in the two scenarios can achieve multi-unmanned
cleaning vehicles to complete the regional path coverage, and the proposed step-genetic algorithm has a faster convergence rate than the
grouping genetic algorithm. In campus scenarios, the proposed stepwise genetic algorithm is 54% less time-consuming and 38% less
optimal solution path length than the grouped genetic algorithm. In the cell scenario, the proposed stepwise genetic algorithm reduces the
time consumption by 55% and the optimal solution path length by 44% compared with the grouped genetic algorithm. |
查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|