首页|基于GA-ALNS算法的带可容忍时间窗的VRP求解

基于GA-ALNS算法的带可容忍时间窗的VRP求解

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
针对带可容忍时间窗的车辆路径规划问题,建立最小化配送总成本的规划模型,结合遗传算法构造改进自适应大邻域搜索算法对该问题求解.利用遗传算法构建高质量解开始自适应大邻域搜索寻优,减小算法计算时间成本;加入3种破坏算子和3种修复算子,以增加种群多样性;嵌入模拟退火接受准则以一定概率接受较差解,自适应更新破坏和修复算子权重,避免算法陷入局部最优.选取Solomon标准测试集进行3组实验,与已知最优解比较距离成本验证算法可行性;在单边容忍度时间窗模型下,与基础ALNS算法对比验证算法改进效果;在双边可容忍时间窗模型下,与相关文献的最优结果对比.实验结果表明,提出的GA-ALNS算法改进效果较为显著,求得的最优解同其他算法相比优化率较好,计算得到的最优方案能实现更低的车辆配送总成本,具有一定的可行性和有效性.
GA-ALNS algorithm for solving VRP with tolerance time windows
To solve the vehicle path planning problem with tolerable time window,establish a planning model minimizing the total distribution cost,an improved adaptive large neighborhood search algorithm(GA-ALNS)was constructed with genetic algorithm to solve the problem.Use genetic algorithm to build high-quality solutions to start adaptive large neighborhood search optimization,reduce the time cost of calculation algorithm;add three damage operators and three repair operators to increase the population diversity;embed the simulated annealing acceptance criterion to accept poor solutions with a certain probability,adaptive update damage and repair operator weight,to avoid the algorithm falling into local optimum.The Solomon standard test set was selected for three experiments to compare the feasibility of the distance cost verification algorithm with the known optimal solution;compare with the basic ALNS algorithm and contrast with the optimal results of the relevant literature under the bilateral tolerance time window model.The experimental results show that the improvement effect of GA-ALNS is significant,and the optimal solution is better than other algorithms.The calculated optimal scheme can achieve lower than the total cost of vehicle distribution,which has certain feasibility and effectiveness.

tolerable time windowvehicle path planning problemadaptive large neighborhood search algorithmgenetic algorithmsimulated annealing acceptance criterion

白雪媛、张磊、李琳

展开 >

沈阳航空航天大学理学院,沈阳 110136

可容忍时间窗 车辆路径规划问题 自适应大邻域搜索算法 遗传算法 模拟退火接受准则

国家自然科学基金资助项目辽宁省自然科学基金资助项目辽宁省兴辽英才计划资助项目

614032602020-MS-233XLYC2002017

2024

10.3969/j.issn.1673-5862.2024.01.014

沈阳师范大学学报(自然科学版)
沈阳师范大学

沈阳师范大学学报(自然科学版)

CSTPCD
影响因子：0.591
ISSN：1673-5862
年,卷(期)：2024.42(1)