摘要
针对带有随机旅行时间、随机服务时间及时间窗约束的车辆路径问题,建立了带修正策略的随机规划模型,并给出了两阶段求解方法。第一阶段运用改进遗传算法获取先验路径,第二阶段采用两种混合修正策略(分别记为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.
作者
马俊
张纪会
郭乙运
MA Jun;ZHANG Ji-hui;GUO Yi-yun(Institute of Complexity Science,Qingdao University,Qingdao 266071,China;Shandong Key Laboratory of Industrial Control Technology,Qingdao 266071,China;Qingdao Port Int.Co.Ltd.,Qingdao 266071,China)
出处
《交通运输工程与信息学报》
2021年第4期87-97,共11页
Journal of Transportation Engineering and Information
基金
国家自然科学基金项目(61673228,62072260)
青岛市科技计划项目(21-1-2-16-zhz)。
关键词
物流工程
车辆路径
随机旅行及服务时间
随机规划
混合修正策略
改进遗传算法
logistics engineering
vehicle routing
stochastic travel and service time
stochastic programming
hybrid recourse policy
modifiedgenetic algorithm