Abstract: The rolling cycle strategy is the main research strategy used by current scholars to solve the dynamic vehicle routing planning (DVRP) problem by using optimization algorithms. The pre-optimization algorithm is improved based on genetic algorithm (GA). GA is prone to prematurity and local optimality, so the solution quality cannot often reach the best. To solve this problem, a greedy reconstruction strategy is proposed to improve GA algorithm. Greedy reconstruction genetic algorithm (GRGA) randomly eliminates a fixed number of customer points in each path, and uses the greedy reconstruction strategy to insert the eliminated points into each path in turn, and retains the solution with the lowest cost, abandoning the completely random policy principle, so that the solution can skip the local optimum. After each iteration, the variable neighborhood descent (VND) algorithm is used to conduct a deep search and complete one iteration. Finally, three groups of tests are conducted. The first group is to test the algorithm effect by using Solomon data set on a unified platform. The second group saves the data obtained by the pre-optimization algorithm and the comparison algorithm respectively, and uses a dynamic scheduling optimization algorithm to schedule the initial path formed by each pre-optimization algorithm in the dynamic scheduling cycle by using the control variable method to test the effectiveness of the improved algorithm. The third group is to test the effect of the pre-optimization algorithm by using a practical case.

Key words: time window, genetic algorithm, variable neighborhood descending search algorithm, greedy reconstruction strategy, rolling period

摘要： 滚动周期策略是当前学者利用优化算法解决动态车辆路径规划（dynamic vehicle routing planning，DVRP）问题的主要研究策略。预优化算法是基于遗传算法（genetic algorithm，GA）进行改进。GA易早熟和易陷入局部最优的特点，使解的质量往往不能达到最好。针对此问题，在GA算法上提出了贪婪重构策略进行改进。贪婪重构遗传算法（greedy reconstruction genetic algorithm，GRGA）随机剔除每条路径固定数量的客户点，利用贪婪重构策略依次将剔除点插入到各个路径，保留成本最低的解，摒弃了完全随机的策略原则，使解可以跳出局部最优。在每次迭代之后利用变邻域下降搜索算法（variable neighborhood descent，VND）进行深度搜索，完成一次迭代。最后进行三组测试，第一组是在统一平台上采用Solomon数据集测试算法效果，第二组是把预优化改进算法与对比算法得到的数据分别进行保存，利用控制变量法在动态调度周期使用一种动态调度优化算法，分别对每个预优化算法形成的初始路径进行调度，测试改进算法的有效性，第三组是采用实际案例测试预优化算法的效果。

关键词: 时间窗, 遗传算法, 变邻域下降搜索算法, 贪婪重构策略, 滚动周期