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

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