Abstract: To study the multi-compartment vehicle routing problem,a mathematical model of minimizing the delivery distance was established,and an improved variable neighborhood search algorithm was proposed to solve it.Based on the framework of the variable neighborhood search algorithm,a multi-start optimization mechanism was designed,and a scanning method was used to construct the initial solution.A Shaking process and a global disturbance process were designed to explore the neighborhood solution space,a return and redistribution strategy was proposed to explore the infeasible area in the solution space,a greedy algorithm and multiple hybrid operators were combined to design the search optimization mechanism within and between the sub-paths of the Local Search process to expand the local search,and a maximum number of iterations to stop the rule was applied to end the loop and retain the optimal solution.The experiment and comparative analysis of the adapted calculation examples showed that the improved variable neighborhood search algorithm designed for the characteristics of the multi-compartment vehicle routing problem could plan a more reasonable distribution path,obtain a more stable high-quality solution,and achieve a more obvious optimization effect in an appropriate time.

Key words: improved variable neighborhood search algorithm, multi-compartment vehicles, vehicle routing problem, variable neighborhood search algorithm

摘要： 为了研究多隔室车辆路径优化问题,建立最小化配送距离数学模型,提出一种改进变邻域搜索算法进行求解。基于变邻域搜索算法框架,设计了多起点寻优机制,运用扫描法构造初始解,设计了Shaking过程与全局扰动过程进行邻域解空间探索,提出还原及再分配策略探寻解空间中不可行区域,结合贪婪算法和多种混合算子设计了Local Search过程的子路径内及子路径间搜索优化机制以展开局部搜索,应用最大迭代次数停止准则结束循环并保留最优解。通过改编算例的实验及对比分析表明,针对多隔室车辆路径优化问题特点设计的改进变邻域搜索算法能够在合适的时间内规划出更合理的配送路径,获得更稳定的高质量解,达到更明显的优化效果。

关键词: 改进变邻域搜索算法, 多隔室车辆, 车辆路径问题, 变邻域搜索算法