针对客户满意度和时间窗时域单一的问题,提出一种多时域分级方式衡量车辆配送进度,该设计细化普通时间窗时域,分成多个时域衡量车辆行进位置,算法方面,遗传算法(genetic algorithm,GA)与变邻域下降搜索算法(variable neighborhood descent,VND)的组合优化形式得到静态预优化路径最优车辆行进线路.动态调度周期中,现有贪婪订单插入算法(greedy order insertion algorithm,GOIA)搜索效率不高,提出一种改进后的贪婪订单插入算法(improved new greedy insertion algorithm,IGOIA),摒弃了GOIA随机插入路径的方式,最有原则的将订单插入到配送路径中去,将其与变邻域下降搜索算法组合优化(Genetic algorithm-Variable Neighborhood Descent,GAVND),对未服务的客户点进行局部优化.通过数学模型优化和求解算法改进,在统一平台上与IGOIA-GAVND、GOIA-GAVND与GOIA-GA2-opt的遗传算法改进形式进行对比试验,改进后的动态订单插入算法在不同规模的Solomon算例下,平均目标值降低了 11%,算法平均计算时间降低了 2.74 s,实例分析中,成本解分别节约了 23%、31%、21%,研究结果证明了原则订单插入算法在滚动周期策略作用下可以获得较高质量的解.
Online dynamic demand vehicle routing planning
Aiming at the single problem of customer satisfaction and time window time domain,a multi-time domain hierarchical method was proposed to measure vehicle distribution progress.The design refines the common time window time domain into multiple time domains to measure vehicle traveling position.The combination optimization form of GA and variable neighborhood descent(VND)algorithm was used to obtain the static pre-optimization path optimal vehicle route.In the dynamic scheduling cycle,the existing greedy order insertion algorithm(GOIA)had low search efficiency.An improved new greedy insertion algorithm(IGOIA)was proposed,which abandoned the random insertion path of GOIA and inserts orders into the delivery path in the most principled way.The algorithm was combined with Genetic algorithm-variable Neighborhood Descent(GAVND),and local optimization was performed on unserved customer points.The improved genetic algorithms of IGOIA-GAVND,GOIA-GAVND and GOIA-GA2-opt were compared on a unified platform,the comparison test with other improved forms of genetic algorithm was carried out on the unified platform.The average target value of the improved dynamic order insertion algorithm was reduced by 11%and the average calculation time of the algorithm was reduced by 2.74 s under different scale Solomon examples.The cost solutions save 23%,31%and 21%,respectively.The research results proved that the principle order insertion algorithm could obtain higher quality solutions under the rolling cycle strategy.
multi-domain time windowgenetic algorithmvariable neighborhood descent search algorithmimproved greedy order insertion algorithmrolling period
万方数据
维普
