摘要： 针对带时间窗动态车辆路径问题(DVRPTW)，根据优化时间点的选取建立DVRPTW的一系列静态子模型，研究优化调度策略，分别是基于新顾客插入后的重复优化方法、批处理的方法或两者的混合。通过定义紧急顾客，提出一种新的紧急顾客插入和分批驱动调度策略，该策略只需实时插入紧急顾客，具有快速响应、计算负荷小和路径计划更新频率低的优点。仿真对比实验比较了4种策略的优劣，并探讨分批优化间隔长度对调度性能的影响。
关键词:
动态车辆路径问题,
调度策略,
批优化,
实时优化,
时间窗,
紧急顾客
Abstract: Aiming at the Dynamic Vehicle Routing Problem with Time Windows(DVRPTW), a series of static DVRPTW sub-models are established according to the optimization times, and four dynamic schedule strategies are provided to optimize the DVRPTW. Three of the strategies are based on a repeated reoptimization of various instances of the static problem, the batch optimization and a hybrid of both. The fourth is a new one called the emergency customer insertion and batch optimization strategy. This strategy only distinguishes the emergency customers and inserts them into real-time routing plan, and hence has the advantages of quick response, small computational load and low update frequency while routing the vehicles. Simulation experiments compare four strategies and discuss the impact of batch schedule intervals on the schedule performance.
Key words:
Dynamic Vehicle Routing Problem(DVRP),
schedule strategy,
batch optimization,
real-time optimization,
time window,
emergency customer
中图分类号:
王君, 李波, 卢志刚. 带时间窗动态车辆路径问题的优化调度策略[J]. 计算机工程, 2012, 38(13): 137-141.
WANG Jun, LI Bei, LEI Zhi-Gang. Optimization Schedule Strategy for Dynamic Vehicle Routing Problem with Time Window[J]. Computer Engineering, 2012, 38(13): 137-141.