-
题名改进遗传算法搜索动态订单下车辆路径最优问题
- 1
-
-
作者
李二超
张智钊
-
机构
兰州理工大学电气工程与信息工程学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2024年第10期353-364,共12页
-
基金
国家自然科学基金(62063019)。
-
文摘
滚动周期策略是当前学者利用优化算法解决动态车辆路径规划(dynamic vehicle routing planning,DVRP)问题的主要研究策略。预优化算法是基于遗传算法(genetic algorithm,GA)进行改进。GA易早熟和易陷入局部最优的特点,使解的质量往往不能达到最好。针对此问题,在GA算法上提出了贪婪重构策略进行改进。贪婪重构遗传算法(greedy reconstruction genetic algorithm,GRGA)随机剔除每条路径固定数量的客户点,利用贪婪重构策略依次将剔除点插入到各个路径,保留成本最低的解,摒弃了完全随机的策略原则,使解可以跳出局部最优。在每次迭代之后利用变邻域下降搜索算法(variable neighborhood descent,VND)进行深度搜索,完成一次迭代。最后进行三组测试,第一组是在统一平台上采用Solomon数据集测试算法效果,第二组是把预优化改进算法与对比算法得到的数据分别进行保存,利用控制变量法在动态调度周期使用一种动态调度优化算法,分别对每个预优化算法形成的初始路径进行调度,测试改进算法的有效性,第三组是采用实际案例测试预优化算法的效果。
-
关键词
时间窗
遗传算法
变邻域下降搜索算法
贪婪重构策略
滚动周期
-
Keywords
time window
genetic algorithm
variable neighborhood descending search algorithm
greedy reconstruction strategy
rolling period
-
分类号
U116.2
[交通运输工程]
TP391
[自动化与计算机技术—计算机应用技术]
-