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

Path planning of a meal delivery robot based on an improved ant colony algorithm

作　　者：蔡军[1] 钟志远 CAI Jun;ZHONG Zhiyuan(College of Automation,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

机构地区：[1]重庆邮电大学自动化学院,重庆400065

出　　处：《智能系统学报》2024年第2期370-380,共11页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学基金项目(61673079,61703068);重庆市基础研究与前沿探索项目(cstc2018jcyjAX0160)。

摘　　要：蚁群算法拥有良好的全局性、自组织性、鲁棒性,但传统蚁群算法存在许多不足之处。为此,针对算法在路径规划问题中的缺陷,在传统蚁群算法的状态转移公式中,引入目标点距离因素和引导素,加快算法收敛性和改善局部最优缺陷。在带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)上,融合蚁群算法和遗传算法,并将顾客时间窗宽度以及机器人等待时间加入蚁群算法状态转移公式中,以及将蚁群算法的解作为遗传算法的初始种群,提高遗传算法的初始解质量,然后进行编码,设置违反时间窗约束和载重量的惩罚函数和适应度函数,在传统遗传算法的交叉、变异操作后加入了破坏-修复基因的操作来优化每一代新解的质量,在Solomon Benchmark算例上进行仿真,对比算法改进前后的最优解,验证算法可行性。最后在餐厅送餐问题中把带有障碍物的仿真环境路径规划问题和VRPTW问题结合,使用改进后的算法解决餐厅环境下送餐机器人对顾客服务配送问题。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 robot waiting time are added to the state transition formula of the ant colony algorithm.The solution of the ant colony algorithm is taken as the initial population of the genetic algorithm to enhance the quality of the initial solution of the genetic algorithm,and subsequently,coding is conducted.The penalty function and fitness function violating the time window 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 algorithm are compared to confirm the feasibility of the algorithm.To apply this to a real-world problem,the path planning problem in a simulative environment with obstacles and the VRPTW problem are joined using the enhanced algorithm to solve the customer service delivery problem of the restaurant delivery robot.

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

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]