Abstract: To find a high-quality approximate solution to the vehicle routing optimization problem with hard time window, a dual objective nonlinear optimization model is established to minimize the number of vehicles and the total driving distance, because the insufficient consideration of time window constraints in the existing mathematical models, and a hybrid variable neighborhood tabu search algorithm is proposed to solve it. On the one hand, an improved saving algorithm is used to generate the initial solution. And three deletion operations and one insertion operation are designed to optimize the number of vehicles in the initial solution, so as to provide an excellent initial solution for the subsequent tabu search. On the other hand, four neighborhood construction operators are designed in the tabu search process. The flexible storage structure, tabu criterion for avoiding repeated searches and amnesty criterion for enhancing diversity search can effectively get rid of local optimal solution, and finally achieve global optimization. Finally, the experimental analysis is carried out on 56 benchmark examples of Solomon and 18 benchmark examples of Homberger. This algorithm has good convergence and stability, and its solutions are better than the two similar search algorithms in the literature. Moreover, the total driving distance is lower than the currently known best solution on 42 examples.

Key words: vehicle routing optimization, time window, tabu search, variable domain search

摘要： 为了寻求带硬时间窗的车辆路径优化问题的高质量近似解，针对现有数学模型对时间窗约束考虑不充分，建立了最小化车辆数和总行驶距离的双目标非线性优化模型，提出了一种混合变邻域禁忌搜索求解算法。一方面，采用改进的节约算法生成初始解，设计了3种删除算子和一种插入算子对初始解进行扰动优化，为后续禁忌搜索提供优良的初始解；另一方面，基于4种邻域构造算子进行禁忌迭代搜索，利用禁忌搜索的灵活存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则有效摆脱局部最优解，最终实现全局优化。在56个Solomon和18个Homberger基准算例上的实验结果表明，该算法的求解质量优于文献中两种同类型搜索算法，具有良好的收敛性和稳定性，且在42个基准实例上获得了比当前已知最好解更低的车辆总行驶距离。

关键词: 车辆路径优化, 时间窗, 禁忌搜索, 变邻域搜索