Abstract: The Dynamic Vehicle Routing Problem with Time Windows（DVRPTW） is broken down into a series of delaying snapshots based on event-trigger. And a dynamic model of DRPTW is established based on these snapshots. An improved large neighborhood search algorithm with double buffers is presented to solve the problem. The algorithm can implement that the latest requests are inserted steady. Computational results of a large number of test problems, which are cited from Solomon’s static benchmarks and Lacker’s dynamic data set, show that the model and method are valid and are superior to other methods in most instances.

Key words: Dynamic Vehicle Routing Problem（DVRP）, time windows, Large Neighborbood Search（LNS）, real routing, heuristics

摘要： 基于事件触发，把带时间窗口动态车辆路径规划问题（DVRPTW）分解成一系列延迟快照，在快照基础上建立相应的动态数学模型，并提出双缓冲区改进大邻域搜索算法进行求解。利用算法的特点，实现新请求无缝插入。采用Solomon设计的56个100节点范例和Lackner相应的动态测试数据，经不同类型动态实例的实验表明，所建立的模型和给出的算法是有效的。

关键词: 动态车辆路径规划问题（DVRP）, 时间窗口, 大邻域搜索, 实时规划, 启发式算法