基于改进遗传算法的动态路径规划研究

来源：计算机工程与应用杂志2018年第19期北京时间：

作者：董小帅1，2，3，毛政元1，2，3

单位：1.福州大学 福建省空间信息工程研究中心，福州 350002；2.福州大学 空间数据挖掘与信息共享教育部重点实验室，福州 350002；3.福州大学 地理空间信息技术国家地方联合工程研究中心，福州 350002

摘要：在静态路网模型的基础上构建时间依赖的动态路网模型数据库，进行动态路径规划问题研究。针对传统遗传算法在解决此问题中存在的“早熟收敛”、局部搜索能力差等问题，对其进行下列改进：结合随机选择和趋于终点方向的种群初始化策略，在保持初始种群多样性的同时提高其个体质量；根据空间邻近关系选择交叉位置点，有效保留父代优良基因，同时避免“早熟收敛”；采用节点适应度的局部搜索策略，根据路段所属道路等级、转弯类型、实时路况以及与局部路段终点的夹角四个影响因子，构建当前节点邻接节点的适应度，提高局部搜索能力。研究结果表明，改进后的遗传算法具有更好的收敛效果和收敛稳定性，满足行进中的动态最优路径规划对求解精度和效率的要求。

关键词：动态路径规划,改进遗传算法,邻近交叉策略,局部搜索