随着电子商务的崛起,物流企业在处理车辆调度问题时,暴露了许多不足之处。目前的车辆调度问题大多以车辆运营成本最小为优化目标,在处理时间窗时,多采用添加违反时间窗惩罚成本的措施。实际运行中由于车辆服务时间与客户时间窗的不对称,造成了客户投诉的居高不下,说明惩罚成本并不能客观地反映客户满意度。同时,车辆在服务一定数量的客户后会产生调整时间,由于车辆的行驶距离不同,调整时间是变化的,故本文研究了考虑变化调整时间及带有时间窗的车辆调度问题(capacitated vehicle routing problem with time windows and variable adjustment time,CVRPTW-VAT)。主要研究内容如下:(1)结合实际车辆服务的环境,考虑车辆在配送中遇到例行检修、燃料补给、人员休整等调整工作而产生的变化调整时间,给出了调整时间与车辆行驶距离的函数关系,同时给出了客户满意度与时间窗的隶属度函数,建立了CVRPTW-VAT的数学规划模型,以最小化车辆行驶距离,最大化客户满意度,最小化车辆使用数量为优化目标,旨在降低配送成本,保证配送服务质量。(2)设计了求解CVRPTW-VAT的分散搜索(scatter search,SS)算法,具体包括基于车辆容量约束和时间窗约束的启发式插入算法进行多样性初始解的生成、保留精英策略选择和随机选择用于参考集的生成、基于弧组合算法的组合算子、基于时间窗约束和车辆容量约束的修复算子、基于插入的提高算子等;同时设计了遗传算法(genetic algorithm,GA)作为对比算法。(3)针对带有容量约束的车辆调度问题、带有时间窗的车辆调度问题、CVRPTWVAT,采用SS算法进行求解,验证了固定车辆数量的调度方案和最小化车辆数量的调度方案两种不同情况。实验结果表明,SS算法求解本文研究的车辆调度问题,优化效果较好。