Abstract: Conventionally, vehicle routing problems with time window(VRPTW)are defined in constant vehicle’s speed. Typically, vehicle’s speed is different in variant duration of time. This paper explicitly considers time-dependent vehicle routing problem with time window(TDVRPTW)through regarding the speed as a time-dependent piecewise function, which is more meaningful. Moreover, to overcome the defect of getting into the local optimum in simulated annealing algorithm(SA)and the slow convergence speed of the variable neighborhood search algorithm(VNS), an improved algorithm, simulated annealing with variable neighborhood(SAVN), for solving TDVRPTW is proposed based on the combination of SA and VNS, which changes into a new neighborhood structure to enlarge the search space when getting into the local optimum. The capacity as well as the velocity of the algorithm for global search undergoes significant improvability. And the simulation result of SAVN, compared with those of SA and VNS, shows the ability of SAVN to jump from local optimal solution and guide the search in promising directions.

Key words: time-dependent, vehicle routing problem, improved simulated annealing, variable neighborhood search algorithm

摘要： 本文在经典的带时间窗的车辆路径问题(VRPTW)的基础上,考虑不同时间段车辆行驶速度不同的情况,研究速度时变的带时间窗车辆路径问题(TDVRPTW),使问题更具实际意义。本文用分段函数表示不同时间段下的车辆行驶速度,并解决了速度时变条件下行驶时间计算的问题。针对模拟退火算法(SA)在求解VRPTW问题时易陷入局部最优解,变邻域搜索算法(VNS)在求解VRPTW问题时收敛速度慢的问题,本文将模拟退火算法以一定概率接受非最优解的思想和变邻域搜索算法系统地改变当前解的邻域结构以拓展搜索范围的思想结合起来,提出了一种改进的算法——变邻域模拟退火算法(SAVN),使算法在退火过程中一陷入局部最优解就改变邻域结构,更换搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。通过在仿真实验中将SAVN算法的求解结果与VNS算法、SA算法进行对比,验证了SAVN算法确实能显著提升算法跳出局部最优解的能力。

关键词: 速度时变, 车辆路径优化, 改进模拟退火算法, 变邻域搜索算法