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

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

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