随机时变下带时间窗的取送货车辆路径问题优化研究

Study on Optimization Optimizationof Stochastic Time-dependent Time-dependentPickup andndDelivery Problem with Time Windows

针对城市交通路网存在时变性和随机性的特点,文章研究了随机时变下带时间窗的取送货车辆路径问题,提出了随机时变车辆行驶时间的鲁棒优化方法,考虑车载限制和客户服务时间窗的约束,以总行驶时间最小化为目标,建立混合整数规划模型,并提出两阶段的混合遗传模拟退火算法。使用三行染色体编码方式、多段多点交叉算子和修复算子的遗传算法获得较优解,使用模拟退火算法进行优化,获得高质量的解决方案。最后,基于PDPTW标准数据集和STDPDPTW测试算例对文章所提出的算法进行了大量的数值实验,充分验证了模型及算法的有效性。

Based on the time-varying and randomness of urban traffic network characteristics, this paper studies stochastic time-dependent pickup and delivery problem with time windows, puts forward the robust optimization method of random time-varying traffic time. Considering the vehicle restrictions and customer service time window constraints, a mixed integer programming model for minimizing total travel time is set up,and a two-stage hybrid genetic simulated annealing algorithm was proposed. The genetic algorithm used three-line chromosome coding, multi-segment multi-point crossover operator and repair operator was used to obtain a better solution, subsequently, the simulated annealing algorithm was used to optimize the solution to obtain a high quality solution. Finally,based on PDPTW benchmark dataset and STDPDPTW test examples, a large number of numerical experiments are carried out to verify the effectiveness of the proposed model and algorithm.