马 俊，张纪会，郭乙运

基于混合修正策略的随机时间车辆路径优化方法

马 俊1, 2，张纪会1, 2，郭乙运3

(1. 青岛大学，复杂性科学研究所，青岛 266071；2. 山东省工业控制技术重点实验室，青岛 266071；3. 青岛港国际股份有限公司，青岛 266071)

针对带有随机旅行时间、随机服务时间及时间窗约束的车辆路径问题，建立了带修正策略的随机规划模型，并给出了两阶段求解方法。第一阶段运用改进遗传算法获取先验路径，第二阶段采用两种混合修正策略(分别记为A、B)调整“失败”的先验路径。混合修正策略A(B)通过随机模拟实验判断对当前顾客的延迟服务(对下一顾客的服务)是否会对该路径后续顾客造成大规模延迟服务，并采取相应的调整措施。基于Solomon算例进行了仿真实验，对小规模算例将仿真结果同CPLEX求解结果作对比；对大规模算例将仿真结果同已知最优解作对比。结果表明：所给算法可获得小规模算例的精确解，大规模算例的近似最优解。同时，对比不同策略下的仿真结果表明两种混合修正策略具有优越性，研究结果对随机车辆路径问题的求解具有一定的参考意义。

物流工程；车辆路径；随机旅行及服务时间；随机规划；混合修正策略；改进遗传算法

0 引 言

车辆路径问题(Vehicle Routing Problem，VRP)是Dantzig和Ramser[1]提出的一类经典组合优化问题。自提出至今，已应用于众多领域，如物流配送、垃圾回收[2]、上门维修及医疗服务等，并演化出许多不同问题，如带容量或时间窗约束的VRP等，有关VRP的最新研究综述参见文献[3]。……