计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (19): 49-55.DOI: 10.3778/j.issn.1002-8331.1708-0248

• 理论与研发 • 上一篇    下一篇

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

董小帅1,2,3,毛政元1,2,3   

  1. 1.福州大学 福建省空间信息工程研究中心,福州 350002
    2.福州大学 空间数据挖掘与信息共享教育部重点实验室,福州 350002
    3.福州大学 地理空间信息技术国家地方联合工程研究中心,福州 350002
  • 出版日期:2018-10-01 发布日期:2018-10-19

Research on solution of dynamic Vehicle Routing Problem based on improved genetic algorithm

DONG Xiaoshuai1,2,3, MAO Zhengyuan1,2,3   

  1. 1.Provincial Spatial Information Engineering Research Center, Fuzhou University, Fuzhou 350002, China
    2.Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University, Fuzhou 350002, China
    3.National Engineering Research Centre of Geospatial Space Information Technology, Fuzhou University, Fuzhou 350002, China
  • Online:2018-10-01 Published:2018-10-19

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

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

Abstract: A time-dependent dynamic database of road network model is established based on the static road network model and the research on dynamic VRP is carried out. Considering the barriers caused by the traditional genetic algorithm in solving this problem, such as “premature convergences”, poor local search abilities and so forth, the following improvements have been made:The quality of initial population is improved while the diversity of the initial population is maintained by combining population initialization strategy of random selection with that of direction tending to end. In order to preserve excellent genes of the parent generation effectively and avoid “premature convergence”, the cross point is selected according to proximity. Based on the local search strategy of node fitness, the fitness of adjacent nodes of the current one is constructed according to four influence factors which are grade, turning type, real-time traffic condition of the road containing the section and the angle between the road and the end of the local section, and the local search capabilities are improved by doing so. The results show that the improved genetic algorithm has a better convergence effect and convergence stability, and meets the requirements for precision and efficiency in planning the dynamic optimal path during marching.

Key words: dynamic VRP(Vehicle Routing Problem), improved genetic algorithm, adjacent cross strategy, local search