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

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