首页|改进蚁群算法的送餐机器人路径规划

改进蚁群算法的送餐机器人路径规划

扫码查看
原文链接
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 万方数据
蚁群算法拥有良好的全局性、自组织性、鲁棒性,但传统蚁群算法存在许多不足之处.为此,针对算法在路径规划问题中的缺陷,在传统蚁群算法的状态转移公式中,引入目标点距离因素和引导素,加快算法收敛性和改善局部最优缺陷.在带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)上,融合蚁群算法和遗传算法,并将顾客时间窗宽度以及机器人等待时间加入蚁群算法状态转移公式中,以及将蚁群算法的解作为遗传算法的初始种群,提高遗传算法的初始解质量,然后进行编码,设置违反时间窗约束和载重量的惩罚函数和适应度函数,在传统遗传算法的交叉、变异操作后加入了破坏-修复基因的操作来优化每一代新解的质量,在Solomon Benchmark算例上进行仿真,对比算法改进前后的最优解,验证算法可行性.最后在餐厅送餐问题中把带有障碍物的仿真环境路径规划问题和VRPTW问题结合,使用改进后的算法解决餐厅环境下送餐机器人对顾客服务配送问题.
Path planning of a meal delivery robot based on an improved ant colony algorithm
The ant colony algorithm has advantages,such as good global ability,self-organization,and robustness,but the conventional ant colony algorithm has several drawbacks.Herein,with the goal of addressing these drawbacks,in the path planning problem,according to the conventional ant colony algorithm,the distance factor of the target point and the guide element are added to the state transition formula to optimize the convergence of the ant colony algorithm in the path planning and enhance the defect of local optimal point.On the vehicle routing problem with time window(VRPTW),the ant colony algorithm and genetic algorithm are combined,and the customer time window width and ro-bot waiting time are added to the state transition formula of the ant colony algorithm.The solution of the ant colony al-gorithm is taken as the initial population of the genetic algorithm to enhance the quality of the initial solution of the ge-netic algorithm,and subsequently,coding is conducted.The penalty function and fitness function violating the time win-dow constraint and load are set.After the mutation and crossover operation of the conventional genetic algorithm,the damage and repair gene operation is added to optimize the quality of each generation of new solutions.Simulations are performed on the Solomon benchmark example,and the optimal solutions before and after enhancement of the al-gorithm are compared to confirm the feasibility of the algorithm.To apply this to a real-world problem,the path plan-ning problem in a simulative environment with obstacles and the VRPTW problem are joined using the enhanced al-gorithm to solve the customer service delivery problem of the restaurant delivery robot.

ant colony algorithmgenetic algorithmstate transition formulafitness functionguiding elementlocal op-timuminitial populationtime window constraintpath planning

蔡军、钟志远

展开 >

重庆邮电大学 自动化学院, 重庆 400065

蚁群算法 遗传算法 状态转移公式 适应度函数 引导素 局部最优 初始种群 时间窗约束 路径规划

国家自然科学基金国家自然科学基金重庆市基础研究与前沿探索项目

6167307961703068cstc2018jcyjAX0160

2024

10.11992/tis.202205056

智能系统学报
中国人工智能学会　哈尔滨工程大学

智能系统学报

CSTPCD北大核心
影响因子：0.672
ISSN：1673-4785
年,卷(期)：2024.19(2)
  • 1
  • 26