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

Hybrid Recourse Policy for the Vehicle Routing Problem with Stochastic Time

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

For the vehicle routing problem with stochastic travel and service time,and time windows,this study provides a stochastic programming model with a recourse and two-stage solving method.In the first stage,a modified genetic algorithm is used to find a prior route;in the second stage,two hybrid recourse policies(denoted by A and B,respectively)are designed to recourse the failure route.Based on a stochastic simulation experiment,the hybrid recourse policy denoted as A(B)determines whether the delayed service to the current customer(the service to the next customer)will cause a large-scale delayed service to the subsequent customers in the prior route,and makes a corresponding decision.Based on the Solomon benchmarks,the superiority of the two hybrid recourse policies and effectiveness of the modified genetic algorithm are shown,respectively,by comparing the experimental simulation results with those of the common recourse policies and the CPLEX Optimizer.The results have an unequivocal significance as a reference for how to solve the stochastic vehicle routing problem.