一致性车辆路径问题下基于模板路径的模拟退火法

根据一致性车辆路径问题的“服务一致性”特征，本文提出了基于模板路径的 模拟退火法（TSA）以更好地求解此问题.该算法求解分为2 个阶段：第1 阶段求解模板路 径，第2 阶段以所得模板路径为参考获得各天车辆具体配送路径方案，2 个阶段均采用模 拟退火法进行优化.借助小、中规模基准数据集，文章对TSA算法进行数值实验，并将实 验结果与ConRTR算法和TTS算法的结果作比较，利用TSA法求解一致性车辆路径问题 得到的配送路径方案和“服务一致性”指标均得到优化.实验结果表明，运用TSA算法规 划车辆配送路径方案，不仅能够降低运营成本，还能提高配送服务质量.

A Simulated Annealing Heuristic for the Consistent Vehicle Routing Problem

According to the“service consistency”characteristics of the consistent vehicle routing problem, a template-based simulated annealing heuristic (TSA) is proposed to look for better solutions, this algorithm can be divide into two stages: in the first stage, we get the template routes, and in the second stage, the template routes serve as a reference to determine the daily vehicle routing schedules. The simulated annealing heuristic is applied in both stages to get optimal solutions. Based on two small-and middle-scale benchmark data sets, numerical experiments are conducted to test the TSA and then the results are compared to ConRTR’s and TTS’. It can be seen that both the“service consistency”indicators in these two experiments are improved. Therefore, the results prove that by using TSA to plan vehicle delivery routes, not only the operating cost is reduced but also higher service quality obtained.