Abstract: In order to effectively solve the dynamic vehicle routing problem with time windows, an improved variable neighborhood search algorithm is proposed and the corresponding mathematical model is established. The algorithm uses the clustering method to complete customer allocation and route planning for the construction of initial solution. Hybrid operators of insert-exchange are used to achieve the shaking process, the later optimization process is presented to improve the solution space, and the best improvement strategy is adopted, which achieves the algorithm a better balance in the solution quality and run-time. The idea of simulated annealing is introduced to control the acceptance of new solutions and the distribution of geographical location, etc, and the route selection is analyzed. Through comparison of experimental results with other algorithms it shows that the algorithm is feasible and efficient.

Key words: improved variable neighborhood search, shaking, simulated annealing, later optimization process, metaheuristic

摘要： 为了切实求解带时间窗的车辆动态路径问题，提出一种改进变邻域搜索算法，并建立了相应数学模型。算法运用聚类方法完成客户分配和路线规划的初始解构建。插入-交换混合算子实现抖动过程，提出后优化过程改进解空间，并采用最佳改进策略实现算法在求解质量和运行时间上的最佳平衡，引入模拟退火思想控制新解接受、地理位置分布等，并对路径选择进行了分析。通过与其他算法的实验结果比较表明该算法的可行性和高效性。

关键词: 改进变邻域搜索, 抖动, 模拟退火, 后优化, 元启发式