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

摘要

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