考虑交通拥堵及工作量平衡性的一致性车辆路径问题

为研究快递公司在提供一致性配送服务时，交通拥堵以及快递人员工作量平衡性因素对配送路径的影响，在传统车辆路径问题研究的基础上，提出了考虑拥堵和工作量的一致性车辆路径问题，并构建了混合整数规划模型。针对该模型的NP难性质，提出了基于模板路径的两阶段模拟退火算法（template-based simulated annealing heuristic，TSA）。该算法通过构建模板路径求解初始路径方案，再利用模拟退火算法优化路径方案，降低车辆总行驶时间。将该模型和算法应用于3组基准数据（benchmark data set）的数值实验，结果表明:本文模型和算法能有效解决此类问题，交通拥堵使最优配送路径的总行驶时间平均增加18.38%，使快递人员在任意两天到达同一顾客的最早与最晚时刻之差平均增加12.92%；当快递人员配件量的不平衡性平均下降35.82%后，二者仅分别平均增加2.29%和1.68%。 

Consistent Vehicle Routing Problem Considering Traffic Congestion and Workload Balance

In order to investigate the effects of transportation congestion and workload balance on the delivery routing of express delivery companies which wish to provide consistent services, a consistent vehicle routing problem considering traffic congestion and workload balance was proposed and a mixed integer programming model for this problem was constructed. In view of the model' s NP-hard property, a two-phase template-based simulated annealing method (TSA) was applied to solve this problem. The TSA attains an initial route plan by constructing template routes first, and then optimizes them using the simulated annealing method to decrease the total travel time. To verify the validity of the proposed model and algorithm, numerical experiments were conducted using three benchmark data sets. Results show that the model and TSA can solve this problem effectively. The traffic congestion will significantly increase the total travel time by an average of 18.38% and increase the difference between the earliest and latest arrival time at the same customer within any two days by an average of 12.92%. Besides, when the average difference of the delivery men's shipment quantity decreases by 35.82%, the total travel time and the difference between the earliest and latest arrival time at the same customer are only increased by 2.29% and 1.68%, respectively.